1つの問題に7時間+αかけて、やっとAC (agc029_c)

問題

beta.atcoder.jp

私の提出

beta.atcoder.jp

時間がかかった理由

  • 自作したテストケースが間違っていた
    • 提供されているテストケースは数が少ないし答えも2, 3なので、間違ったコードでも通りうる
    • 案の定、提出後にWA
    • 自作するが、それが間違っていて、コードもそれに引き寄せられて間違っていく

高速化の試行錯誤

  • mapをunordered_mapに変えてみたりもしたが、範囲eraseが使えなくなる
  • 速度は速くなる
  • メモリ使用量は多くなる
  • 適材適所
  • 最終的にmapに戻した

計算速度も求められる

  • Aは109なのでvector a(109) で全状態を持つのは無理
  • mapを使うが、現在の文字列の長さのところまで a で埋めるfor文は遅い
    • 注目している桁の位置のみ状態を書き込むことで高速化
    • 例:

f:id:peroon:20181216171349j:plain

数字との違い

  • 数字だと繰り上がった後には0が残るが、辞書式では違う

f:id:peroon:20181216172216j:plain

インクリメンタルな開発

  • こんなに時間がかかった理由は、
    • 間違ったテストケースを作成
    • コードをそれに合わせる
    • 提出してWA
    • テストケースを足す(しかし以前のが間違っている)
    • 以下ループの泥沼
  • 大切なのは、絶対間違っていないテストケースを作ること
    • 普段、提出してWAだとすぐDropboxにUPされているテストケースに頼っていたが、それはよくない
  • 正しいテストケースを作るには、問題の正しい理解が必要

テストケースを提供

[in]
9
1 4 2 3 7 3 4 2 1

[out]
3

学び

  • vectorでは持ちきれない状態をmapで解決した

必要な技術

  • 状況理解
  • テストケースの自作
  • 高速化としてのmap
  • mapの範囲削除
  • 二分探索

公式の解説動画

www.youtube.com