Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/779-42fb2e29
この記事にトラックバックする(FC2ブログユーザー)

Another Regional Contest (NWERC 2009) (この記事を編集する[管理者用])

2009年11月14日16時から5時間,10問.
[ Link ]

寝坊して45分遅れぐらいで参戦.
なんとかGとJ以外の8問解いた.
GはAcceptが0で,JはAcceptが1なので,まぁまぁかな.
GとJを除くと,簡単めな問題が多いかな.

Aは与えられた数字を使ってできる素数の数を求める問題.全部作ってチェックするだけ.
Bはノードに文字列が付与された完全2分木が与えられる.枝を張りかえてノード数を減らす問題.
適当にハッシュで判定しようとして上手くハッシュ作れなくてWAもらった.
愚直に判定やるとノード数最大50000でO(n^2)になっちゃうので駄目っぽいと思ってたんだけど,1秒台で通った.
Cは連続する部分列でdで割り切れるものの数を求める問題.前SPOJか何かで解いた記憶がある.たぶんこのブログの何処かに書いてる.
Dはフラクタル.2次元幾何+再帰.実装問題.
EはDP.どっち向きの車が次に進むかが決まっていたら,到着順に,進めるようになったら即座に進むのが最適.
最後にどちらの側の車が走ったか,両側の車があとどれぐらい残っているか,でDPすれば良い.
領域量O(n^2),計算量O(n^3).
FもDP.O(n).適当にルートを決めてやると,ルートから計算すると上手くいく.
Gはわからん.
Hはシミュレーション.6角座標を問題文に書かれている通りに数字を埋めていけばよい.
てか,カタンって,数字は中心から並べていくけど,資源の配置は並べ方違うのではなかったっけ…?
Iは幾何.点が与えられるので,それを頂点となる単純な多角形を作ってくださいという問題.
上をなぞって,その後下をなぞって凸包を作る方法があるけど,それの上だけなぞって,後は右から使わなかった点を全て追加していく感じで解いた.
Jはヨーロッパリージョンではお馴染みのワームホールの問題.単純にダイクストラしてTLEもらった.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/779-42fb2e29
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。