Saving The Universe Again

Google Code Jam 2018 の予選、A問題の考察です。あくまで個人的な解法の紹介ですので、正確を期すためには、主催者の解説ページを参照してください。

Code Jam は今年からフォーマットが一新されました。過去の形式に慣れていた人ほど戸惑ったのではないでしょうか。私もその一人です。練習ラウンドで慣らしはしましたが、いまだに慣れないです。サーバ側にも、新システムゆえかトラブルがあったようです。1回戦までに直っているといいのですが……。

問題

異星人からの襲来を受けました。彼らの攻撃プログラムは、’C’ と ‘S’ から成るコマンド文字列で構成されます。’C’ は「チャージ」、現在の攻撃力を倍加させます(攻撃力の初期値は1です)。’S’ は「シュート」、現在の攻撃力をダメージとして加えます。コマンドのハックに成功したあなたは、隣り合った文字を自由に交換することができますが、その回数は最小限にしたいです。コマンド文字列 P が与えられたとき、合計ダメージを D 以下にするためには最低で何回の交換が必要でしょうか?

考察

予選のA問題ということで、比較的簡単な部類に入る問題でしたが、手応えはいかがでしたか。

Code Jam では同じ問題の中にも Small と Large の2種類の設定がありますが、ここでは Large を想定して考察を進めます。

IMPOSSIBLE

この問題では、どうやっても合計ダメージを D 以下にできないケースは “IMPOSSIBLE” と答えなければなりません。まず、このケースを先に判定しましょう。

交換の回数はひとまず置いておいて、合計ダメージを理論上最小にする操作は、すべての ‘S’ を左端に寄せることです。このときの合計ダメージは、’S’ の個数に等しくなります。

つまり、与えられた文字列に含まれる ‘S’ の個数が D よりも大きければ “IMPOSSIBLE” です。そうでなければ、少なくともすべての ‘S’ を左に寄せることで D 以下にできることが、この考察でわかりました。

問題のカギ

この問題は、「1回の交換で、好きな ‘S’ を選んでそのダメージを半減できる」ということに気付くかどうかがポイントです。なぜそう考えることができるのかを説明します。

まず、隣り合った文字を自由に交換できるとありますが、”CC” や “SS” を交換することに意味がないことはすぐにわかります。また、”SC” を交換しても必ずダメージを増やすことになってしまい、損なだけです。となると、選ぶべきは “CS” の部分のみとなります。ここを交換したとき、’S’ の持つダメージは半減します。

では、”CSSS” のようなパターンはどうでしょうか。この右端の ‘S’ のダメージを減らすのは一見高くつくように見えますが、そうではありません。試しにこの右端の ‘S’ を左に3回移動させてみましょう。出来上がる文字列は “SCSS” ですね。この文字列は、左端の ‘S’ を1回移動させたのとまったく同じであることにお気づきでしょうか。つまり、どのような連続する ‘S’ にも必ず左端となるものが存在しますから、それを常に選択することで、「どの位置に存在する ‘S’ も1回の交換でダメージを半減できる」とみなすことができるのです。

結論

1回の交換で好きな ‘S’ を選んでそのダメージを半減できると考えれば、最も効率の良い方法は、その時点で最大のダメージを与えている ‘S’ を見つけ出してそれを半減するというサイクルを、合計ダメージが D 以下になるまで繰り返すことです。これはあらかじめ ‘S’ 個別のダメージを配列に格納しておき、毎回ソートしながら先頭の値を半減していくことで実現できます。文字列 P の長さはたかだか 30 ですから、この方法で十分間に合います。

ソフトウェアの設計・実装がうまく行かなくてお困りではありませんか? 組込屋にお任せください。リモート案件は、常駐の半額でお受けしています。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)