Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

A Bangladeshi Contest (この記事を編集する[管理者用])

2009年12月19日17時から5時間,9問.
[ Link ]

徹夜明けにちょっとだけ仮眠取って寝起きで参加ってことで酷いことに….
一応問題数だけならTopタイの7問解いた.
そのうち問題別に記事作るけど,簡単に解いた問題解説.
nodchip先生の記事がわかりやすいので,そっちを見る方が良い.

Aはこの前TopCoderのMember SRMのbeta 2回目?か何かで出題されたのとほとんど同じ.
見ている枝のコストが空港の建設コストより小さい間クラスカルする.
空港の数を最小化だと思っててWAもらった.
Bはやるだけ.文字列操作.
Cは個人的には難しかった.というか今も想定解法理解していない.
負けるパターンはwikipedia: Wythoff's_gameの通りなんだけど,テストケースが多いのでそれを愚直に調べてTLE.
テストケースを最初に全部読み込んで,ソートして,Fenwick Tree使って数え上げるという荒業でAcceptもらった.
後で,nodchip先生の記事をちゃんと読む.
Dは書くだけ.
Eは問題文を読むのに手間取った.書くだけ.最初から縦横が同じ長さの個体がいると0,縦横別々に同じのが存在すると1,あたりがコーナーケースで気をつけるべき点か.
Gは2分探索 + rolling hashでO(N log N)で解ける.N=文字列の長さ.でもNは高々1000ということでN^2でも良いらしい.
最初に使えない文字を,1字1字別の文字に変換していくと,それは1回しか登場しなくて,使えないことになるので,実装が楽.
なぜか,答えは2以上じゃないといけないと思い込んでWAもらいまくった.
Iは行列べき乗.障害物がある場所まで行列べき乗して,障害物がある場所は別の行列をかける.そして,次の障害物までまた行列べき乗をかける.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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