titiaのノート: キーエンスプログラミングコンテスト 2021

2021年1月16日土曜日

　Dまで四完でした。一ヶ月くらいレートマイナスが続いていたので、プラスでほっとしました。

C - Robot on Grid

　文字が書かれていないマスでは、2/3の確率で右にいけ（RかXを書き込んだとき）、2/3の確率で下にいける(DとXを書き込んだとき)、と考えると上手くいった。

　類題と気付くまでも気付いてからも時間がかかってしまったけど、復習したときもよく理解せずACしたので仕方なかったかな、とも。

　「アダマール行列」というキーワードがでてきたので、「高校数学の美しい物語」の該当ページくらいは理解しておきたい。

　すぬけさんの解説動画を見てAC。

　自分も含め、区間DPっぽいと思った人は多いはず。さらに、制約から三乗が可能そうなので、もう一つ何かパラメーターに持って、DP[l][r][k]のようにできる。ただ、このkを、ターン数のように考えたのでは上手くいかない。

　解説動画では「貯金」という言葉を使っていた。（ツイートを見ると、保留とか予定調和DPという言葉で説明しているものも）

　（問題文中の）すぬけ君はどの飴でも取れるのだけど、区間DPに落とし込みたいなら、今考えている区間の飴を取るようにする他なく、だとすると、他の箇所の飴を取る権利はDPの区間がその場所に来るまで貯めておく……というのは結構自然ですね。

　なんか用語があった方が記憶に残りそうなので、「予定調和DP」という言葉で覚えておくことにしたい。

（解説動画を見たところ、Fはちょっと厳しそうだったので今解くのはやめます。主にFFTへの理解が浅いことが原因です……。勉強しないと。）