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

---

問題

ABC407C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

ボタンAとボタンBで別々に考える。
Aは押した回数が桁数になるので、Sの文字数を調べればすぐにわかる。
難しいのはBの方で、以下のように考える。

例えば"53"の場合。
2つ目の数字が3であるということは、2回目にボタンAを押した後にボタンBを3回押すことになる。
ということは、2回目にボタンAを押す瞬間には、1つめの数字は2になっていなければならない。
これは5-3=2という計算で出せる。

例えば"35"の場合。
2つ目の数字が5であるということは、2回目にボタンAを押した後にボタンBを5回押すことになる。
ということは、2回目にボタンAを押す瞬間には、1つめの数字は8になっていなければならない。
これは3-5=-2が負になるので、さらに+10して8という計算で出せる。

つまり、次の数字から前の数字を引いてから負の数なら+10する、という計算で各ボタンAの間に何回ボタンBを押すかを求められる。
if分岐で出してもいいし、10足してから%10してもよい。
また、int（未作成）型に直して引かなくても、char型のまま引き算してしまって問題ない。

それらの合計を、ボタンAを押す回数に足せばおしまい。

解答例

解答例

注意点

最後の1回分に注意。

次の数を参照する都合上、最後の1つもそのままやると範囲外アクセスでエラーする。
if分岐で処理してもよいが、番兵法（未作成）を使って最後に'0'をくっつけておくのもよい。

別解

倍数化アルゴリズムを使用する。

例えば"2025"の場合。
最後にボタンAを押した後にボタンBを5回押す必要がある。
3回目にボタンAを押した後にボタンBを合計で「10で割って2余る」かつ「5回以上」である回数、つまり12回押す必要がある。
2回目にボタンAを押した後にボタンBを合計で「10で割って0余る」かつ「12回以上」である回数、つまり20回押す必要がある。
1回目にボタンAを押した後にボタンBを合計で「10で割って2余る」かつ「20回以上」である回数、つまり22回押す必要がある。
ボタンAの4回と合わせて答えは26回、という手順で出すこともできる。
解答例

1ずつ加算しながらボタンAのタイミングを逆算する

上の解のさらに亜種。
倍数化アルゴリズムを使うまでもなく、1ずつ加算していけば適切な余りになるタイミングが見つかる。
最大で50万文字*9回なので、余裕で間に合う。
解答例