TopCoder SRM 524 Div 1
なんだか参加記録書くのも、参加するのも久しぶりな気がするSRM.
あと2〜3ヶ月でRating 2200超えたいなあと思いつつ問題演習をしていく所存。
今回はDarseinさんと同部屋。
赤のいない平和な部屋だった。
Result
245.20 / Opened / Unopened
1撃墜1ミス
126位 2027 -> 2056
へぼい。
Medium LongestSequence
問題
数列C[i]が与えられる。
C[i]の各項について、
- C[i]が正なら、連続する任意のC[i]項が正
- C[i]が負なら、連続する任意の-C[i]項が負
という制約をつける。
この制約を全て満たす数列のうち、長さが最大のものを答えよ。
無限に長い数列が作れる場合、-1を、
数列が作れない場合は0を返せ。
制約条件
- 1000≦C[i]≦1000
Cの項数≦50
試行錯誤
え、これやばくない……まったく方針が立たない。
とりあえずサンプル1が何故そうなるのかはわかった。
n=4の場合で矛盾する。
{-7,11}のサンプルが何故そうなるのか全然わからない。
実際に制約を満たす数列を作りたいが作れない。
16個だと作れて17個だとどうして作れないんだろう。
ずーっと1時間考えつづけて時間切れorz
Challenge Phase
n=3忘れの人がいたので落とそうとする。1秒差で別の人に落とされる。
もう一人いた。そいつは落とせた。
もう一人いた、と思ったらChallenge失敗。nで無理だったら1とn-1にわけて再帰していた。
System Test
250通った。うーんorz