オフラインリアルタイムどう書くE26参加しました

はじめに

2018/9/1開催の「オフラインリアルタイムどう書くE26」に参加しましたので、そのレポートです。

しばらくオフライン参加できなくて久しぶりの参加でした。…ブログ書くのはもっと久しぶりだろ、と言われてしまうとまあ、その。

どんな感じ?

毎度永和マネジメント様のオフィスをお借りしているのですが、環境が整っていてやりやすい…。今回見たら、ホワイトボードが増設されていて説明に活用させていただきました。 …卓球台は最近あまり出番がないのですけども。

今回は私含めて6名でした。1人は初参加ということで、色々な人に参加して頂けるのは嬉しいですね。

問題

今回は初めて、@cedretaberさんが出題にチャレンジされました。難易度はやや高め、緊張感の増した(解答時間の)1時間…。すわ全敗かというところ、一応ロスタイム(というか解説タイム)中に解けたので、一応セーフでしょうか。(ということにしてください)

タイトルはGears Out!です。詳細は問題のサイトをご覧ください。概要は次の通りです。

• N×Nに配置されたギア(歯車)がある。
• 目的は、何回か操作を行い、最終的に全てのギアを上向きに揃えること。その操作手順を1つ挙げること。
• 1操作では、いずれかの歯車を時計回りに1/4回転させる。その時、上下左右に隣接する歯車も連動し、反時計周りに1/4回転する。

コードを組んで作るのは、「操作手順の1つ」なので、一意ではありません。そのために、回答をチェックする機能も上述の問題のサイトに仕組んであります。実際に歯車がガチャガチャ動いて合うかどうかをシミュレートしてくれます。…凝ってますね!

解説

問題の整理

まず最初に気付くこととしては、「操作する歯車の順番を入れ替えても結果に影響はない」ということです。 あくまで、その歯車と周囲の歯車を回転させるだけの操作なわけですから、いつ行っても効果は変わらないのです。

つまり、欲しいのは「どの歯車に何回操作を行うか」という回数の情報だということになります。

さて。各歯車の向きは数字として与えられていますが、ある歯車に1回操作を行うと、次の図のように、その歯車には+1、上下左右に隣接する歯車には-1の効果があります。なお、1周すると元通りなのでこれはmod 4の世界の話です。つまり、0と4や1と5は同じ値と見做すことができますから、1 から -1 されて 0 というのは 4 になっているのと同じことです。

逆に、各歯車を動かした時に、ある地点での数値がどう変化するかに着目します。すると、当該地点への操作がはプラスに、上下左右の隣接地点への操作はマイナスに働くということになります。

ということは、各歯車の操作回数を変数にとれば、次のような連立1次方程式を解いていることに他なりません。( 等号が≡となっているのはmod 4で考えているためです。 )

ということで、少なくともこれはガウスの消去法で解けるということに気付きます。

詳細は省きますが、会場で仕上げた解は、やっつけでガウスの消去法を実装したものです。なお、係数行列によって複数解があることになりますが、そこは適当に1通り選ぶようにしています。

効率的な解法

さて。先ほどの連立1次方程式、これはN=3に対して係数行列が9×9になっているのですが、これを3×3ずつに区切ってみると、似たようなパターンが現れることに気付きます。

それもそのはずで、ある歯車への操作がどの歯車に影響を与えるか、それは場所が変わっても同じパターンになっているからです。 ということは、この1次連立方程式をもうちょっと簡約化できるのではないかと考えてみます。

ということで、変数および歯車の数字の変化を、横一列でまとめてベクトルとしてみます。そうすると、1つの行列Aにより方程式を簡約化できることが分かります。ちなみに、行列Aは対角要素が1、対角要素の隣接要素が-1、その他が0の行列です。

ここから先、N=3 に限らず一般化した話に切り替えます。

