AtCoder Beginner Contest 236 (ABC236) D - Dance を解いた。

問題: https://atcoder.jp/contests/abc236/tasks/abc236_d

本番では解けなかった。そのときに考えたこととしては……。 XOR の処理から途中で最善のものを判断することは難しそうなのでおそらく全探索だろうと判断した。愚直にやってしまうと 16! で間に合わない。 2 グループに分ける 16 C 8 ごとに 8! で考えたのだけど 10^8 で間に合わなかった。

解説を見ると、 DFS で全探索し各ペアの小さい側を未選択のもののうち最小にするようにしていた。これで 15 * 13 * 11 * 9 * 7 * 5 * 3 * 1 通りで 10^6 で間に合うらしい。

• 解説: https://atcoder.jp/contests/abc236/editorial/3285
• 提出: https://atcoder.jp/contests/abc236/submissions/28777403

今日のコミット。

• rust-sandbox 3 commits
  • its: 0.6.3
  • its: Updated argopt
  • its: Added some traits
• rust-atcoder 1 commit
  • abc236 d