概要
コンテストページ : https://atcoder.jp/contests/agc039
当核問題 : https://atcoder.jp/contests/agc039/tasks/agc039_a
解説
問題文
文字列 が与えられます。
を 回繰り返してできる文字列を とします。
の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで のどの隣り合う 文字も相異なるようにするとき、 必要な操作の回数の最小値を求めてください。 – 引用 AGC039-a
コンテスト中の解法
「やるだけ問題」と言われる、問題文の内容を忠実にコードに落とし込む系列の問題です。(「やるだけ問題」ってカテゴリあんまり好きじゃない)
ケースに対する場合分けをひたすら考えて、コードに落とし込みました。メモがあると捗ります、おすすめです。
自分が場合分けした項目は以下の4つです。
- 文字数1(N==1)の場合(example:”a”)
- すべての文字が同じ場合(example:”aaaaa”)
- 両端が一致していない場合(example:”AtCoder”)
- 両端が一致している場合(example:”AtCoderA”)
考えてみれば1,2の場合は一緒にしてもいいことが分かります。(両方 s.length * (K/2) が解となる)
当時の自分はこの解に気づかず、何やら複雑な処理をこねこねしています。(反省)
3.両端が一致していない場合
この場合は 左から順に同じ文字が二回続いた回数を記録する ことで解を求められます。
解は 記録した回数 * k となります。
4.両端が一致している場合
3の処理の結果を用います。
両端一致の文字数を数え、割り切れる場合は (3の処理によって)記録した回数 * k + (K-1) が解となります。
提出コード : https://atcoder.jp/contests/agc039/submissions/7865790
感想
ACが出た当初はすごく喜んでいたが、冷静になって評価をすると無駄が多い。
今回はバグを埋め込んでいなかったため良かったが、冗長なコードとロジックはバグを埋め込みやすい。端的に、そして簡潔に書き上げたいものです。
約4ヶ月ぶりの緑タッチチャレンジチャンス。緑にさせてくれ。
