7K12 blog

猫でも分かるアルゴリズム解説

DDCC2020 D - Digit Sum Replace

f:id:tkr987:20210516191459p:plain

https://atcoder.jp/contests/ddcc2020-qual/submissions/22659513

  • 少なくとも(桁数-1)回だけ桁を減らす必要がある
  • 桁は減らないが数字が小さくなる変換もある、条件は2桁の数字  10a+b について  10 \leq a + b

f:id:tkr987:20210516193321p:plain

適当にシミュレーションしてみると、2桁の数字が小さいとき桁が下がる変換になる傾向にあり、2桁の数字が大きいとき桁は減らないが数字が減る変換になる傾向がある。正確な条件は

  • 2桁の数字  10a+b 10 \leq a + b のとき桁は減らないが数字  a + b は小さくなる
  • 2桁の数字  10a+b a + b \lt 10 のとき桁が減り  a + b = c となる  c に数字が置き換わる

少なくとも(桁数-1)回は桁を減らす「→」の変換が必要で、桁は減らないが  a+b が減る「」の変換も何回か必要ということを意識するのが本質かもしれない。

」の変換を観察すると-9だけ減ることが分かり(ぇ)

99(9+9)18(1+8)→9

46(4+6)10(1+0)→1

などのシミュレーションから「」の回数は  ceil((a+b) / 9) - 1 で求まる。

あとは「」と「→」の合計回数を出力すればACできる。

 

感想: 「」の変換天才すぎて無理