ABC 401-500/ABC438B - Substring 2 - 競技プログラミング用 知識集積所

---

問題

ABC438B

必要知識

A問題レベルのものは省略

• 全探索※
• 二重ループ※

考え方

B問題で最小値を求めろと来たら、考えるべきは全探索※。
SがN文字、TがM文字あるので、可能性がある候補はS内にN-M+1ヶ所ある。
そのそれぞれについて、「そこをTに合わせるには何回操作が必要か」を全て求め、最小値を答えればよい。

さて、「そこをTに合わせるには何回操作が必要か」は、今度は「その場合の各桁ごとの必要操作数」を求めて合計すればいい。
これは、Sの該当位置の数とTの該当位置の数を見比べればよい。
Sの方が大きい場合や等しい場合は、Sの数からTの数を引けばよく、char型同士の引き算でちゃんとint型で答えが出る。
Tの方が大きい場合は、一度数をループさせる都合上、Sの数に10を足してからTの数を引けばよい。
これはif分岐を使って実装してもいいし、常に10を足す方で計算した後に%10してもよい。

解答例

解答例

注意点

可能性がある候補数を間違えない。

うっかりN-Mヶ所としないように。
forループの終了条件を間違えると、最後の1つの処理が抜けてしまう。

別解