$$ \left\{\begin{eqnarray} &~&A{\bf\it x_0} - {\bf\it x_1} &\equiv& {\bf\it b_0} \\ &~&- {\bf\it x_0} + A{\bf\it x_1} - {\bf\it x_2} &\equiv& {\bf\it b_1} \\ &~&- {\bf\it x_1} + A{\bf\it x_2} - {\bf\it x_3} &\equiv& {\bf\it b_2} \\ &~&\vdots & ~ & \\ &~&- {\bf\it x_{N-3}} + A{\bf\it x_{N-2}} - {\bf\it x_{N-1}} &\equiv& {\bf\it b_{N-2}} \\ &~&- {\bf\it x_{N-2}} + A{\bf\it x_{N-1}} &\equiv& {\bf\it b_{N-1}} \\ \end{eqnarray}\right. $$

というところで、${\bf\it x_{N}}\equiv{\bf\it 0}$ を導入すると、

$$ \left\{\begin{eqnarray} &{\bf\it x_1}&\equiv&A{\bf\it x_0} - {\bf\it b_0} \\ &{\bf\it x_2}&\equiv&A{\bf\it x_1} - {\bf\it x_0} - {\bf\it b_1} \\ &~&\vdots & ~ & \\ &{\bf\it x_k}&\equiv&A{\bf\it x_{k-1}} - {\bf\it x_{k-2}} - {\bf\it b_{k-1}} \\ &~&\vdots & ~ & \\ &{\bf\it 0}\equiv{\bf\it x_N}&\equiv&A{\bf\it x_{N-1}} - {\bf\it x_{N-2}} - {\bf\it b_{N-1}} \\ \end{eqnarray}\right. $$

つまり、ベクトル$x_n$に関する隣接3項間漸化式になっているということです。ここから、行列列(紛らわしい…!)$A_n$ とベクトル列${\bf\it v_n}$を導入して、${\bf\it x_n}\equiv A_n {\bf\it x_0} - {\bf\it v_n}$と表すことができると分かります。 それと先ほどの漸化式を照らし合わせると、

$$ \begin{eqnarray} &~&{\bf\it x_k} \equiv A{\bf\it x_{k-1}} - {\bf\it x_{k-2}} - {\bf\it b_{k-1}} \\ &\Rightarrow&A_k {\bf\it x_0} - {\bf\it v_k} \equiv A(A_{k-1} {\bf\it x_0} - {\bf\it v_{k-1}})-(A_{k-2} {\bf\it x_0} - {\bf\it v_{k-2}}) - {\bf\it b_{k-1}} \\ &\Rightarrow&A_k{\bf\it x_0} - {\bf\it v_k} \equiv (AA_{k-1}-A_{k-2}){\bf\it x_0} - ( A{\bf\it v_{k-1}} - {\bf\it v_{k-2}} + {\bf\it b_{k-1}} ) \\ \end{eqnarray} $$

というところから、

• $A_0 \equiv E,~~{\bf\it v_0}\equiv{\bf\it 0}$
• $A_1 \equiv A,~~{\bf\it v_1}\equiv{\bf\it b_0}$
• $A_n \equiv AA_{n-1}-A_{n-2}$
• ${\bf\it v_n} \equiv A{\bf\it v_{n-1}} - {\bf\it v_{n-2}} + {\bf\it b_{n-1}}$

と定めてあげれば十分です。そうやって、$A_N,~{\bf\it v_N}$ を計算してあげれば、${\bf\it x_N}\equiv A_N {\bf\it x_0} - {\bf\it v_N},~~{\bf\it x_N}\equiv {\bf\it 0}$ から、

• $A_N {\bf\it x_0} \equiv {\bf\it v_N}$

これを解いて${\bf\it x_0}$を求めることで、再度漸化式を回して芋づる式に各${\bf\it x_n}$が分かることになります。

この方法だと、解くべきベクトル方程式の係数行列がN×Nサイズですから、ぐっと計算量が落ちることになります。 ※今回の問題規模(N≦9)なら、総当たりしても済むくらいです。

こちらを行列操作(こちらはLU分解)で解いたのが改良版です。

終わりに

さて次の開催案内がもう出ています。興味がある方は是非ご参加を。 参考問題が事前公開されていますので、難易度を測るのにいいんじゃないでしょうか。

なお、今回の色々な方の実装例は、オフラインリアルタイムどう書く E26 の問題に紹介されています。