タグ

2008年11月17日のブックマーク (1件)

  • Google Code Jam World Finals: コンテスト: ymatsux 雑記帳

    GCJ World Finals の問題セットの紹介,及び私自身の結果です. まずは総評.World Finals だけあって,非常に難しい問題セットでした.しかし,どの問題も,鋭い気づきや深い考察が必要とされる一方で,必要とされる知識は基的(難しいものでも MST や最大フロー程度)な問題ばかりで,良問揃いだったと思います.恐らく,秘蔵の問題を最後に放出した,といったところなのでしょう.今回参加していない方も一考の価値がある問題セットだと思います. 次に問題セットの分析. まず Small から.A, B, C はどれも自明なアルゴリズムで,しかも単純な実装で解ける問題でした.その分配点も非常に低くなっていますが.D は,最初の森と二番目の森をつなぐルートは最短路なら何でも良いという,若干の考察が必要です.E は基的には自明な DP ですが,何らかの高速化が必要だったようです.いずれ