Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年05月04日20時02分から.

Assignment

日本人いないかなぁ…,いないっぽいなぁ….
(もし居てたら超ごめんなさい)

EASY

n*mの映画の席のうち,横に並んで2人座りたい.
50個以下,既に人が座っている席が与えられるので,座り方のパターンの数を求める問題.
nとmは10億以下.

誰も座ってない列はm-1パターン.オーバーフローに注意.
既に人が座ってる席がある列は50列しか無いので,全部考える.
並んでk個空いていればk-1パターン座り方がある.
書くだけ.
がりがりがり.
サンプル通らない.あれ?
この問題は1-originだったんだけど,コード中に0-originで考えた式な部分がある…,酷い.
修正.サンプル通った.Submit.
なんかミスってるような気もするので,見直す.自分でテストケース作って試す.
大丈夫そうかな.次行こう.

MEDIUM

映画が20個以下あって,各映画に盛り上がる場所が1箇所ずつある.
最初のテンションは74で,1分ごとに1減る.
盛り上がる場所をみた瞬間,テンションが47上がる.
テンションが-0.5になったら寝て,もう起きない.
映画を見る順番を自由に選んで,完走できる映画数を最大化したい.
そのような映画の順番を求める問題.複数個解があるなら辞書順で最も速い問題を求める問題.

どう見てもビットDPです.
書くだけ過ぎる.
がりがりがり.
書いた.サンプル通る.
時間大丈夫か?
最大ケースを試す.普通に間に合う.
よし,サブミット.
ちょっとだけ,コードミスってないか見直す.OKっぽい.

HARD

2人の人A, Bに映画のレビューをしてもらうことになった.
2人とも,queueに映画を突っ込んで,1つずつ取り出してレビューする.
N本を最初にどっちかに割り振って,queueに突っ込む.
それぞれの人はqueueから取り出して,見終わったら,相手の人のqueueに突っ込む.(まだ相手の人がその映画のレビューをしてなければ)
新しく映画をqueueから取り出すとき,queueが空なら,もう終わったと判断して,終了する.(その後映画が突っ込まれてもレビューしない)
全部で最初の割り振り方は2^N通りあるけど,すべての映画が2人にレビューされるような最初の割り振り方の数を求める問題.
それぞれの人が,それぞれの映画を見るのにかかる時間が与えられる.それぞれ20分以下.
Nは47以下.

20分ってのがやたら小さい.これがポイントのハズ.
DPかなぁ…,500が典型的DPだったのに….
考える.わからん.


自分に割り振られた映画の時間の和を初期値として,相手に割り振られた映画を
 相手が見るのにかかる時間 - 自分が見るのにかかる時間
を足して行って,それが,マイナスに1回でもなれば駄目,みたいな感じ.
20*50=1000なのでO(1000*1000)でDPでいけるか?
いや,相手の分を忘れてる,O(1000^4)だ….
無理.
ある程度映画を均等に割り振ってしまえば,後はどう割り振ってもOKなので,枝刈りは効くような気がする.
やってみる.
書いた.
最初,相手が見終わった瞬間,渡された映画はその瞬間はqueueにまだ入ってないと思ってたんだけど,そうじゃなかった.
それを修正したらサンプルは通った.
映画数30のランダムケースを試す.0.25秒….うわー,無理くさい.
映画数47のランダムケース.bad allocとTLEが交互に出てくる.
どうすれば良いのか,考えろ!
思いつきませんでした.

Challenge

今日は間違えるような問題ないだろう….
250のオーバーフローだけ調べるか.
先に取られた.
誰もチャレンジしない.やっぱり平和だなー.
1000点問題の他の人の解法でも見よう.
と思ったら,他の部屋は結構殺伐としている!?
500が結構落ちてる.どういうことだ?
しかし,チャレンジケースも分からない.終了.

System tests

500落ちないか怖いな…何か見逃してないかな….
と思ってたら通った.良かった.
後々考えると,確かに500はコーナーケースが色々あったり,映画は完走した映画数で判定とか,辞書順とかミスり易い要素もあったのかもしれない.
自分の部屋の500も結構システムテストで落ちてた.
勿体無いといえば勿体無いけど,チャレンジで点数稼ぐんじゃなくて,あくまで問題の点数で僕は勝負するんだ…とか言ってみる.
1000は2人同時に考えずに,1人ずつ考えるとO(1000^2)とかで行けるのか!…ってなんでそれでいいのかまだ理解できてない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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