2010-02-08 - TopCoderの学習のお時間

Level	タイトル	試合中	あとで	ひとこと
DIV1 250	TheQuestionsAndAnswersDivOne	WA 35min	済	場合の数は得意な方のはずなのに大混乱
DIV1 500	TheFansAndMeetingsDivOne	WA 37min	済	intオーバーフローと定数倍最適化
DIV1 1000	TheCitiesAndRoadsDivOne	UnOpened	-

Coding
- 250
  - とりあえず全部調べたら9^9だけど計算量が不安
  - 場合の数で出せそうなので考える
  - が焦ってしまってグダグダ。間違った回答がサンプル通っちゃってそのまま提出してしまった
- 500
  - ん、DP…でいいのか？　計算量40*40*40*1600=約1億になるけど…
  - ええいもう時間がない書いてしまえ
  - なんか係数があってないみたいでサンプルの答えが合わない
  - 250から2項係数のコードを持ってきて割り算してみたら合った。ここで残り20秒、大きいケースでTLEしそうだけどもういいや提出
Challenge
- 500落とされた。これは予想通り
- 250も落とされてしまった
- 250を探索しているコードでTLEが狙えたかもしれないが-25が怖すぎる
System Test
- みてるだけ

ベースラインに押し戻され。

250は、落ち着いている状況ではあり得ないような勘違いでした。SRMは3問（実質2問）しかないからやけに緊張してしまう。

500は、250から持ってきた2項係数を計算するコードがint型のままだったので、40C20とかきたらオーバーフローしちゃいます。これは残り20秒じゃしょうがない。

あとやっぱり定数倍最適化しないとTLEしてました。

サンプルはよく読みましょう

Level	タイトル	試合中	あとで	ひとこと
DIV1 250	Inequalities	AC 10min	-	やるだけ、ほどよい作業量
DIV1 500	NumberPyramids	Compiled 66min	済	DPなのはすぐ分かったがあと一歩が
DIV1 1000	TheContest	UnOpened	-	誰も正解してない

Coding
- 250
  - 最高1000までということは、全部調べりゃいい
  - 整数しか考えないものと思い込んで、-1〜1001まで1刻みで調べていてサンプルが通らず焦る
  - サンプルをよく読んで実数の範囲と理解
  - というわけで0.5刻みで調べるとサンプル通ったので提出
- 500
  - 高さ>20 ならばすぐ return 0; で良いのと、一番下の桁に着目して2項係数を重みとするナップザック的DPを解けばよいのはすぐわかった
  - 一桁の数しか入れられないものと思い込んで愚直にDP書くとサンプルが合わない
  - サンプルをよく読んで、10以上も入れて良いことを把握
  - とすると計算量がbaseLength*top*topになってダメだ
  - ずっと考えたが効率の良い方法がわからず
  - 手持ちぶさたになったので、端からではなく係数の大きい真ん中から調べていくコードを書いて、「おお確かに数倍は速くなる」とかやってた。どうしようもない。
  - 後でうまく書けている人のコードを見るとシンプルで感激
Challenge
- 250でどう見ても間違ったことやってる人がいたのだけどチャレンジしてみたら失敗
- よーく読むと、どうして間違ってるのにたまたま通っちゃったのかわかった！
- と思った瞬間他の人に落とされた…
System Test
- 250は通った

最低でも半分より上には入らないと厳しいね。