AtCoder Beginner Contest 152

　Fが解けずの五完でしたが、後で見直したらFは難しくなかった。直後にCodeforcesがあったので疲れないようにやろう、とは思っていたけど、実装が大変な問題でもなかったし……。

コンテストへのリンク

A - AC or WA

　N=Mか調べる。

B - Comparing Strings

　小さい数字を繰り返した方がお得。

C - Low Elements

　今までで一番小さい数字を管理

D - Handstand 2

　最初、桁DPのようなことをしなくちゃいけないのか、と思って飛ばした。

　冷静になると、1以上N以下の「最初の数字がiで最後の数字がjとなるような数字の個数」が全探索できるので、それを使って計算できる。

E - Flatten

　Aの最小公倍数を$A_i*B_i$とすれば良い。

　Pythonなら直接最小公倍数を求めて解くことも可能だったらしいけど、私は各素因数を何回使うかを調べて、modを取りながら最小公倍数を求めました。

F - Tree and Constraints

　コンテスト時の書き換えのファイルを見たら、

DP=[0]*(1<<M)

　とか書いて止まってたのですが、ここで止まるのはおかしい。この方針（bit DP）で解けます。

　各制約が満たされているかどうかを状態を持つDPをします。

　各制約のpathに含まれる頂点が何かを前計算しておいて、各辺を白く塗るか/黒く塗るかでDPを更新。

　初期値はDP[0]=1

　辺を見る順番もどうでも良いので（なので、本質的に木であることを使ってない。直線と解き方同じ）、1から順番に見ていくとすると、k番目の更新は、path中にkを含むものの和集合をBとして、各i(0<=i<2^M)について、

DP[i|B]+=DP[i]

　とすればOK。
　1<<Mから0へ、大きい順に見ていけば、DPテーブルを使い回すこともできる。

　これで、（前計算を除いて）計算量は$2^M*M$となるので解けます。（前計算はM回DFSしてO(N*M)でしましたが、もっと速くなるはず）

　今、公式解説を見たら包除原理って書いてあって驚いた（他の解説ブログ等も見たけど、大体包除原理を使ってそう？）のだけど、この方針の方が自然では？

　この後、解説放送を見たりして包除原理の解法を理解しました。いや、でもやっぱりこの解法の方が簡単では？
（youtubeのコメントでこの解法に言及されている方がいました。コメント内では、本質的には包除原理と同じ解法という話になっていたみたいです。うーん、私には違う解法に見えるんですが……。）