ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。数学はじめに2018/9/1開催の「オフラインリアルタイムどう書くE26」に参加しましたので、そのレポートです。オフライン参加できなくて久しぶりの参加でした。...ブログ書くのはもっと久しぶりだろ、と言われてしまうとまあ、その。どんな感じ?毎度永和マネジメント様のオフィスをお借りしているのですが、環境が整っていてやりやすい...。今回見たら、ホワイトボードが増設されていて説明に活用させていただきました。...卓球台は最近あまり出番がないのですけども。今回は私含めて6名でした。1人は初参加ということで、色々な人に参加して頂けるのは嬉しいですね。今回は初めて、@cedretaberさんが出題にチャレンジされました。難易度はやや高め、緊張感の増した(解答時間の)1時間...。すわ全敗かというところ、一応ロスタイム(というか解説タイム)中に解けたので、一応セーフでしょうか。詳細は問題のサイトをご覧ください。N×Nに配置されたギア(歯車)がある。目的は、何回か操作を行い、最終的に全てのギアを上向きに揃えること。その操作手順を1つ挙げること。1操作では、いずれかの歯車を時計回りに1/4回転させる。その時、上下左右に隣接する歯車も連動し、反時計周りに1/4回転する。コードを組んで作るのは、「操作手順の1つ」なので、一意ではありません。そのために、回答をチェックする機能も上述の問題のサイトに仕組んであります。実際に歯車がガチャガチャ動いて合うかどうかをシミュレートしてくれます。問題の整理まず最初に気付くこととしては、「操作する歯車の順番を入れ替えても結果に影響はない」ということです。その歯車と周囲の歯車を回転させるだけの操作なわけですから、いつ行っても効果は変わらないのです。欲しいのは「どの歯車に何回操作を行うか」という回数の情報だということになります。各歯車の向きは数字として与えられていますが、ある歯車に1回操作を行うと、次の図のように、その歯車には+1、上下左右に隣接する歯車には-1の効果があります。なっているのと同じことです。逆に、各歯車を動かした時に、ある地点での数値がどう変化するかに着目します。すると、当該地点への操作がはプラスに、上下左右の隣接地点への操作はマイナスに働くということになります。いうことは、各歯車の操作回数を変数にとれば、次のような連立1次方程式を解いていることに他なりません。4で考えているためです。)ということで、少なくともこれはガウスの消去法で解けるということに気付きます。詳細は省きますが、会場で仕上げた解は、やっつけでガウスの消去法を実装したものです。係数行列によって複数解があることになりますが、そこは適当に1通り選ぶようにしています。先ほどの連立1次方程式、これはN=3に対して係数行列が9×9になっているのですが、これを3×3ずつに区切ってみると、似たようなパターンが現れることに気付きます。それもそのはずで、ある歯車への操作がどの歯車に影響を与えるか、それは場所が変わっても同じパターンになっているからです。いうことは、この1次連立方程式をもうちょっと簡約化できるのではないかと考えてみます。いうことで、変数および歯車の数字の変化を、横一列でまとめてベクトルとしてみます。すると、1つの行列Aにより方程式を簡約化できることが分かります。ちなみに、行列Aは対角要素が1、対角要素の隣接要素が-1、その他が0の行列です。限らず一般化した話に切り替えます。$$つまり、ベクトル$x_n$に関する隣接3項間漸化式になっているということです。v_n}$と表すことができると分かります。b_{n-1}}$と定めてあげれば十分です。x_n}$が分かることになります。この方法だと、解くべきベクトル方程式の係数行列がN×Nサイズですから、ぐっと計算量が落ちることになります。※今回の問題規模(N≦9)なら、総当たりしても済むくらいです。こちらを行列操作(こちらはLU分解)で解いたのが改良版です。終わりにさて次の開催案内がもう出ています。興味がある方は是非ご参加を。参考問題が事前公開されていますので、難易度を測るのにいいんじゃないでしょうか。問題に紹介されています。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。