次のアルファベット
CODE FESTIVAL 2016 qualA-C "次のアルファベット"
アイデアは比較的すぐに浮かびましたが,またしても沼りました.
提出コード
考察
辞書順ということで,先頭の文字ほど若い文字に置き換えたいです.
もっと言うと先頭の文字ほど'a'に置き換えたい.
よって,先頭から順に見ていってKの残り回数的に'a'に置き換えることができれば置き換える.'a'に置き換えられなければそのままにしておく.
という操作をしていけばよいです.
なぜなら,'a'に置き換えられないということはそれ以上操作をしても辞書順で大きくなっていってしまうためです.
例えば,入力が
xyz 2
のときは,'x'は何もいじらないほうがよくて,'y'を'a'に置き換えるのが最適です.
'x'を'a'に置き換えるためには3回の操作が必要で,なので足りません.
つまりどれだけ'x'を置き換えようが今の"xyz"より辞書順で大きくなります.
ただ,一連の操作を行った後,が余る可能性があります.
例えば,入力が
xyz 100
のとき,"aaa"にするのに6回の操作を要し,94回分余ります.
これに対しては末尾の文字を置き換えるのが最適なので,余った回数を26で割った剰余分の操作を末尾に適用させればOKです.
沼
ここで私が沼った原因を紹介します.
例えば,入力が
axyz 26
のとき,6回分の操作で"aaaa"にして,残りの20回分を末尾に回すのが最適です.
しかし私のコードでは,先頭の'a'を'a'にする(操作を26回行う)ことで,”axyz”にしてしまっていました.
'a'を見たらスキップというコードの追加により無事AC.
感想
今回の沼は自分でも気づけたはずですが,知り合いに指摘されてなんとかACしました.
まだまだ罠に気づく能力は低そうです.