131. AtCoder参加記録（AtCoder Beginner Contest 265）

34回参加でレート 1410 です。

今回はパフォーマンス 1680 です。

ABCDEを通して、FGExは未解答です。Cで1ペナ、Dで1ペナ。

各問題の思考過程など。

2分7秒。

パッと思いつかなかったので全探索しました…

4分38秒。

書かれている通りにやるだけ。持ち時間の消費タイミング、移動可能判定のタイミングなどに注意しつつ書けばOK。

初回提出6分10秒、そこからACまで1分16秒。

あるマスにいるとき取れる行動は1つだけなので、以前訪れたマスに再訪した場合は無限ループになります。よって、状態は $O(HW)$ しか無いので普通にシミュレーションすれば間に合います。

if に else を付けるのをサボってバグらせてしまい、悲しい1ペナ。かなり痛い…。

初回提出8分37秒、そこからACまで8分11秒。

ちょっとややこしいので入力例1を書いてみる。区間和が $P + Q + R$ になるような場所を見つけるのが必要なのか。
区間和なので累積和がすぐ想起される。
$x$ が決まれば、 $y$ は $x$ から $y-1$ の区間和が $P$ になるところ、 $z$ は $x$ から $z-1$ の区間和が $P+Q$ になるところ、 $w$ は $x$ から $w - 1$ の区間和が $P+Q+R$ になるところを求めればよい。一見ややこしいが、要するに「累積和に対して二分探索」を3回並列でやるだけ。これで $O(N \log N)$ なのでOK。
添字バグで1ペナ。やたら時間を取られつつ修正…。

なんでこんなに時間掛かったんだろう…という感じでした。添字バグは普通に実力不足。

37分11秒。正しい方針に辿り着くまでかなり時間を要しましたが、そこからは早かったです。

愚直解は $O(3^N)$ なので当然無理。
全通りから障害物を通るルートだけ引く？と考える。操作1～3をそれぞれ何回行うのか、を全探索すれば $O(N^3)$ になるので、計算量的にこの操作が想定解に含まれてる気がする。
各操作回数が決まった状態で辿り着く座標は、操作順序に依存しない。ある操作回数で障害物に辿り着いた場合、そこまでの通り数は次のステップに加算しないような処理になれば嬉しい… → ここからDPに発想が行き始める
少しずつ操作回数を増やすようなDPなので、（全操作回数, 操作1の回数, 操作2の回数, 操作3の回数）という状態が必要そう…。これは流石に実行時間制限3秒でも無理では？
操作3の回数は、全操作回数から他の操作回数の和を引けばよかった。じゃあこれでいいか。
ある座標に障害物が存在するかは、座標値を上手く64ビット整数に押し込むことで HashSet によって $O(1)$ で判定できる。
$dp[i,j,k] = (全i回操作し、操作1をj回、操作2をk回行うときの障害物を経由しない通り数)$
という定義になる。