AtCoder Beginner Contest 132 参加記

前回の参加記はこちら。今回も振り返っていきます。


問題

D - Blue and Red Balls

i回操作する場合、赤ボールの両端、または間のi箇所に青ボールを入れるので、その組み合わせはcomb[N+K-1][i] * comb[K-1][i-1]通りになる。重複組み合せなので、ボールの間に仕切りを入れるイメージでやると良い。また、Nは2000以下なのでcombはパスカルの三角形で列挙すれば良い。

...というのを数学苦手マンのわりにはコンテスト中に早めに気付けたのが良かったです。

E - Hopscotch Addict

けんけんぱの「けん(1回目)」と「けん(2回目)」と「ぱ」の3状態を保持するようにしてBFSすれば良いです。

途中まで有向グラフであることを見落としていて「けんけんぱを2頂点間でやれば絶対ゴールできるやん」などと考えていて危なかったです。サンプルのテストケースに救われました。

F - Small Products

「√Nでいい感じにDPするんだろうな〜」という予想はできたけど、それ以上はコンテスト中は分からず解けませんでした。要復習。

振り返り

今回もABCDEの5完でした。前回 早解きすること を課題としていましたが、今回はいい感じに早解きができたので良かったです。ABC過去問のABCだけを早解きする練習を少しやっていたので、その効果が出たのかな?と思います。とはいえ、今回たまたま早解きできた説もあるので、次回もこんな感じでやっていけるようにしたいです。