judge.u-aizu.ac.jp 島の数がnで橋の数がn-1の連結なグラフなのでサイクルが存在しないということが分かれば簡単な問題。次数が1の島には行かないで橋を撤去するだけ、次数が2以上の島にはいって帰ってきて橋を撤去する、という時間を合計してから次数が1の…

judge.u-aizu.ac.jp 街（この問題ではスタート地点および汚れた床）の間の距離を求めるのにBFSしないといけないので面倒だが、それさえやってしまえばTSPを書くだけの問題。TSPについては停止条件でスタート地点に戻る必要がない点について注意が必要。 実装…

judge.u-aizu.ac.jp 鉄道の最小コストを計算する問題。駅数が少ないのでワーシャル・フロイド法が使える。まず、会社ごとに各駅間の最短経路をワーシャル・フロイド法で計算し、対応する運賃も計算する。次に、各駅間の運賃を全会社の運賃の最小運賃として初…

judge.u-aizu.ac.jp 久しぶりの競プロになってしまった。リハビリがてら、解法が簡単だけれど実装するのが面倒で放っておいた問題を解いた。 幅優先探索をするだけの問題だが、左右の足ごとに距離を持つことを実装している途中で失念して、その他ゴールの処…

judge.u-aizu.ac.jp 再び最短路問題の典型問題を解いている。速度のあるDijkstra法の問題。書くだけの問題だが、保持すべき状態数が多かったり（速度と直前の辺）して実装に単純に時間がかかったりバグを仕込んだりして1時間くらいかかった。いつものことだ…

judge.u-aizu.ac.jp 引き続き最短経路問題の復習をしている。いよいよ典型問題と言うのは無理があるかもしれないが、各頂点に状態があるダイクストラ法の問題。 この問題はそれぞれの冷凍施設で何分冷凍するかというのが問題になるが、ゴールで残り時間が0秒…

judge.u-aizu.ac.jp 引き続き、最短経路問題の典型題を解いて練習している。各頂点が状態を持っている場合のダイクストラ法の問題を解いた。ビットで状態を持つような問題もあると思うが、今回は単純に残りチケット枚数だった。ビットの実装は苦手というか慣…

atcoder.jp リハビリとして今日は最短経路問題の、アルゴリズムを実装するだけの簡単な典型問題を解きたかった。実装が正しいかチェックするためにオンラインジャッジが出来る問題を探したが、本当に実装するだけのよう問題を見るけるのは逆に難しく、少し変…