MemberSRM501

赤い人として挑んだ最初のSRM。

• -

250. FoxPlayingGame

問題：0に操作A(scoreAを足す)nA回と操作B(scoreBをかける)nB回を好きな順で行ってできる最大の数を求める。

• タイトルだけ見て、日本人writerなんだろうなぁ…とか思う。

• まぁ、操作Aと操作Bの残り回数でDPすれば良いよね　→　合わない
• そうか、最小値も持たなきゃだめか　→　合わない
  • バグってたんだと思われる

• ぐぬぬ…。

• ひょっとして、操作Aはまとめて行って良いんじゃね…？
• max(0≦i≦nB) scoreA*nA*pow(scoreB, i) で良いか。
• サンプル通ったので提出。迷走したなぁ…。

500. FoxAverageSequence

問題：0以上40以下の整数からなる数列で，A[i]は前までの値の平均以下かつ，A[i]>A[i+1]>A[i+2]が成り立つ場所が無いものの数を求める問題。

• 上限40なら5乗くらいはかけても良いのかな。
• DPするとしたら、必要な情報は「直前でA[i]>A[i+1]が成り立ってたか」と，「直前の値」と，「それまでの和」か。
• 式を立ててみると…あれ、5乗で行けそう。

• めずらしくDPなのにすぐ方針が立つも、ここからDPの苦手っぷりを発揮。
  • 具体的には分岐条件をミスったり，配列操作をミスったり。
  • 途中、方針違うんじゃないかと思ったレベルのハイパーデバッグタイム。
• 最悪ケースに影響しない枝刈りは入れない事にしてるので、実装は楽めだった。
• 40個の-1を試したら800msだったので、大丈夫だろうと踏んで提出。

Challenge Phase

• 250で場合分けゲーした人はミスがありそうなので、その辺を重点的に読む
  • DP勢は無視
• 「paramA>1000」を「paramA>1」と書いてしまったかわいそうなコードを見つけたので美味しく頂いた

• -

結果：AC / AC / -- ，+50, 584.13pt, 52位
レーティング：2308 -> 2347

レッドコーダーの自分が見納めだと思ってましたが、何故かレートを上げることが出来ました。
未だに気持ちは黄色中盤くらいなので、だんだん反動が怖くなってきつつあります。