AtCoder Beginner Contest 008 C問題について
問題
問題はこちらです。
ここにコインがN枚あり、それを全て同じ確率になるよう無作為に一列に並べる。
そこに対して以下の操作を行う
- 全てのコインを表向きにする
- 左端から順に右端にたどり着くまで、そのコインよりも右側にある、そのコインの倍数の書かれたコインをひっくり返す(表→裏、裏→表ともに行う)
【例*1】2(表) 4(表) 6(表)→2(表) 4(裏) 6(裏)→2(表) 4(裏) 6(表)……終了
これが、全ての並び順を同じ確率で起こるとした上で、表を向いているコインの枚数の期待値を出力してください。
――という問題です。
問題を読んだ感想
これ、ABCのC問題ですか？
まず問題を読んで、すっっっっごくめんどくさいんじゃないかと思いました。
N≦8を満たすデータセットなら99点って、それこの問題がこの問題である必要性ありますかね！！！って感じです。
でも今回ブログに書いている理由として、賢い人の思考回路(まさしく回路的)を紐解いていけば、もしかするとこういった数学的アプローチをするときに役立つかもしれないというのがあって、ABCのC問題としてというよりも思考回路の成長に良質なのではないかというところに行き着きました。
解説スライドを読んで見る(p17からです)
まず総当りはN<=8でいけて、N<=100なら無理なんだろうと考えられます。
これはメタ読みしてもいいですし、大体、全部の組み合わせをシミュレートするのは無理があるだろうと想像がつきます。(N!通りになりますからね……)
次の段階から自分とアプローチの違いがあって、自分はおそらく数学的に計算で求めるのだろうというところまで考えついていましたが、期待値の性質を活かすというところには全く辿り着けませんでした。
あるコインxに対する約数の数が～～のときは～～とか考えてました。それは数学的と言わないのではないか。
上記した自分の思考って、手元で試してみないとそれが正しいのかわからないのに、手元で試した程度では確かであることがわからないんです。
仮にちょっとした法則性が見えてきたとしても、それが本当に正しいのか(例えば極端なデータセットのときなど)は示せません。
それに比べると期待値の性質を用いるというのは、示すまでもなく確かです。確かであるから性質なので。
更に組み合わせとして考えるのではなく、あるコインxに対してフォーカスした時、必要なのはそれの約数だけであるとした。
つまりその約数の数さえわかればあるコインxを左から順に動かしてきたとしても、裏・表が順に繰り返されるので、そのコインが表になる確率を求めることが容易です。
この問題において何より重要なのは、表を向いているコインの枚数の期待値を出力してくださいという点です。
つまり、ひっくり返される側をフォーカスするほうが、その状態を考えやすいといえます。(以下はひっくり返されるコインのパターン、0はあるコインの約数であるコイン)
このアプローチにたどり着ければ、あとはそれぞれのコインについて約数の数を数えて、それぞれのコインについて期待値を求めて最後に足し合わせるコードを書くだけでおそらくACになると思います(あとでコードは書きます)
大事だなと思ったこと
確かであることがわかることだけを考えるべき。
もちろん問題を読んで、すぐにその思考に移れるかというと厳密には難しいと思います。
ただ、何度も何度も確かであると(おそらく)確かめられないことを脳内で試行するのは、時間を失うだけでなく頭も疲れてしまいます。
そのあたりを見極めて、『こうだからこうなる、つまりこの考え方で答えが出る』というような、証明とまでは行かなくとも論理的に破綻していない思考回路を意識する必要があると感じました。
もちろんこの問題のアプローチ自体、ひっくり返される側のコインにフォーカスを当て、更に約数かそうでないかの二値化によって単純にし、数を数えて偶奇で確率を分け、最後に足して答えを出力するという、少し地頭が必要な気もするものなので、適切な思考回路で辿ったとしても難しかったかもしれません。
今後は『検証可能』を意識して問題に取り組んでいきたいなあと考えています。
追記：期待値の性質を～というところよりも、ひっくり返される側をフォーカスするということを考えるほうが重要であってたどり着きやすいようにも思う。
意外とシミュレート系だと逆を考えるってよくあるので、そこを頭に入れておくことが大事だと思う。
*1:太字はコインを返すのに参照した『そのコイン』を示す
