パナソニックプログラミングコンテスト2020

　ABC形式の企業コンテスト。Dまでの四完と、成績は今一つでしたが、writerのりんごさんらしさが出た印象に残る問題でした。

コンテストへのリンク
コンテスト後のツイート

B - Bishop

　H=1やW=1がコーナーケースの問題。TopCoderっぽい問題な気がします。

C - Sqrt Inequality

　誤差に気を付けましょう、という教育的な問題。幾何の問題だと、誤差に気を付けるのが重要かつ本質になることが結構あります。そういうとき対応できるように、普段から気を付けておかねば。

D - String Equivalence

　DFSで列挙する。最近のABCで何度か出題されていますね。

　私は、「再帰を使って列挙する」のは、結構難しいと思っています。

　DPで遷移を考えるのと本質的には同じかもしれませんが、大抵のDPでは、部分を切り取って考えれば良いのに対して、再帰では全体の構造を頭に入れておかないと混乱しやすい、というような。

　（あくまで印象です。本質的にはこの二つは同じはず）

E - Three Substrings

　貪欲したくなる気持ちを抑えて全探索する問題。

　コンテスト中も、全探索をしなくちゃいけないはず、とは気付いたのですが、実装に困って解けませんでした。

公式解説に書いてある方法をやるだけなのですが、意外と実装に苦労する問題ではないかと。

F - Fractal Shortest Path

　一応コンテスト後に自力でACしたけど、かなり時間がかかって大変だった……。

　

　「避けなければならないブロックは高々一つ」ということに気付けたら、後は二点の間にブロックがあるかどうかを大きい方から調べていく、という感じで解けるけど、この方針が立っても、実際に実装するのはかなり大変だと思う。

　AGCっぽい問題に見えるので、なんでABCで出題したんだろう？　というのはちょっと不思議。確かに、発想すべき点は「避けなければならないブロックは高々一つ」くらいなので、発想より実装よりの問題、ということなのかな……。