AtCoder Regular Contest 116 D問題 「I Wanna Win The Game」解説。
普段は個別問題の解説は書かない。けど、今回は本番中に解けたけど考えすぎてめっちゃ疲れたので、まとめておく。
細かい書き方はやや適当にしています。(個別の問題の解説を見に来る人はそれほど多くないだろうから、きっちり書き上げる重要性は低い)
しばらくは例1を使って考える。
まず重要なのは、bit XORを考える問題は、それぞれのbitを独立に考えれば良い。あるbitの結果は他のbitの結果に全く影響しない。
例1にある
5 20 --- (1, 2, 3, 7, 7)
を考えて、それをbitに分解する。bitごとに出現回数を見ると
- 4のbit→2回立っているからbit XOR = 0
- 2のbit→4回立っているからbit XOR = 0
- 1のbit→4回立っているからbit XOR = 0
となる。合計の20は、4*2 + 2*4 + 1*4 = 20
と分解できる。
各bitの登場回数が分かったら、何通りか分かるか?
逆に考えると、
- 4のbitが、2回立っている
- 2のbitが、4回立っている
- 1のbitが、4回立っている
という数列ならば、合計は20であり、そのXORは0なので条件を満たす。
では、このような数列はいくつあるか?
- 4のbitの割り当て方は5C2 = 10通り
- 2のbitの割り当て方は5C4 = 5通り
- 1のbitの割り当て方は5C4 = 5通り
これをかければよく、10*5*5 = 250通り
である。
合計Mから、各bitへの振り分けを全て考えてみよう
bit XORが0となる必要十分条件は、全てのbitに関して登場回数が偶数であることである。 したがって、bit XORが0となるためには、合計Mは偶数でなければならない。したがってMが奇数なら答えは0だ。
いまMを偶数とする。 登場回数は全て偶数なので、2で割ろう。合計もM=20を2で割った10になる。 10を各bitに振り分けるやり方をすべて書き出し、それぞれの場合の数を計算すると、以下の5通りになる。
10 = 8*0 + 4*2 + 2*1 + 1*0 → 5C0 * 5C4 * 5C2 * 5C0 = 50 10 = 8*0 + 4*2 + 2*0 + 1*2 → 5C0 * 5C4 * 5C0 * 5C4 = 25 10 = 8*0 + 4*1 + 2*2 + 1*2 → 5C0 * 5C2 * 5C4 * 5C2 = 250 (上の例) 10 = 8*1 + 4*0 + 2*1 + 1*0 → 5C2 * 5C0 * 5C2 * 5C0 = 100 10 = 8*1 + 4*0 + 2*0 + 1*2 → 5C2 * 5C0 * 5C0 * 5C4 = 50 ↓ 合計475
適切な振り分けのための条件
上の例では「M/2 = 10 を各bitに振り分けるやり方」を全部考えた。
一般の偶数Mの場合は、どうすれば振り分け方を全部考えられるだろうか?
いっぺんに決めるのは難しそうだ。
上位ビットから決めるか、下位ビットから決めるか。
上位ビットから決めることにしよう。
(N//2 は、N÷2の整数部分を表わす。)
今、振り分けるべき残りの数をrestとし、あるビット(digitと書く)にk個を振り分けたとしよう。(最終的には、N個のうち2k個の数の当該ビットを立てることになる。)
kが適切な値である条件は、以下3つである。
- 0以上 N//2以下である
(0 <= k <= N//2)
- 今見ているビットよりも下位の桁に振り分けられる数は高々
(下位ビットの和) * (N//2)
である。したがって、振り分けた残りがこれ以下でなければいけない。(rest - digit * k <= (digit-1) * N//2)
- 振り分けた残りが負になってはいけない
(rest - digit * k <= (digit-1) * N//2)
DP
天下り的だが、DPを導入する。
(DPに行き着くまでの思考過程は後述する)
M/2を各bitに振り分ける。
DP[bit][rest]を、今からbitの桁に数を振り分けようとしていて、残りの数がrestであるときの、N個の数の決め方、とする。(例えばbitが3だったら23 = 8の桁に振り分けようとしている。)
- 初期条件:
DP[0][rest] = N C 2*rest
- 最後に1のビットに振り分けるという状態で、残った数がrestである。この場合のN個の数の決め方は
N C 2*rest
通りである。
- 最後に1のビットに振り分けるという状態で、残った数がrestである。この場合のN個の数の決め方は
- 最終的な答え:
DP[12][M/2]
- 振り分ける可能性のある最上位桁は、212 = 2048である。なぜならM/2は高々2500なので、4096以上のbitに与えたら残りが負になってしまい不適当となるからだ。
- 漸化式:
DP[bit][rest] = SUM(DP[bit-1][rest - (2**bit) * k] * N C 2k)
(kの動く範囲は、上記3つの条件を全て満たす範囲)- 適切なkを選ぶと、それより下位のビットに振り分ける数は
rest - (2**bit) * k
である。今見ているbitに関しては、N個のうち2k個を選んでビットを立てる。その選び方はN C 2k
である。
- 適切なkを選ぶと、それより下位のビットに振り分ける数は
計算量について:
DPテーブルのマス目の個数は12 * M/2 <= 12 * 2500 = 30000
DPテーブルのマス目を1つ計算するための計算量は、正当なkの範囲なので高々 N//2 = 2500
単純にかけると75000000 = 7500万となる。厳しそうだが、kに関する他の条件により実際はこれより少ない。
なんで解くのに時間がかかったんだろうか
ここが本来書きたかったパートだわ。
Cが解けたのが40分、Dが解けたのが101分なので、61分もかかっている。これは時間がかかり過ぎたと思う。
コンテスト本番中の思考を再現すると、次のようになる。
- 「M/2 を各bitに振り分けるやり方」を全部列挙して、それぞれについて掛けて最後に足し合わせれば良さそう
- 上位ビットから順に決めれば良さそう
- ということは……現在見ているビットに対して再帰関数になる?
- しかも再帰を全部計算してると同じ状態を何度も計算し直すことになる。そのせいで間に合わない。
- メモ化する必要がある。
- メモ化再帰? メモ化再帰をちゃんと書くなんてめったに無いぞ? マジで?
- あ、メモ化再帰ってことはDPと同等なのか。DPでいいのか?
- DPテーブルの定義をこうやると……あ、DPでいけそう。
解法の指針がDPだということを確定するまでに時間がかかったんだと思う。
kyopro_friendsさんはメモ化再帰でやってるぽいけど。
サーバル「D問題は、奇数の個数を全探索すると、2進法の1の位は決まって、全体を2で割って小さいサイズの問題にできるよ。メモ化再帰で実装するのが簡単だね」 pic.twitter.com/bKuZF6Qcim
— 競技プログラミングをするフレンズ (@kyopro_friends) 2021年3月28日
あと、
- 「適切な振り分けのための条件」を考えているときは、上位ビット
- しかし、DPテーブルを計算するときは下位ビットから順に計算している
というのが腑に落ちない。どこで逆転したんだ?