ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC271

もう少しうまくできたはずです。
コンテスト
提出

C - Manga

二分探索。
捨てられる本を先にカウントします。

D - Flip and Adjust

DPです。dp[i][j] = i枚目まで選び、総和がjになるとき、最後に選んだ表裏の種類、としてDPしていきます。

E - Subsequence Path

諸悪の根源。数列Eが頂点の列だと思って30分以上費やしました。これがなければFが通っていたと思うと…
dp[i][j] = i項目まで見たときの頂点jの最小距離、としてこれを一次元に圧縮します。

F - XOR on Grid Path

一行足りなくてコンテスト中ACまで3分足りませんでした。 半分全列挙します。
N-1回移動した段階でどのマスでどの値になっているか、を列挙します。これをスタートからとゴールから行います。今いるマスについて、スタートから今までの値と、そこからの値は同じになっていれば最終的に0になるので、あとはうまく組み合わせを探して数えればおしまいです。

G - Access Counter

dp[i][j] = i時で、次に誰かがアクセスした時刻がjになるような確率、とすると、これを行列とみなしてN乗し、iが23、jが青木君のアクセス時刻になるようなもののマス目の値を足して答えになります。
行列の中身ですが、これは無限等比級数になります。1日誰もアクセスしない確率が公比、初項は直近のjでアクセスする確率です。
あとはこの級数の和を求めればOKです。