AtCoder Beginner Contest 151
今回は A から C まで。ランクも下がった。
どちらかというと今回は解けたという話でなく、どうして解けなかったか？という話になる。 普段は競技プログラミングで点が取れなかった話は振り返ってみても役に立たないので書かないが、 今回は教訓を見出したので自戒を込めてブログ記事にしている。
で、
その解けなかったのは D で、与えられた迷路に対して適当な始点と終点を与えて最短パスを最長にする、というような問題だった。
問題サイズは割と小さかったので、総当りで始点を設定して BFS で最も遠い点を出せばいいかと考えた。 ただ実行時間はなるべく短くしたかったので、始点からは次の条件を満たすものを除外することにした。
- 上下の点が通行可能
- 左右の点が通行可能
要するに通路のあたるような点は始点終点から外そうとした。 これは割ともっともらしい。最短パスが最長になる始点終点はなにかしら端のほうになりそうだ。
ということで実装をして提出してみたのだが、最後の１ケースだけ WA になるという残念な結果になってしまった。 コンテスト時間中はなにかしら問題文で見落とした箇所があったのかとか、特殊なケースがあったりするのか、など考えていたが、 なんのことはない、上に述べた除外している箇所を外すだけでうまく動いたのだった。
これに気付いた後で、そのケースを考えてみると次のようなものがあった。
■■■■■ ■□□□■ ■□■□■ ■□□□■ ■■□■■ ■□□□■ ■□■□■ ■□□□■ ■■■■■
このような８の字型の迷路だと、８の上側の通路と下側の通路を指定すると最短経路が最長になる。
なにが悪かったか？
明らかに余計な条件を加えたのがよろしくなかった。
高速化の鉄則として、
まず正しく動くものをつくり、それから最適化する
というのがある。これこそなにより自分が気を付けなければいけなかったことで、競技プログラミングであってもこの鉄則に従わなかったのは申し訳がたたない。
「高速化する」というのは競技プログラミングの上でももっともらしく聞こえるが、まず正解を出すのが最優先だ。 そもそも速くなるケースは限られるという時点で、最も時間がかかるテストケースが投げられてくる競技プログラミングへの解答としては不適切であったし、今回のようにパッと思いつかないようなレアケースに足を引っ張られることもある。
教訓としては、総当りでいくと決めたら変に高速化を目指さない、ということになるか。TLE になってから考えればよいし、焼け石に水的な高速化はおそらく間違いの場合が多い。
