月草色の幻影 Official Site

家に引き籠っていると書き出しに困ります。
KC三戦連続延長戦の時にでも書いておけばよかったと暫し後悔。

皆さんこんばんは、Alhenaです。
私がずっと家にいる所為で電気代が上がっていると思うと、何とも居た堪れない気分になります。
まあ居ますけど。


今日は5月22日の問題の解答を書こうかと思います。

リンクも張りましたが、問題を此処に再掲しておきます。

問 42枚の紙を教師が持っている。
この紙を横7人、縦6人の並びで整列した42人の生徒に一枚ずつ配りたい。
教師も生徒も紙一枚を繰るのに1秒、紙を渡すのに2秒掛かり、教師は最前列の7人、生徒は前後左右の4人以外とは受け渡し出来ない。
どのようにすれば最も速く生徒全員に紙が行き渡るか。
但し、繰る・渡すといった行為は各人同時に一つしか行えず、また、教師が移動する時間は無視出来るものとする。


以下解答になりますので、自力で解きたい方は注意して下さい。




この並びで最も速く渡す方法を考えるよりも先に、生徒の並び方を無視した時(=教師または生徒が誰とでも受け渡しできる場合)の最速タイムを考えます。

渡り方の理想を考えると、全ての生徒が同時に手元に一枚の紙だけが残る状況になるのが、尤も無駄なく渡った結果だと予想できます。
従って、仮に生徒の人数が2の累乗で、始めから生徒の一人が紙を持っていたとすれば、只管手持ちの紙を半分数えて一枚も持ってない人に渡す、という行為を繰り返すことで、理想の状況に持ち込めることになります。

この時2^n人の生徒が居るとすると、そのタイムは(2^n-1)+2nで表されます。
()の中は紙を繰る回数、その後のnは紙を渡す回数です。
これを基調に一般化してみます。

先ず2^nではない場合の渡し方ですが、これは基本的には2^nの場合と同じように半分にして渡していきます。
本当にそれで最速なのか疑問に思う方もいらっしゃると思いますが、一先ずは受け入れて下さい。

次に教師が居る状況を考えます。
こちらは比較的簡単で、生徒が一人多いものとして扱えば問題ありません。

以上を踏まえた上で立式します。
紙を繰る回数は、紙の枚数をm枚とすれば、最終的にはこれを全てばらさなければいけないので、m-1回になります。
紙を渡す回数は、生徒m人に対してm<=2^nを満たす最小のnになりますから、ceil(log₂m)回になります。
但し、此方は教師を考慮に入れなければいけませんので、ceil(log₂(m+1))となります。
まとめると、(m-1)+2*ceil(log₂(m+1))　で表されます。

m=42とすれば、タイムは53秒と出てきます。
なお42枚という数字は、天井関数部分の閾値63枚よりは大分小さいので、実際の渡し方には結構な余裕があります。
なので解答も何通りもあることが予想されます。

さて、実際の解答に行く前に、この53秒を導出する過程に疑問のある方に対して、もう少し納得しやすい別の導出法を挙げておきます。
簡単にいえば至ってアナログな手法に拠る帰納法です。

1枚しかない場合を考えると、その秒数は2秒であることに疑う余地はないでしょう。
2枚しかない場合では、二通りの渡し方が考えられますが、何れにしても5秒になります。
また、生徒が元々2枚持っている場合には3秒で渡せます。

3枚以降はこの情報だけを元に、最速タイムを考えていきます。
どんな枚数であっても必ずその枚数を二つに分けなくては進まないので、二つに分けるまでにかかる秒数に、分けた後の長く時間がかかる方を足せば、その枚数のその分け方に拠る最速タイムが出てきます。
後はそれを比較していけば、ある枚数に対する最速タイムが帰納的に求まっていきます。

途中を書くのは面倒なので省略しますが、この方法でも53秒となります。


さて、漸く目標タイムが出せました。
此処から実際にそのタイムに近づけていきますが、結論から言えばこのタイムで渡し切ることが可能です。
かなり長くなってしまったので、その部分はまた次の機会にします。

此処まで下らない長文にお付き合い頂き、有難うございました。


追記(8/26)
上に書いた帰納法をRGSSで書いてみました。
興味のある方は覗いてみて下さい。

kami.txt