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}という具合です。
これは同じ物を含む並び替えなので、
が並び替えの総数です。N=8の時を計算すると、81,729,648,000通りとなり全探索は無理そうだという結論になりました。しかし、これは誤りです。
例えば、N=2のとき、以下のように全探索できて、楽しさが異なるような組の作り方は3通りになります。
人1と同じ組になる人を全探索する。
{1,2},{1,3},{1,4}のいずれかとなる。残りの組を決める
- {1,2}のとき、{3,4}を組にしてを計算する
- {1,3}のとき、{2,4}を組にしてを計算する
- {1,4}のとき、{2,3}を組にするを計算する
最初の見積りだと、6通りになっています。何がまずかったかというと、組の作る順序を考慮してしまっています。言い換えると、組に番号をつけて区別してしまっています。
最初の見積りだと、{1,2,2,3,1,3}と{3,1,1,2,3,2}は区別されます。しかし、排他的論理和は順序によらず同じになるので、これらを同一視できます。
ボールと箱の問題に言い換えてみると、最初の見積もり方法は、
- 区別のある箱に区別のあるボールを2個ずついれる方法の総数
正しい見積もりは、
- 区別のない箱に区別のあるボールを2個ずついれる方法の総数
です。
従って、正しい見積もりは、各組の選び方に対して組に番号をふる方法が通りあるので、これを除いた
です(多分)。
N=8のとき、2,027,025通りとなり、これで全探索可能ということがわかりました。
実装に移ります。
全探索ですが、同じ組の組み合わせを作らないようにする必要があります。これは典型とも言えるかも知れませんが、小さい順に決定していくと上手くいきます。具体的には、
1. 組を作っていない人の中で番号が最も小さい人を選ぶ
2. 人と組を作れる人全員について、それぞれの人と組を作り、それぞれの場合について1に戻る
となります。この様に状態が複雑に変化してfor文で処理しきれない場合はDFSが有効です。
一応、実装を載せておきますが、無駄に長く、ややこしい実装になってしまったので、他の人を参考にした方が良いです。
提出コード
ここからは直接問題とは関係の無い内容となります。
状態遷移を伴うDFS
状態遷移を伴うDFSは苦手だったので、今後のために実装方針をまとめておきます。
個人の見解なので、間違いなどあるかもしれません。
考慮すべき事項
- 状態の管理に必要な情報
- 情報の受け渡し方法
- 終了条件
状態の管理に必要な情報
今回の問題場合、以下の2つの情報が必要です。
- 人iが既に選ばれたかどうか
- 組に基づくXOR和
人iが選ばれたどうかは、例えば、配列などに記録するか、冪集合で管理します。
情報の受け渡し方法
2パターンに分けてみました。
- 値渡し
- グローバル変数で共有
値渡し
おそらく実装が楽になるので、可能な限りこちらを考慮すべきかなと思います。しかし、情報が配列や二次元配列などを含むと何度もコピーが作られることになるので、この場合は避けた方が無難だと思います。
グローバル変数等で共有
状態に配列が含まれる場合に、必要な変更のみを加えることで計算量を抑えられます。但し、探索が終了した場合に状態を復元する必要があります。
今回の問題では、他の方の実装を見ると、XOR和は値渡しして、人iが使われたかどうかはグローバル変数等で共有しているものが多い様に思います。また、冪集合で管理して値渡しをしているものもありました。
終了条件
探索方法にも絡みますが、終了条件を設定する必要があります。呼び出し先で終了判定するのが良さそうです。
自分の実装では、番号最小の人を選ぶのを呼び出し元で決定してしまっています。組を1つ作って、更に番号最小の人まで選んでしまっているので、終了条件を判定する位置もおかしな場所になり、状態の復元も相まってよくわからない感じになっています。
あとは、図示してみると整理されるのかなと思いますので、時間があれば図示の例を載せたいです。