AtCoder Beginner Contest 162 感想

https://atcoder.jp/contests/abc162

28位。F問題で2、3個飛ばしするDP書いたらバグっちゃった。

A,B,Cはいうことなし。Dはj-i≠k-jがなければ（赤の数）×（緑の数）×（青の数）で求まるので、そこからj-i=k-jであるものを引けばいい。

E問題は約数包除（？）ですぐ解ける。最大公約数が x になるような組の個数 F(x) を求めることを目標にする。これが求まれば答えは x F(x) の総和になる。直接 F(x) を計算するのは難しいため、まず公約数が x の倍数であるような組の個数 G(x) を求め、ここから F(x) を復元する。G(x) の計算は容易であり、F(x) への復元も包除原理によって達成できる。

F問題。自分は偶数個と奇数個で場合分けをした。この先では、選んだものを黒で塗り、選ばなかったものを白で塗ることにする。

偶数個のとき

２個ずつのまとまりにする。あるまとまりを見たとき、白と黒がひとつずつになっているはずである。

さらに少し考えると次の形以外ありえないことがわかる。よって偶数個のときは累積和で解ける。

奇数個のとき

偶数個のときと同じように２個ずつのまとまりにする。ただし一つ余るはずである。

あまったものは白であるとしてよい。あまりはかならず奇数番目になるが、かならず奇数番目の白が存在する。全て黒だと取り過ぎになってしまうので。

このとき選んだものは次のような形をしているはずである。よってDPで解ける。