ICPC2019国内予選にwe regret to inform you...というチームで参加しました。3完86位という結果で完全に実力不足ということで納得していたのですが、ホスト校枠の関係で85位の慶応のチームがアジアに行く見込みらしくてwe regret to inform you...という結果…

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

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

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

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

judge.u-aizu.ac.jp ABCの問題は実装練習として進めていくとして、問題としては少し簡単なので問題を解く力が鈍らないようにICPCの問題もたまに解き進めていこうと思う。 10種類のアルファベットを全探索しても通りで、式中のアルファベットの個数は100個以…

judge.u-aizu.ac.jp 単純にメモ化再帰した。コーディングの方針がほぼ確定しているとはいえ、20分くらいで解けたので僕としては及第点としたい。しかしループの範囲を間違えて1WAした。こういうのが良くない。 judge.u-aizu.ac.jp

judge.u-aizu.ac.jp 簡単そうな問題だったので30分くらいで早く実装する練習をしようと思ったが、渦巻きの図を書くことに異常に手間取ってしまった。もう少しバグを生まないように、しっかり考えて描かないといけないと常に思っているのだが、実際にやるのは…

judge.u-aizu.ac.jp ICPCを埋めていく日です。 制約が小さいので、特に効率の良い解法があるわけではなさそうだと思って普通に探索をした。しかし、かなり明らかな枝刈りを見逃してTLEを出してしまった。それを直したら通ったが、実装としては非効率的なコー…

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

judge.u-aizu.ac.jp 基礎的な内容の復習をしながら、ICPCの問題を埋めることにした。AOJ-ICPCで適当な難易度の問題から埋めていこうと思ったら、去年のD問題だった。過去問として残しておいても良かったが、目についてしまったので解いた。 初めは賢く解く方…