Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM491 DIV1 参加記録 (この記事を編集する[管理者用])

2010年12月19日01時02分 (JST) から.

Assignment

250-600-900の変則セット.
こういうセットは600からやるか,900からやるか迷って困る.まぁ普通に600からやろう.
自分以外に赤のいない部屋.落ち目になるとこういう部屋によく配置される気がする.
フロリダ (アメリカ) のホテルから参加.TopCoderと同じタイムゾーン.
モバイルノートPCの解像度が低くてやりにくいので,始まる前にやりやすいウインドウの配置を研究した.

EASY

6面対のサイコロの作り方のパターン数を求める問題.回転して重なるなら同じとみなす.
各面にはそれぞれ異なる1~Nの数字を書き,向かい合う面の数字の和は全部一定で,それはK以上でなければならない.
Nは1000以下,Kは2000以下.

ちょ,狐の次郎さんとか問題文に書いてあるのですが….
ま,まぁ,解かなきゃ.
取り敢えず,サイズが小さいから,向かい合う面の数字は全パターンの試そうかな.
で,後は,それを達成する数字の組の数を求めて,コンビネーション足していけば終わり.
それを達成する数字の組は…,図を描いて考える.
うーん,場合分け面倒じゃないか.
違う違う!
このサイズなら全部ループ回して探しても問題ないじゃん!
ループ回す.
合わない….
あ,数字0も使えるようになってた….
修正.サンプル通った.サブミット.

MEDIUM

長さ50以下の文字列がN個 (16以下) 与えられる.文字列はアルファベット小文字のみからなる.
各文字列の中の文字を適当に入れ替えても良い.
与えられた文字列でTrieを作ったときの最小ノード数を求める問題.

Nが16とかどう見ても2^NのDPっぽい.
でも,どうするのかパッとは,わからないなぁ.
50 * 2^16の配列でもつくってDP…,じゃないな,50はどの文字から使っても良いからダメ.
まぁ,取り敢えず,2^Nなんだから,文字列を分離して部分問題にするわけよね.
あ,わかった…かも?
取り敢えず,各部分問題は,全部に共通する文字をgreedyにおいて行って,後はどの部分問題に分けるか試せば良いよね.
あ,O(N^3)なのか,それで16なのか.
greedyに置いていくのは…,全部に共通する文字数だけ最初に求めておけば数式一発で書けそう.
書く.
書いた.
ケアレスミス直して,サンプル通して,サブミット.

HARD

それぞれN枚 (50以下) のカードの山AとBが与えられる.
それぞれのカードには1以上100以下の実数が書かれている.
K回,次の手順を行う.
 それぞれの山から1枚ずつカードを選び,その数字をSとTとして,
  X := X + max(S,T)
  Y := Y + min(S,T)
このとき,X/Yの最大値を求める問題.

うーん.
取り敢えず,比なので取り敢えず2分探索でしょう.
 max(S,T) - 答え min(S,T)
を得られる点数として,最終的に正にできるかどうかの判定問題になる.
うーん.
取り敢えず,大きい物同士,小さい物同士でいいのでは?
てか,そうじゃなかったら,解けない気がするし,取り敢えずそれで.
サンプルは通るなぁ.通るようにサンプル作られてる気がするけど.
サブミット.
さて,妥当性を検証しよう.
ランダムに入れ替えて,それより大きい答えが出てこなければ良さそう.
やってみる.
ランダムに入れ替えても全部同じ答えになる.
なんと!?
2分探索の範囲を初期化してなかった….
あー,普通に反例あるなぁ.
さて,どう解くのやら.
きっとフローか何か.
ってか,普通に単なる最小費用流じゃないか….
!?
ノートPCにライブラリないorz
それは,ちょっと厳しい….
無理でした.

Challenge

900でgreedyの人がいたので適当に落とす.
600で,何故か長さも状態に入れてて50倍遅い人がいたのでTLEで3人落とす.
そうこうしてるうちに自分の900が落とされる.当然.

System tests

なんかエラーってなかなか結果が出なかった.
900が荒ぶって,なんかほとんど落ちていた.なんでだろう.doubleコストの最小費用流だからかな?
チャレンジで結構稼げたのでまあまあいい順位.
それと,チャレンジの最後2分程度が正常に機能しなかった部屋があったみたいで,Ratedにするかどうか議論されたが,Ratedになった.
ターゲットに復帰.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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