AOJ 1176 Planning Rolling Blackouts (ICPC Domestic 2011 E)
AOJ 1140 Cleaning Robot (ICPC Domestic 2005 F)
AOJ 1182 Railway Connection (ICPC Domestic 2012 D)
鉄道の最小コストを計算する問題。駅数が少ないのでワーシャル・フロイド法が使える。まず、会社ごとに各駅間の最短経路をワーシャル・フロイド法で計算し、対応する運賃も計算する。次に、各駅間の運賃を全会社の運賃の最小運賃として初期化して、ワーシャル・フロイド法で全駅間の最小運賃を計算する。
ワーシャル・フロイド法が使えるのでバグを作りにくいと思ったが、なぜか通らなくて一晩寝かせた。翌朝にデバッグをしようとしたときにサンプルケースの3個目があっていないことに気づいた。おそらく昨日もあっていなかったのだが、なぜかスルーしていた。元のコードの問題点は、同じ会社で同じ駅間に二つの路線があることを想定していなかったことだった。これを修正してAC。
通らなかった版の実装は40分くらい（それでも遅いが・・・）だった。サンプルケースの答えはちゃんと確認すべきですね・・・。
AOJ 1150 Cliff Climbing (ICPC Domestic 2007 D)
久しぶりの競プロになってしまった。リハビリがてら、解法が簡単だけれど実装するのが面倒で放っておいた問題を解いた。
幅優先探索をするだけの問題だが、左右の足ごとに距離を持つことを実装している途中で失念して、その他ゴールの処理などのバグもあって1時間近くかかってしまった。
Codeforces Round #550 (Div. 3)
簡単な問題の速解きといった感じの問題セットで、Div. 3としては理想的なんじゃないかと勝手に思った。アルゴリズムというよりもプログラミングの問題だった。
Eを飛ばしてFを解いた時点で40分程度残っていて、立ち回りとしては悪くなかっただけにE問題が解けなかったのが勿体無かった。あとで見直したところ、一文字タイポしていたことが原因だった。かなり悲しい。
とはいえ、かなり非効率的な実装をしていたことが時間がかかってバグを埋め込んだ原因だった。いつも言っていることだがコードを書き始める前に効率の良いコードがかけないか考える時間をちゃんと取りたい。取りたいのだがコンテスト中だと焦ってしまう。
今回の結果でレートが1600を超えて青色になった。Div. 3がunratedになるので（僕はunratedのコンテストにに参加するほど元気がないので）最後のDiv. 3だったと思うと、やはりE問題が解けなかったことが勿体無かった。
AtCoderのパフォーマンスを見ても、今の力では次の1900を超えるのが難しいと思う。最近は時間がなくて全く練習できていないのだが、頑張っていきたい。
Codeforces Round #549 (Div. 2)
明らかに難しくないD問題を落とした。まだ見直していないので、原因がわかったら更新する。
しかし本質的な敗因はB問題に時間をかけてしまったことだった。最初に嘘解法を思いついてしまったせいで1WAをしたうえで時間を使ってしまった。こういうのは本当によくないので、考察時間をきちんととることを意識したい。
エクサウィザーズ 2019
C問題に異常に時間がかかってしまった。確かに言われてみれば二分探索問題でしかないので、これが思いつかなかったのは反省したい。
僕の解法は想定解法とは違って、O(Q)で走る。詠唱を逆順に読んでいき、左端と右端についてこの段階でこれより左・右にあるゴーレムは最終的に落下するというインデックスを持つようにする。これは各詠唱についてO(1)で更新できるのでO(Q)で走る。説明が面倒になったのでコードを読んでほしい。
解法自体は悪くないが、如何せん時間がかかりすぎた。ひとつの例について成否の判定ができるものは二分探索を考える、というのはセオリーだと思うので見落とさないようにしたい。
