アルゴリズム実技検定の電子書籍版を買ったので、最近読み進めています。

競プロ始めたての人向けの解説が多くて、すごく読みやすいです。

全探索とか、自分がわかってる部分はスラスラ読み進めて、問題のグラフ理論へ。

隣接行列の実装方法はわかっていたけど、隣接リストの実装はしたことが無かったので、隣接リストを使いながら、テキストに載っていた、PAST第3回のE問題を実装してみた。

問題リンク

頂点の値を書き換えていく問題。こういうのって、最後に全頂点の情報を出力するのかと思っていたけど、1回ずつ出力することに気づかずにエラー探しててちょっと時間かかってしまった。

この問題では頂点数が最大200だから初心者でも隣接行列か隣接リストが実装できれば解ける問題なんだろうけど、ABCとかでよく見る問題だと10^6くらいあったりするから、Pythonで解くにはもっと高速にしなければいけないのかな？って少し思った。

その後、テキストに書いてた次の問題も解いてみたけど、半分くらいWA出して原因もまだ掴めてないので今日は一旦諦めます。