geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC236 参加記録

コンテスト中AC:A〜C

D - Dance

解けなかったので、反省点含めて記録します。
まず、Nが小さいことから全探索が可能と予想して、全状態数を見積ってみました。

例えば、N = 3のとき、{1,1,2,2,3,3}を並べ替え、人{1,2,3,4,5,6}に対応させ、同じ数字を2人組にするという方法を考えました。
{1,2,2,3,1,3}なら、{1,5},{2,3},{4,6}という具合です。

これは同じ物を含む並び替えなので、
\frac{(2N)!}{(2!)^N}
が並び替えの総数です。N=8の時を計算すると、81,729,648,000通りとなり全探索は無理そうだという結論になりました。しかし、これは誤りです。

例えば、N=2のとき、以下のように全探索できて、楽しさが異なるような組の作り方は3通りになります。

  1. 人1と同じ組になる人を全探索する。
    {1,2},{1,3},{1,4}のいずれかとなる。

  2. 残りの組を決める

    • {1,2}のとき、{3,4}を組にしてA_{1,2}\oplus A_{3,4}を計算する
    • {1,3}のとき、{2,4}を組にしてA_{1,3}\oplus A_{2,4}を計算する
    • {1,4}のとき、{2,3}を組にするA_{1,4}\oplus A_{2,3}を計算する

最初の見積りだと、6通りになっています。何がまずかったかというと、組の作る順序を考慮してしまっています。言い換えると、組に番号をつけて区別してしまっています。
最初の見積りだと、{1,2,2,3,1,3}と{3,1,1,2,3,2}は区別されます。しかし、排他的論理和は順序によらず同じになるので、これらを同一視できます。

ボールと箱の問題に言い換えてみると、最初の見積もり方法は、

  • 区別のある箱に区別のあるボールを2個ずついれる方法の総数

正しい見積もりは、

  • 区別のない箱に区別のあるボールを2個ずついれる方法の総数

です。

従って、正しい見積もりは、各組の選び方に対して組に番号をふる方法がN!通りあるので、これを除いた
\frac{(2N)!}{(2!)^N N!}
です(多分)。
N=8のとき、2,027,025通りとなり、これで全探索可能ということがわかりました。

実装に移ります。
全探索ですが、同じ組の組み合わせを作らないようにする必要があります。これは典型とも言えるかも知れませんが、小さい順に決定していくと上手くいきます。具体的には、
1. 組を作っていない人の中で番号が最も小さい人iを選ぶ
2. 人iと組を作れる人全員について、それぞれの人と組を作り、それぞれの場合について1に戻る

となります。この様に状態が複雑に変化してfor文で処理しきれない場合はDFSが有効です。
一応、実装を載せておきますが、無駄に長く、ややこしい実装になってしまったので、他の人を参考にした方が良いです。
提出コード

ここからは直接問題とは関係の無い内容となります。

状態遷移を伴うDFS

状態遷移を伴うDFSは苦手だったので、今後のために実装方針をまとめておきます。
個人の見解なので、間違いなどあるかもしれません。

考慮すべき事項

  • 状態の管理に必要な情報
  • 情報の受け渡し方法
  • 終了条件

状態の管理に必要な情報

今回の問題場合、以下の2つの情報が必要です。

  • 人iが既に選ばれたかどうか
  • 組に基づくXOR和

人iが選ばれたどうかは、例えば、配列などに記録するか、冪集合で管理します。

情報の受け渡し方法

2パターンに分けてみました。

値渡し

おそらく実装が楽になるので、可能な限りこちらを考慮すべきかなと思います。しかし、情報が配列や二次元配列などを含むと何度もコピーが作られることになるので、この場合は避けた方が無難だと思います。

グローバル変数等で共有

状態に配列が含まれる場合に、必要な変更のみを加えることで計算量を抑えられます。但し、探索が終了した場合に状態を復元する必要があります。

今回の問題では、他の方の実装を見ると、XOR和は値渡しして、人iが使われたかどうかはグローバル変数等で共有しているものが多い様に思います。また、冪集合で管理して値渡しをしているものもありました。

終了条件

探索方法にも絡みますが、終了条件を設定する必要があります。呼び出し先で終了判定するのが良さそうです。
自分の実装では、番号最小の人を選ぶのを呼び出し元で決定してしまっています。組を1つ作って、更に番号最小の人まで選んでしまっているので、終了条件を判定する位置もおかしな場所になり、状態の復元も相まってよくわからない感じになっています。

あとは、図示してみると整理されるのかなと思いますので、時間があれば図示の例を載せたいです。