TCO12 Round 2B 参加記

5月だというのにやけに冷え込んでいたので暖房つけて参加したTopCoderOpen2012 AlgorithmのRound 2Bの参加記です。
まず結果をば

順位	得点	レーティング
512nd	171.43	1432 → 1497
300	550	900	Challenge
171.43	未提出	未提出	0

という感じです。点が変則で、easy問題がいつもより難化している回でした。
確実に1問通すのが目標だったので、とりあえずは目標達成です、はい。

開始前

特に眠たくなかったけど、サッパリしたかったのでシャワった。
お茶を用意して、EclipseCoderからArena行って、ついったーでどーでもいいこと呟いて待機

開始

当然、目下の敵である300を開く

ゆっくり読む
なるほど、N個の部分に分かれたダーツ盤があると
各部分には1〜Nの点が高々1回ずつ割り振られていると
中には点数がいくつなのか分からない部分があると
P点以上取るために投げるべき最小回数Kを答えよ、と
ん？点数が分からない場所に投げたらどう計算するのか書いてないな
サンプル読む
あー
分からない場所に当てたら、最悪のケース（つまり最も得点が低くなるような）で計算して、それでもなおP点以上とれるか、っていうことかー
もっとサンプル読む
電卓使いながらなんとなく分かってくる
点が書かれていない個所全部に1回ずつ当てたら、確実に、書かれていない点数の合計点が手に入るんだな
ということは
サンプルを見るに
点数が書かれているものの中で最大のところに連続でK回当てる場合か、書かれていない場所の個数をXとして、X回投げてその合計値を得るのを何回か繰り返す場合の最小値が答えかなー
前者は簡単に求まるからー
めんどいのは後者だなー
P点を超えるのは投げすぎだから、X*合計値がPを超えないまで投げるかー
すると残りの（P-X*合計値）の分の得点は、書かれていない点数を小さい方から加算していってこれを超える最小のkが、残りの投擲回数だなー
書く
サンプル合わない
あ、いけねー
細々と修正する
最後のサンプルが合わない
あれ？何で求まらんのだ？
あー
(P-X*合計値）の分の得点を得るために、書かれていない点数にだけ投げるのを考えていたけど、このときに、書かれている点数の最大のところに連続して投げた方が得する場合があるのかー
書く
サンプル通る
結構時間使ったなー
300 Submitted

ちょっと部屋内の状態を確認する
うわ、おぺらさん流石に解くの速いなー
っていうかみんな解くの速いなー（部屋内で真ん中より下の方だった）
これは550頑張るかー

550読む
？
T-WもW-Tも最大化するの？
よくわかんない
サンプル見る
あー、なんか大きい本ばっかり選んでるなー
小さい本を選んでいるサンプルを見つける
！？どーいうこと？
考えてもやっぱりよく分からない
Division Summaryを見てみる
550解けてる人が結構いる
自分の位置は600位台
むむぅ
サンプルが理解できないので投げやりになってくる
グダって終了

休憩フェーズ

ついったでどーでも(ry

チャレンジフェーズ

チャレンジという名のただの1人ソース観賞会
いつもに比べてJavaの人が多かったので1人ずつ読む
お、300似た解き方してる
なにこれ？
550これDPしてんの？
終了

感想

300を解けたことが結構嬉しかったり
でも550に手も足もでなかったのが、まだまだ差を感じるところでした
解法を考える以前に、題意が読み取れないというね
easyを安定して解けるまでは、easyに多めに時間を割いていこうと思います
次第にmediumに回す時間が増えてくれると思うので、それが実感できたらmed用の練習をしようかなと思っています