7K12 blog

猫でも分かるアルゴリズム解説

ABC129 E - Sum Equals Xor

f:id:tkr987:20200204235609p:plain

https://atcoder.jp/contests/abc129/submissions/9899468

 

感想: 頭が悪すぎて一生DP書けない

 

頭が悪すぎて最初

DP[i][j][k] := i桁目のビット組jが(00,01,10,11)でi-1番目のビットを加算したときキャリービットがkとなる組み合わせの個数

と定義して何も分からなくて1ミリもプログラムを書くことが出来なかった。

f:id:tkr987:20200204235624p:plain

紙に絵を書いても頭が悪くてa AND b = 1となるとき絶対にa + b = a XOR bとならないということに気づけなかった。まぁ、そこは運が良ければ気づけるかもしれないので、あまり気にしないことにしたい。

 

そして、正しいDP定義は中々難しい。

DP[i][状態] := i桁目まで見ていて以下の状態における組み合わせの個数

状態0 = L[i]が1のとき、0桁目からi桁目までの過去において真面目に(a,b)=(0,1)(1,0)として考えた事しかない状態。

状態1 = 0桁目からi桁目までの間、つまりL[0]からL[i]の間にLの値が1のところ(a,b)=(0,0)として考えた過去が存在する。この状態になると、i桁目以降(a,b)=(0,0)(0,1)(1,0) どれを選んでもLを超えない。

f:id:tkr987:20200205005843p:plain

 Lの桁DPであることは制約を見れば誰でも分かるが、(a,b) = (0,0)(0,1)(1,0)が採用できる場合、DP[i][状態] += DP[i][状態] * 3のように書けるので実はDPは2次元で済む、というのは大事なポイントになりそう。そして、初見だと「えっ状態でDP!?天才か!?」と感じると思うが、過去にABC117Dで同じようなテクニックが使われたことがある。

https://atcoder.jp/contests/abc117/tasks/abc117_d

自分はABC117Dを既に解いていたが、頭が悪くて今回も自力で実装できなかった。才能なくて萎える。

 

あと、状態0と状態1から状態1への遷移の書き方だが、

DP[i][状態1] += (DP[i][状態0] + DP[i][状態1]);

と書くより

DP[i][状態1] += DP[i][状態0];

DP[i][状態1] += DP[i][状態1];

と書いたほうが状態1つずつ考察できて頭を使わずに済む。少なくとも自分は頭が悪くて1行で書くことは出来なかった。解説を書いても結局のところ自力で書けないので一生プログラミング書けるようになる気がしない。