UTPC2011

UTPC2011

個人戦5時間という、久々にハードな戦いに行ってきました。
美少女セットでした。

• -

A. プログラミングコンテスト

• やるだけだったので、コンパイルもせずに投げてみて無事AC。
• それでも提出は遅めで、驚愕した。

B. (iwi)

• やるだけだったけど、一応サンプルは試した。
• サンプル通ったので、投げてAC。

C. [ [iwi] ]

• かつて研究室の教授から似た問題を出されたなぁと思い出した。
• 適当に実装したら、「iwiを含む」という条件を見落としててWA。
• このときに全探索でも良いことに気付いたけど、面倒なので同じ方針で直した。

D. 停止問題

• 状態数多くないし、適当に幅優先すれば良さそう。
• if文をいっぱい書いてると間違ってる気がしてならない。
• 珍しく間違ってなくて、1発で通った

E. ファーストアクセプタンス

• 問題見た瞬間、何分で解けるか分かるとかぱないなぁ…。
• というか、問題設定的に考えて、全部解けるとかぱないなぁ…。

• まぁ、DPですよね。って事で組んで提出した。

F. 全域木

• ノードN個の全域木からN+1個とかN+2個とかの全域木が生成できる予感…。
• はしたけど、数え漏らしたり重複したりしそうで怖かったので飛ばした。

G. プログラミングコンテストチャレンジブック

• ソートして上6個で2つ三角形作れるか試せば良くね？と思ったらダメだった。

• しばらく後で考え直したら、普通に反例が見つかった。
• 連続する3個を取り出して、2個作るパターンもあるっぽいので、加えたら通った。

K. 巡回セールスマン問題

• これ、ほとんどのノードが入次数も出次数も1じゃね？
• 1直線に並んだノードを1つの辺に圧縮すればグラフがだいぶ小さくなりそう。
• そしたらダイクストラで余裕な予感。

• これは！と思って、Gで1WA出した後から、ほぼずっとこれを書いていた。
• が、書き上げられるほどの実力はなかった。
• というか、優先度付きキューの使い方を間違ってたので、旅に出る必要がありそう。

• -

問題文も面白かったですが、問題自体もとても面白いものでした。
時間の半分以上をKに費やした挙句に通らず、
もっと色んな問題に挑むべきだったかなーという気もしますが、
楽しめたので後悔はしていません。
運営の皆さま、および参加された皆さま、お疲れさまでした！