judge.u-aizu.ac.jp 時間を逆から辿り、連結であれば最小全域木を構成して、状態を保存する。ただし、遡る過程で連結でなくなった場合には状態をリセットする。 連結でなくなったときに建設を止めるというところの認識を間違っていて、後々連結になったら建…

judge.u-aizu.ac.jp まず本を読み終わる時間を最短にするには一人目が所要時間の長い順に本を読み、二人目の子供は二冊目から同様に読めば良い。一人目が一冊目を読む間に、二人目が二冊目以降を読み終わらない場合は最適性は明らか。全て読み終わったあとに…

judge.u-aizu.ac.jp 実装するだけなのだが、次数が1の場合に来た道を戻る処理を書いていないことに気づかずにデバッグに時間をかけてしまった。こういうのは本当に良くないので反省したい。 judge.u-aizu.ac.jp

atcoder.jp 開始直後にたまたまTwitterを見ていて、ABCの形式が変わっていたことを知った。Ratedになったので久々に参加した。 問題は速解きという感じで難しいものはなかった。最近のABCはあんまり典型的なアルゴリズムを使うような問題もないので、特にICP…

judge.u-aizu.ac.jp AOJ-ICPCで500点までの問題のICPC国内予選過去問は概ね解いたが、バグも多いし時間もかかってしまっているので、この辺りの難易度で模擬国内やアジアの問題を少し解いていきたいと考えている。 この問題は一見すると幾何問題だが、実際に…

judge.u-aizu.ac.jp オーバーラップしている面積を全組み合わせについて計算して、重なりがある場合について面積を重みとして持つ辺でグラフを作れば、次数が高々2なので全探索で最小の表面積（重みの和が最大の連結部分グラフ）を探せば良い。 幾何問題なの…

judge.u-aizu.ac.jp なぜかF問題だが、すごく簡単な問題があったので寝る前に解いた。ちょっとバグらせたので30分くらいかかったので何も言えないが、これはC問題くらいでも良い気がする。Python使って解いたので、他の言語だと色々考えないといけないことが…

judge.u-aizu.ac.jp 問題を見てすぐにDPっぽいということが分かる。使用した最小金額を値として持つということが自然なので、すぐに思いつく解法としては[店の数]×[500円の数]×[小銭]が考えられる。なので通るかと思い、実装した。色々とバグらせてしまい、…

judge.u-aizu.ac.jp まず問題を見た時点でDPだということが分かる。そして、制約がなので、がくらいになることがわかる。 想定解法はおそらく場合分けしてDPと全探索の二通りの解法で書くんだろうなと予想していて、実際に講評の解法の1個目はそうなっていた…

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

judge.u-aizu.ac.jp ブロックが樹上になっていることがポイントで、一番下から再帰的にブロックの配置を表した木を作り、重心も再帰的に計算する。 このくらいの実装量になると自分がバグらせることは目に見えていたので出来るだけ書き始める前に構成を決め…

judge.u-aizu.ac.jp 基礎的な幾何問題。問題文を読んで簡単そうだと思ったのだが、実装に無限に時間をかけてしまった上に凄くバグらせた。実装を始める前に構成は軽く考えていたのだが、考えていなかったコーナーケースへの対応などでどんどん酷いコードにな…

judge.u-aizu.ac.jp E問題だが、かなりシンプルなメモ化再帰で解ける問題。状態数は任意のサイズの長方形なので、だいたいくらいになって間に合う。実装は30分ほどでできていたのだが、境界をミスしていてデバッグに時間がかかり40分強でAC。 ICPCのD、E問題…

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

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

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