Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年01月28日01時02分から.

Assignment

275-500-975という何とも中途半端な配点のセット.

EASY

1~Nまで (Nは1000以下) の数字が書かれたカードが1枚ずつあり,素数だと背景が赤,そうでなければ背景が青.
今,K枚 (50以下) のカードが,裏向きに置いてある.そのカードは左から小さい順に置いてあることが保証されている.
カードの色だけが与えられたとき,各カードに対して,特定できるならその数字を,できないなら-1を返す問題.

rngセットだ.
どうやるんだろう.
えっと,結構サイズが小さいな.
各カードに対して,そのカードがxであることがあるかどうかを全部判定しても問題なさそう.
で,それはgreedyで良いのでは?
そのカードから左に眺めていって,使える数字のうち最も大きいのを割り当てて可能かどうか.
同様に,右に眺めていって,使える数字のうち最も小さいのを割り当てていって可能かどうか,それぞれ判定.
いけるな.
結構めんどい,275だからか.書く.
サンプル通った.提出.

MEDIUM

N個 (50以下) の箱の中に1つだけハズレがある.
N*Nの{0, 1}行列が与えられる.
箱iを開けたとき,行列のi,j成分が1なら,箱jがハズレかどうかがわかる.
最適戦略を取ったとき,ハズレの箱を開けずに,ハズレの箱を特定できる確率を求める問題.

ほう….どうするんだろう.
rngセットの問題は,大抵最初はどうするんだろう,から始まるなぁ.
サンプルを眺めてみる.
結局,どの箱はハズレかわからないから,答えは,1 - 開けるべき箱の数 / 全部の箱の数 でいいんだな.
自分の情報が他の箱に入ってない場合は開けなければいけない.
いや,最後に残すのもありか.
どれを最後に残すか全パターン試してもいいな,それは.
うーん,あれ?
サンプル4って,0.875じゃないんじゃない?
1個だけ開ければ良いってことだよね?
1個で他の箱の情報を1個を除いて全部持ってる箱なんてないじゃないか.
え???
どういうことだ…?
??
????
??????
あ,わかったかも.わかった.
そうだそうだ,ハズレじゃないとわかった箱はノーリスクで開けられるんだ.で,その中にある情報もゲット出来る.
最初にワーシャルフロイドしよう….
それだと,基本的に,強連結成分分解してDAGに落としたときの入次数0のノードの数を求めるような感じ.(ダメ予備軍)
だけど,自分から枝が張られているようなノードの次数は絶対自分より小さいから,普通にgreedyに選ばべば良いじゃん.(ダメ)
ってことで,次数の大きい方から順番に箱を開けていけば良い.(ダメ)
書く.サンプル通る.提出.

HARD

H階 (10^9以下) に N層 (H以下) のエレベーターは何通り考えうるか,mod 1000000007で求める問題.
N層のエレベーターとは,N-1個の整数A[1]~A[N]で特徴付けられ,一番下の層がa階に止まっているとき,それぞれの層は
 a, a+A[1], a+A[2], ..., a+A[N]
階に止まっている.
また,一番下の層の止まる階が,決められており,その階に止まることで,全ての階に厳密に1つのエレベーターの層が止まることにならなくてはいけない.

取っ付きやすそうに見えるので,少し考える.
いろいろ考えると,小さいサイズに帰着させて解けそうな気がしてきたが,最初の印象ほど単純じゃないことに気づく.
時間もないし,適当に書いてみる.
一番面倒そうなサンプル「だけ」通る.
記念サブミット.
サマリー見ると,上位でも500をリサブミットしてる人が多くて不安になる.え,ハメなんかない問題だよね…?

Challenge

何もできず.HARDは落とされた.

System tests

MEDIUMが落ちる.
greedyでいいかどうか,怪しいと思いつつ提出した人が多かったみたいだけど,自分はgreedyで良いと確信していた.
よくよく考えればgreedyで良いわけがないのだが,なんでこんな勘違いをしたのか今となっては誰もわからない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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