AOJバッキバキに噛み砕いた解説「足し算ゲーム」

はじめに

さるAOJの問題足し算ゲーム ( UTPC2009 E問題 ) につきまして。当局による解説はあるのですが、もうちょっと噛み砕いた解説を試みます。

…気付いてしまうと「なんじゃそれ」なんですが、そこまでの敷居もあるかなあ、ということで。

問題整理

問題文にも書かれていますが、これはとあるゲームにおける、双方最適な戦略を選んだうえでの、勝敗判定です。そのため、勝利/敗北条件の把握と、戦略の決定ができないと、プログラムを組むこともままなりません。

ということでゲームの内容を整理してみます。

• ゲームの進め方
  • ある数字 ( 1000桁以下、入力で与えられる ) から開始し、2人で交互に操作する
  • 自分の手番では、ある隣り合う2桁を選んで、その数を合計した数に置き換える
    例えば、数字が1234 の時に、100,10の位を選んだ場合、"23" が 2+3=5 で "5" に変わって 154 になる。
    • 選んだ2桁の合計が10を超えるかどうかで、ちょっと状況が違うことに注意が必要
    • 例えば、4649 で 100,10の位を選んだ場合、6+4=10 なので "64"が"10"に変わって 4109 これは桁数自体は変わってない
• 勝利/敗北条件
  • 自分の手番の時、上で説明した「置き換える」操作ができないと負け
  • つまり、自分の手番で既に数字が1桁になっていたら負け。相手に1桁の数字を渡せれば勝ち
• 戦略
  • 自分の手番でどの2桁を選ぶか、選択の余地がある。そこが戦略
  • でもどう選べばbest??

戦略考察

方針

というわけで、bestの戦略を考えてみるわけですが…。
結論から言うと、どの戦略を選んでも ( 自分の手番でどの2桁を選んでも )、勝敗にはまあああったく影響しません。どんなに頑張っても、あるいは逆にどんなに手を抜いても、勝敗は変わらないのです。

なぜかというと、そういうことにしないと面倒で問題が解けないからまあカラクリがあるわけですが、幾つかのケースで勝敗が実際にどう決まるかシミュレートしてみます。「例示は理解の試金石」と言いますし。

単純なケース

まず、10,100,1000 といった、「1の後に0だけが続く」数で見てみましょう。なぜ単純なのかというと、「どんな選び方をしても同じ数字ができる」からです。

先頭の2桁 "10" は "1" に。先頭以外の2桁 "00" は "0" に。結局、0 の桁が1桁だけ減っていくという進行になります。そのため、勝敗を決定する要素は桁数のみ。桁数の偶奇によって先手・後手どちらが勝つかが決まるわけです。

このことから、「桁数」というのが重要なファクターであることが分かります。
もうちょっと考えてみると、別に 100… という数でなくても、操作の度に順調に桁が減っていくのであれば、同じように桁数だけで勝敗が決まるということも分かります。
例えば 1230 という数であれば、途中をどう選んでも合計は決して10を超えません。つまり、1度の操作で必ず桁が減りますから「偶数桁：先手勝ち」と判断できます。

次のステップへ向けちょっと考慮時間

さてそれでは桁数だけ考えれば良いのでしょうか…? といっても、そうは問屋が卸しません。操作を行って合計が10を超える場合には、数字は変化するものの桁数が変わらない ( 減らない ) からです。
しかも、いつ「10を超える操作」になるか、どの桁を選ぶかによって変わりますから分かりません。さあ困りました。

ちょっとここで気分を変えて、先ほどの1230の図を見直してみましょう。

…。あることに気付くでしょうか??

…実は、どんな操作をしても、必ず 6 で決着しています。
いえ、それどころか、どの段階でも各桁の合計は 6 です。これは偶然でしょうか…? ( 反語 )

いえ、これはある意味アタリマエです。途中、2つの桁を足し合わせるというのは小計をとっているに過ぎず、どういう足し方をしようと合計には影響しませんから。

しかしこの「アタリマエ」というのは馬鹿にできません。どのような操作を選ぼうとも、あるいは操作を進める前と後いつでも同じ結果になる数、こういうのを「不変量」と言うのですが、重要な存在になることが多いからです。
なぜならば、不変量があるということは、そこに着目すれば、途中の経緯を一切すっとばして最後の状況を見ることができたりするからです。

この1230の例で言えば、全桁の合計が 6 ということから、最後の1桁で決着する時の数 6 が予見できる、ということです。

しかしまだ問題は残ります。それはやはり、途中の足し算が10を超えた場合。この時実は桁の合計が減っています。まあどこかで減ってくれないと最終的に1桁になれないので、減るのも「アタリマエ」ではあるのですが。
次の図は 4649 の 100,10 の位を選んで操作した時の例です。合計が23から14に減っています。

では、この「10を超えた時」に何が起こるかを解けば、全容が明らかになるはずです。

10を超えた時

では、足し算の結果が10を超えた時にどうなるか、見てみます。

他の桁は変化しませんから、純粋に選ばれた2つの桁にだけ着目すれば良いはずです。

