AGC021

README

AGC021過去問感想

• A問題は解いてる最中は直感的な方法（O(logN), 底は10）で行けるかどうかが不安だった（正しさの証明ができなかった）ので、復習も兼ねて桁DPで解いた。
  • 明らかにオーバーキルではある。
  • 桁DPのコツである、以下のコツを再確認できた。
    • i から i+1 への遷移
    • dp[0][0] のみを起点とし、 dp[0][1] はある種無効な値で初期化
    • lessフラグ0からはlesフラグ0, 1両方への遷移があるが、lessフラグ1からはlessフラグ1のみの遷移しかない