ARC122-Aの備忘録

問題

atcoder.jp

要点

• DPに強くなりたい
• AtCoder Libraryは偉大

すぐに考えついたこと

• 普通にO(n²)は無理
• それぞれの数字に付く+の数と-の数出すと良さそう?
• 思いつかないので要素全て1で手書き全列挙してパターン探る(DPを頭から外す)

列挙した

• N = 7まで手書き全列挙した
• -の数が鍵となりそうなので数える

数えた

• N=2 {1}
• N=3 {1, 1}
• N=4 {2, 1, 2}
• N=5 {3, 2, 2, 3}
• N=6 {5, 3, 4, 3, 5}

• N=7 {8, 5, 6, 6, 5, 8}

• 左右対象(当然)で予想が立てられそう

  • N=2の時，数列は{1}
  • N=3の時，数列は{1, 1}
  • N=n(>3)の時，数列のn/2までの要素は同じindexであるN=n-1の要素とN=n-2の要素の和
• "良い式"の数はFibonacci数?
• とりあえずこれを実装する

実装した

• どうやってもO(n²)になる
• この手法では無理そう
• よくみたら-を表す数列の要素もFibonacci数と関連しそう
  • 具体的には左からi番目のマイナスの数が欲しい時は，N-i番目のFibonacci数とi番目のFibonacci数の積になりそう
    • ここに気づくのに1時間55分
    • 数列をよくみて気づくべきだった
    • (証明したい)

実装した(2)

• 実装途中でコンテスト終了
• mod 10¹⁰+7 に翻弄された
• 最後の3つのテストケースが通らない
• 他の人の回答見ていたらAtCoder Libraryのなかにmodintという自動でmod取ってくれる便利なものがあるらしい

実装した(3)

• 通った
• 解説読んだ DPをさくっと思いつけるようになりたい

まとめ

• DPは偉大
• AtCoder Libraryは偉大
• 経験積もう

gist - ARC122-A