Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年09月09日20時02分から.

Assignment

ちょっと忙しかったので,数分遅れで参加.
250-500-900の変則セット.HARDが簡単なのかな?

EASY

神様しか答えの知らない2択問題がある.答えはAかB.
n人の人が神様に答えを聞いた.
そのn人の人から神様から聞いた答えを聞いた.その結果が与えられる.
神様が嘘を付いた人数と,n人の人が嘘を言った人数が与えられる.
答えはAかBか判断できないか,両方矛盾してるかを求める問題.
nは100万以下.

問題文読みにくい….
うーん….
読めた…?
サイズが微妙に小さいから….
神様から正しい答えを聞いた人の中で,嘘を付いた人数の数でループして,それぞれの答えになりうるか調べる.
がりがり.
書けた.実行.AとBが逆だった.
直してサブミット.

MEDIUM

50個以下のクエリが与えられる.
クエリを発注した人の名前と,各クエリにかかる時間が与えられる.
1度に1個のクエリしかこなすことができず,各人の待ち時間とは,自分の発注したクエリが全部終了するまでの時間.
全員の待ち時間の平均値が最小になるような順番でクエリをこなす.複数あるならその順番の中からランダムで1個選ぶ.
各クエリの終了時間の平均値を求める問題.

ふんふん.こっちはまだ問題読みやすい.
所要時間の短いクエリからやれば良いよね.最初のほうが待ってる人の人数多いんだから.
というより,同じ人のクエリは連続してやるのが良いはずなので,1個のでかいクエリだと思えばよい.
適当に,ソートして順番に処理するのだ.
同じ所要時間なら,どっちか先かわからないので,平均値を求めるんだから,期待値的には半分遅くなると思えばよい.
同じ人が発注したクエリが2個以上あれば,その中で実行順番は任意だから,期待値的には自分の他クエリの所要時間の半分だけ遅くなると思えばよい….
あれ.
かなり簡単になるなぁ.
まとめると…
 クエリiの始まる時間の期待値 = 自分より所要時間の短い人が発注したクエリの所要時間の和 + 自分と同じ所要時間の人が発注したのクエリの所要時間の和/2
でいいじゃん.
かきかき.
サンプルあった.提出.

HARD

1列にn個(nは16以下)のプリンターが並んでいる.各プリンターの間の距離が与えられている.
各プリンターには内部的に数字が記録されてて,起動してから1秒ごとに1増やすか減らすかできる.
起動したときに,数字がいくらになったら印刷するかというのを設定できる.
最初プリンターは全部が起動していなくて,あるプリンターの前にいる.
n個の印刷したい数字が与えられたとき,それを印刷するまでの最小時間を求める問題.
1つのプリンターは1回しか印刷できない.

16と言う数字を見て2^16のDPの予感…,ってそんな簡単な訳ないよな….
問題を読む.
え,いや,めちゃくちゃ単純なDPじゃないの?
…いや,各プリンターがどの数字を印刷できるか任意に指定できるんだ,簡単じゃない.
うーん….
設定したプリンタと印刷した数字で状態数が4^16は無理だなぁ….
回る順番を固定すれば,二分探索+最大流でn種類全部印刷できるかどうか判定できるよね….
回る順番が16!あるのが問題なんだってば…,え?
あれ,16!もないのでは….だって,通り過ぎたプリンタは取り敢えず起動してしまえばいいのだから.
少ない気がする.
全パターン試しちゃえ.
がりがり.
サンプル通る.
取り敢えず適当に作った最大ケースを入れてみる.1200ms….微妙….
まぁ,なんとかなるんではないか.サブミット.
さて,いろいろ試してみようか….
ランダム最大を入れてみる.4ms.えw
何か間違えてないか?
いや,無意識に入れた枝刈りが効いてるっぽい….
最悪ケースは何だろうか,こんな感じだろうか,いれてみる.1730ms.やばい….
取り敢えず,枝刈りを消して実行してみたらいいんじゃないの.それで2s超えなければ問題ない.
実行….TLE.2s超える….
怖い…,怖いよ….
でも,落ちるケースも作れないし,改良法が思いつかないので放置.
終了1分前に,実は最悪ケースと思ってたのは全然最悪じゃないのでは…,ということに気づく.
取り敢えず,新・最悪ケースを入れてみる.1790ms….あれ,ほとんど変わらないだと.

Challenge

落しどころがわからないから見てるだけー.
と思ったら結構ぼろぼろ落ちてるなぁ….
途中で用事のためArena落として抜ける.

System tests

どうやらちょっとシステムテストがトラブったらしいが,帰ってきたら普通に終わってた.
なんか全部通ってたみたい.
900ptのシステムテストは意外と余裕でした…,が,落ちるケースがありそうで怖い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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