ICPC 2007年国内予選問題D

問題はこちら:http://icpc.logos.ic.i.u-tokyo.ac.jp/icpc2007/contest/D_ja.html
崖登り。コンテスト中は問題見た瞬間にすぐ解ける問題とわかり
「ああ、書くだけだね」と完全に丸投げしてしまったけど、
終わってみると結構4問解けているチームが多い。
これ全員がダイクストラ(もしくはベルマンフォードあたり)書いたのかなあ。コンテストのレベル上がったなあとその時は思っていたけど、必ずしもそうでないことに気づきました。

この問題はもちろん最短路問題だけど、一般的な最短路問題より少し簡単で実は深さ優先探索でも解ける。その場合は例えば以下のようなアルゴリズムでよいのではないか。

グラフ的に行けるところへ距離を加算しながら再帰していって、ある(位置,足)にきたときの始点からの距離が前に到達した時より長かったら、それ以上探索する必要がないから枝狩り

ポイントは各ステップにおける距離(すべりやすさ)が高々9までということ。同じ点を2回通らずに別の点まで移動した場合、距離の上限はW*H*2*9となる。

よって、距離の更新が行われる回数は各点についてW*H*2*9回で抑えられるため、最終的に計算量は
(W*H*2)*(W*H*2*9)*9で、最大でも10億くらい。国内予選なら間に合う時間なんじゃないかな。

振り返ってみれば、結局ダイクストラを使わないと解けない問題は、知る限り国内予選では一度も出ていないわけで、「特別知識がなくても解ける」日本の問題のクオリティは高いなあと改めて思ったり。

ICPC国内予選

毎年この日は7号館(の一部)が盛り上がりますね。お祭りの日。この日くらい日記書きます。
結果は、負けたけれどチームメイトがとても強いこともあって通過。dmとkeeすごい。
解けた問題はABCDFで、5問解いた他の3チームも同じなんじゃないかな。Eを最後にまわさない理由ないし。

Unknownおめでとう。アジア予選では負けません。
TalesOfCodersもおめでとう。ここはものすごく強いチームなのに去年まで予選の罠にかかっていたので一緒に通過できて非常に嬉しい。
地底練習会のチームでワンツースリーフィニッシュでしたね。アジア予選に向けてすぐ練習が始まるので、がんばりましょう。

ICPC 2005年国内予選問題D

馬車券問題。ちょっと気になったので解きなおし。
基本的な方針はこれまでいろいろなところで議論されているものと同じだけど(DAG上最短路)
問題は生成されたグラフのトポロジカルソートをどうやって得るか。

以下の方法でうまくいくと昨日になってはじめて気づきました。

続きを読む

ICPC終了

世界大会出場決定コンテストに敗退。今年度のWorld Final出場の夢は消えました。
最終的に時間で負けたわけですが、現時点で実力差は多少実感していたので、この時間差にはなんとなく納得してしまったりします。

ともあれkitsune-のみなさまおめでとうございます。それにしても強い。間違いなく最強クラスのコーダーを、二人がアルゴリズムでサポートする体制には死角がほとんど見当たらない。振り返ってみれば、練習会でもこちらが順位では上になったことはほとんどなかったですね。世界大会で代わりにきれいな色のメダルを取ってきてくれることを期待しています。

我がMakegumiは、去年の国内予選8位、学内5位から、今年はアジア予選出場、海外派遣とかなりの躍進の年となりました。夏合宿などで上位チームと練習できたこともいい経験になりました。

最近は全体的にレベルが上がってきたせいか、簡単な問題だけでなく中程度の難度の問題も短時間で解くことが要求されているように感じるので、その点をふまえて練習していこうかとおもいます。

世界大会での活躍を祈りつつ、来年度にその実力を分けてもらえることを画策しながらあえてこの言葉を叫んでおきます。

きつねー。