問題
私の提出
時間がかかった理由
- 自作したテストケースが間違っていた
- 提供されているテストケースは数が少ないし答えも2, 3なので、間違ったコードでも通りうる
- 案の定、提出後にWA
- 自作するが、それが間違っていて、コードもそれに引き寄せられて間違っていく
高速化の試行錯誤
- mapをunordered_mapに変えてみたりもしたが、範囲eraseが使えなくなる
- 速度は速くなる
- メモリ使用量は多くなる
- 適材適所
- 最終的にmapに戻した
計算速度も求められる
- Aは109なのでvector a(109) で全状態を持つのは無理
- mapを使うが、現在の文字列の長さのところまで a で埋めるfor文は遅い
- 注目している桁の位置のみ状態を書き込むことで高速化
- 例：
数字との違い
- 数字だと繰り上がった後には0が残るが、辞書式では違う
インクリメンタルな開発
- こんなに時間がかかった理由は、
- 間違ったテストケースを作成
- コードをそれに合わせる
- 提出してWA
- テストケースを足す（しかし以前のが間違っている）
- 以下ループの泥沼
- 大切なのは、絶対間違っていないテストケースを作ること
- 普段、提出してWAだとすぐDropboxにUPされているテストケースに頼っていたが、それはよくない
- 正しいテストケースを作るには、問題の正しい理解が必要
テストケースを提供
[in]
9
1 4 2 3 7 3 4 2 1
[out]
3
学び
必要な技術
- 状況理解
- テストケースの自作
- 高速化としてのmap
- mapの範囲削除
- 二分探索
公式の解説動画
https://www.youtube.com/watch?v=mRWp91Nkn8Awww.youtube.com
