SRM524

TopCoder

旅路の新幹線の中から更新。たまにはこんな日も良いですよね。

  • -

250. MagicDiamonds

問題：与えられた自然数nを、最小何個の合成数の和で表せるか求める

  • 合成数なら分解しなくて良いので答えは1
  • 素数だったら、1+(n-1) あたりに分解しておけば2個で表せるのでは
    • n=2 だったら 1+1
    • n>2 だったら (n-1)が偶数になるので2で割り切れる
  • しかし冷静に考えたら2は素数なので、3だけは1+1+1で表さないといけない
    • Challengeは高速に3を入力するゲームかなぁと、ぼんやり思った
  • まで考えたら後は良い気がしたので、適当に組んで提出した。

500. LongestSequence

問題：C[i]>0なら連続するC[i]項の和はすべて正、C[i]<0なら連続する-C[i]項の和はすべて負となるような数列のうち、長さ最大のものの長さを求める。

  • hosさんのXmasContestで似た問題を見たような気がする。
  • とりあえず、作る数列を{x1, x2, ..., xn}とでもする。
  • S(i) = x1 + ... + xi とする
    • このとき、隣接するk項の和は、S(i+k)-S(i)で表せる
    • これより、Cの各要素について、
      • C[i] > 0 : S(j+C[i])-S(j) > 0 より S(j+C[i]) > S(j)
      • C[i] < 0 : S(j-C[i])-S(j) < 0 より S(j-C[i]) < S(j)
    • が各jについて成り立つ必要がある
  • 数列の長さをnとして、S0, S1, ..., Snに対応するn+1個のノードを作る
  • S(i) < S(j) が成り立つ必要がある場所について、i->jの枝を張る
    • このグラフ上で巡回路があると、 S0 < S2 < ... < S0 のような矛盾が生じる
    • なければ各Sの大小関係が定まり、条件を満たす長さnの数列が作れる
  • この性質を利用して、数列が作れる最大の長さを求めれば良い
    • 長さ1から順に調べても間に合う気はしたけど、チキンなので2分探索した

Challenge Phase

  • "3"を高速に入力するゲームには敗北(´・ω・｀)
  • しかし、何故か"5"で落とせる人がいたので美味しくいただいた
  • -

結果：AC / AC / -- ，+50, 577.14pt, 19位
レーティング：2313 -> 2398


Div1で初めて20位以内に入り、レーティングも自己ベストを更新できました。
そろそろ500でDPが出て詰む日も近い気がするので、対策しておかねば…。