TopCoder SRM413 DIV1

最近プログラミングコンテストばかりですが…。
いきなりのDIV1（一軍）。いろんな人の戦歴を見るに、一番簡単なやつだけ確実に解いてればyellow coderまでは行けそう（レーティングによって色分けして表示される）なので、まずはそのあたりを目標に。

• • -

んんん、変に考えすぎて解けるものを逃してしまった。
250点問題だけ確実に解いて、レーティング1230→1418に。やたら上がったな…。今回は難しめだったのかもしれない。500点問題の正解率が10%台とか。次回うまくやれたらyellow coderになれるかも。

250点問題

数列の問題ではあるけれど、図形で考えるとわかりやすかった。点（0, a0）を通る直線の傾きを増やしていって、全インデックスの地点で交差する傾きの値があるかを調べる。ちょこちょこミスをして結構時間かかってしまったけれど、落ち着いて解く。

500点問題

全部計算したら時間が足りない、かといって全部キャッシュしてたらメモリが足りない、適当なところを探ってね、という問題。だったのだけど、「もっといいアルゴリズムがあるはずだー」と間違った方向に考え込んでしまって時間切れ。なんか不満というか納得できないというか。他の人の解答を見ると、渡すパラメータによっては時間切れになるのが多そうで、案の定半数以上がシステムテストで落とされてた。チャレンジしてみときゃよかったかな。

1000点問題

問題文を読んだだけ。グラフか。しらみつぶしの解答はすぐ書けそうだけど、たぶんそれじゃあ駄目なんだろうなあ。