Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年02月18日11時から.

Assignment

問題が,250-450-1000.
そして,この部屋は関西部屋ですか…?

EASY

01からなる列が与えられる.
それをB進数で解釈したら,ageになる.
Bを求める問題.Bは正の実数.
答えが存在しない,もしくは,複数存在するならそれを指摘する.

問題文読まずに,バイナリサーチ特攻.
expected -1とか-2とか言うのはなんだ?
-1は解なし,-2は複数ある場合か….
適当に修正,サブミット.
さあ,ちゃんとテストしようか….
"00001"みたいに,頭に零ついてても良いのかー!
age==1 かつ str=="1" を複数解の条件にしちゃったよ….
頭の零削ろう….
他に間違いはない?
ん?
age==1 で 最小の桁が1 で他に1があったら-1なんじゃ….
0進数って返してるよ,自分馬鹿.
答えがEPSより小さい時-1にしよう….
リサブミット.
さて,もう大丈夫だよな….
一応色々試してみる….
age=1, "10001"で1e-4ぐらいの値が返ってくる!
1e-4の4乗は0ですね…orz
2回目リサブミット.

MEDIUM

ボールに点数が付いている.
各箱にC個ボールが入っている.
各箱に入っているボールの点数は最初同じ点数で纏められている.
ランダムに2つのボールを取り出して,スワップする作業をS回行う.
各箱に入っているボール点数の期待値はいくら?

DP?
良く考えてないけど,期待値なんだから,毎回スワップした後の,各箱のボールの期待値を覚えて置いて,その値のボールが全部入っていると思って続きをやればよさそう.
E[A+B]=E[A]+E[B]は偉大なのだ.
やってみる.
1回スワップするときですら答えあわねぇ…orz
取り出し方の組み合わせの計算間違ってるよ!ってのに気付くのに時間掛かった.
サンプル通った.
サブミット.
これは大丈夫じゃないかな…450点だし.

HARD

ノード数100以下の有向グラフで,ノード1から2に移動したい.
ただし,1本だけ破壊された枝があって,それは,その枝の始点まで行かないとわからない.
さて,最悪ケースを想定して,最小時間で移動するとしたら,その時間は?

問題読み間違えて,最初手間取った.
うーん,普通にDPするだけじゃない?
無意味に,手間取る….
サンプル通るぞい….
合ってる気がするんだけど,1000はこんなに簡単なわけは….
でも,皆サブミットしてるし簡単なのかも,駄目もとで出しておこう.
サブミット.

Challenge

250はみんな落とす!
狙うぞー.
結果: マイナス25pt…,なにやってるの?orz

System tests

Hard落ちる.やっぱりかー.でも皆は通してるな…,そんなに難しくはないのかな.後で要復習.
同じ部屋で赤くなった人はおめでとうございます.
これで日本の赤コーダー15人とか…,凄いなー.
ターゲット2人とかおかしい.

Easyは全体で40人強しか通ってない.
SRM300台のEasy問題を思い出させてくれるトリッキーさで,とても面白かった.
かくいう自分も,強い人に,君のEasy,配列の範囲外にアクセスしてるよ,って言われた.
たぶん,システムにそういうケース無かっただけで,偶然落ちなかった予感. (2010-02-18 13:50追記 そういうケースあったけどうまく例外飛ばなかった模様)

2010-02-18 14:20追記

超強い人のwritterより

原因がわかったw v->uの辺が壊れてる→v->w->vと戻ってきた→v->u使えるw とかいう現象が起きてたorz

自分がHard落ちたのこれだ!(たぶん)

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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