TopCoder SRM 524 Div 1

なんだか参加記録書くのも、参加するのも久しぶりな気がするSRM.
あと2〜3ヶ月でRating 2200超えたいなあと思いつつ問題演習をしていく所存。


今回はDarseinさんと同部屋。
赤のいない平和な部屋だった。

Result

245.20 / Opened / Unopened
1撃墜1ミス
126位 2027 -> 2056


へぼい。

Easy MagicDiamonds

問題

n個のダイヤを輸送する。
一度に輸送できるダイヤの数は、素数個以外の好きな数である。
最低何回の輸送が必要か、答えよ。

制約条件

n≦10^12

試行錯誤

合成数だったら1回で輸送できる。
そうじゃなかったら……?
1回では無理だが、1個とn-1個に分けて2回で運べる。


あ、n=3のときだけ3回かかる。
素因数分解するだけ。書いた。
何回か見直しして、計算時間とかも大丈夫そうなのでサブミット。

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