競プロ日記

1つ挟んだけどしっかりやり遂げた。


コード
https://yukicoder.me/submissions/306799


前の記事で言った通り、ダイクストラ法そのものは関数として実装していた。
典型的なダイクストラ法の問題(頂点とコストだけ)しか知らないので、これをどうやってダイクストラ法で解くのか割と悩んだ。
解説見ても頂点とコスト毎に最短距離を求めるダイクストラ法としか書かれておらず、分かりやすいコードを見つけるのに苦労した。
見てなるほど、取り得るコスト全てを探索して、それぞれの最短距離を保存していくのか。
イメージとしては、グラフの頂点それぞれにとり得る総コストと同じだけ頂点が連なっている感じだろうか。
拡張ダイクストラ法を調べていて、どこかで3次元で上から順に求めていく、というようなことが書かれていた気がするが、今になってなるほどと思う。
しかし、この方法だと計算量がかなり多くなるような気がするがどこまでやれるのだろうか。
とり得るコストの量が多くなってくるとゴール手前はかなりループするんじゃないかと思うのだが。
処理自体は大小関係の比較と配列への代入と、かなり早い処理しかないから大丈夫なのだろうか。
計算量のオーダーについても考えていかないとまずそうだと最近感じた覚えがあるが、これもその一種だろうか。
単純に考えれば最短距離[頂点][コスト]全てに代入される可能性があるのだからO(n^2)だろうか？
だがどう考えても町やコストじゃなく道の数に比例して計算量は増えるだろうからよく分からない。
要勉強。
どちらにしても今回の制約内ではまず問題ないだろうということは分かるからとりあえず良しとしよう。


次にコードのお話。
以前自力で作成したプログラムの道情報は、いわゆる隣接行列というもので、無駄が多いらしい。
隣接リスト形式に書き換えることで無駄が減るのはもちろん、スタック・キューへの適応もより自然になった気がする。
そもそもグラフについての知識がなさすぎたな。
そんなこんなで蟻本見ながら自分が分かりやすいようにプログラムを完成させた。
なんでも乗ってる蟻本しゅごい。

で、ダイクストラ法の関数を実装している時点でうすうす気づいていたが、こんな典型的なダイクストラ法の関数作って意味ないだろうと。
なんならオブジェクト指向で形式さえあっていればどんなグラフでも返せる形にしている。
そんなことを考えながらとりあえず作った関数を改造していたのだが、関数作っておいてよかったとしみじみ感じた。
どこを変更してどこを拡張すればいいか、ということを考えたいのであって、素のダイクストラ法に対してリソースを使いたくないからだ。
ダイクストラ法の処理を何度も何度も書いていれば別かもしれないが、そんなことをする予定はないしもそもそれが無駄だろう。
おそらく与えるグラフの形式は毎回変わるので、オブジェクト指向云々は若干どうでもいい感じはする。

この改造したダイクストラ法のプログラムを作成してすぐ解けたか、というとそうではない。
大体答えが出るが、いくつかランタイムエラーが出ていた。
こういう場合、おそらく配列の範囲外参照だと当たりをつけているが、大体問題ないだろうと思っている。
さぁそうなった場合にどこを調べるか。
もちろん多少ややこしい処理をしているダイクストラ法の関数内だ。
グラフの頂点の数が小さいのかとか、判定の順番的にコストがオーバーする可能性があるのかとか、色々調べてみたが解決しない。
学生時代に研究で使って何も解決しなかったGDBまで使って調べると、なんとmain関数内でエラーが。
原因はグラフの要素数だった。
町の数を要素数とすべきところを、道の数を要素数としていた。
大体の場合、街の数より道の数の方が大きいので多くがACだったわけだ。
確かにREのテストケースは短いものが多かった。
似たような要素数のミスがあったABC017 D サプリメントのときは未だに問題が悪いと思っているが、この短期間に同じようなミスを繰り返すのは少し凹む。
要素数でミスしないようにするのはもちろんだが、テストケースが分かる場合、そのテストケースの傾向から間違いの検討をつけられる気がしなくもない。
これも1つの学びとして吸収していこう。
コンテスト本番ではサンプルだけから考えるのは少し厳しそうではあるが、学習段階では無駄に時間を取られずにすむかもしれない。




今年中は新しいアルゴリズムが必要な問題はもう解かない予定。
簡単なのはちょっとくらい解きたい気持ちはある。
年末だしゆっくりしたいところだけど普通にやることが多い。
何よりスマブラ練習しないといけない。
普通の格ゲーとあまりにも操作感が違ってかなり苦労している。
サタパでやらせてほしいなぁと思うけどCスティックないからだめだね。
それでは良いお年を。