• 例1: 46→10 小計4+6=10→1+0=1
• 例2: 79→16 小計7+9=16→1+6=7
• 例3: 58→13 小計5+8=13→1+3=4

…。まあせいぜい数十通りなので全部挙げてもいいんですが。これくらいで振り返ってみます。どの例でも共通しているのは、

• 必ず“1x”に変化している
  これは1桁同士の足し算は最大 9+9=18 なので、繰り上がりは 1 にしかならない、ということですね。
• 合計が9減っている

重要なのは「9減っている」というところですが、これはなぜか。次のように筆算で足し算した時のことを思い出してみましょう。

繰り上がりがある分、1の位の数字は10減っていますね。そのため桁の合計としては9減ることになる、ということが説明できました。
上で挙げた 4649 の例で、合計が23から14に減っていたのも、この「9減る」に因るものだったと言えます。

まとめ

では分かったことを整理します。

• 勝利/敗北条件
  • 自分の手番で数が1桁であれば敗北
• 桁数の変化
  • 操作における足し算で10を超えなければ1桁減る
  • 操作における足し算で10を超えた場合は変化なし
• 桁の合計の変化
  • 操作における足し算で10を超えなければ変化なし
  • 操作における足し算で10を超えた場合は9減る
• 決着の時
  • 数字が1桁
    → 最後に残る数字は 1～9 のいずれか

こうして並べると、「桁数の変化」「桁の合計の変化」が相補的であることが分かります。つまり、必ず桁数が1減るか、桁の合計が9減るか、どちらか一方だけが起こるということ。そして、最後の数字の範囲が決まっている以上、「桁の合計が9減る」というイベントは ( いつか、までは分からなくても ) 必ず決まった回数発生するということ。

そして、勝敗が桁数によって決定する以上、「桁の合計が何回9ずつ減らせるか」は桁数と同じ意味を持ちます。次の図の例のように、4桁だけれども2回合計が減る4649と、6桁で合計が変化しない100000は同じ回数で決着する、ということです。

なおかつ「決まった回数」ということは、途中の操作に関係なく、同じ結末に落ち着くということを意味します。

ここまで長かったですが結論です。

• 戦略に関係なく勝敗が決まる
• 勝敗は、「桁数」と「桁の合計を9減らすことができる回数」の合計の偶奇で決まる

実装

では、どうやってプログラムに落とし込むか…、ですが。

• どうせどうやっても勝敗は同じなんだから、適当な戦略を決めて勝負をシミュレートする
• 上で分かったことを元に、「桁数」「桁の合計を9減らすことができる回数」を調べる

の2通りが考えられます。もちろん1番目でも良いのですが実装が面倒くさいので折角突き止めたのですから、2番目で実装します。

以下は、実際にACしたC++11のコードです。

#include <iostream>
#include <string>
using namespace std;
int main() {
  string nums;
  cin>>nums;
  while ( cin>>nums ) {
    int s=0;
    for ( char c: nums ) {
      s+=c-'0';
    }
    int x=nums.size()+(s-1)/9;
    cout << ( x%2==0?"Fabre":"Audrey" ) << " wins." << endl;
  }
}

ポイントを挙げると、

• 先頭行はケース数でしかないので読み飛ばす ( 無視する )
• 入力行 ( ケース ) 毎のループで処理 ( numsには数字が文字列として格納されている )
• 桁の合計を、s に保存 ( 各桁の数値は '0' との char型同士の差で得られるので、文字毎のループで足していく )
• 桁数 ( nums.size() ) に何回合計が減らせるか ( (s-1)/9 ) を足して x とし、その偶奇により判断
• 偶数なら先手 Fabre、奇数なら後手 Audrey の勝ち

「何回合計が減らせるか」これは s の値 9 毎に変化するわけですから、9による割り算として計算できます。ただし、単純に割ってはダメで、ズレがある部分を考慮する必要があります。そこで (s-1)/9 としています。
なお、C++の除算 / は正の整数同士であれば、自動的に余りを切り捨てた結果になります。

参考: なお、考え方は変わりませんが、もっと簡潔なコードにすることはできます。説明を書くのが面倒くさいのでなぜこうできるかは、参考ということで各自にお任せします。

#include <iostream>
#include <string>
using namespace std;
int main() {
  string s;
  cin>>s;
  while ( cin>>s ) {
    int a=0;
    for ( char c: s ) {
      a+='9'-c;
    }
    cout << ( a%18>8?"Fabre":"Audrey" ) << " wins." << endl;
  }
}

終わりに

まとめです。

• 全貌を解き明かせば必要な計算は少しで済む
• 幾つかのケースを実際にシミュレートする。「例示は理解の試金石」
• まずは簡単なケースで。次に複雑なケースで簡単なケースとの違いに着目する
• 不変量は大事な解決の糸口
  ※この問題での不変量は、桁の合計そのものではありませんが

今更ながら。この解説は数学なりプログラミングにあまり慣れていない人向きを想定して書いたものです。理解の一助となれば幸いです。