No.3031 (物理学)長距離~教育的問題 解説

おことわり

サンプルが変更されたため、ここに書いた解法は、もはや通用しません。

問題

No.3031 (物理学)長距離相互作用の収束計算に関する教育的問題 - yukicoder

ある仮定の下、イオン結晶内のある点(座標の原点)の電位を求める問題です。

解説

電位は重ね合わせが成り立ちますので、各電荷から受ける電位の総和を求めることになります。

なので、厳密な証明は別として、直感的には、求める電位 \( V \) は、適当な係数 \( A, B, C, \dots, P \) を用いて

\( V = A\,\alpha_{000} + B\,\alpha_{001} + C\,\alpha_{010} + D\,\alpha_{011} + E\,\alpha_{100} + F\,\alpha_{101} + G\,\alpha_{110} + H\,\alpha_{111} \)
\( \quad \quad + \ I\,\beta_{111} + J\,\beta_{113} + K\,\beta_{131} + L\,\beta_{133} + M\,\beta_{311} + N\,\beta_{313} + O\,\beta_{331} + P\,\beta_{333} \)

と表せそうだと言えます。

(気分としては、これらの係数は、電荷の種類ごとの距離の逆数の総和と解釈されますが、実際にはそれぞれの総和は発散するため、厳密な解釈ではありません。)

ここで、原点から見た距離の対称性から、

\( B = C = E \)

\( D = F = G \)

\( I = J = K = L = M = N = O = P \)

が言えますので、

\( V = A\,\alpha_{000} + B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)
\( \quad \quad + \ I\,( \beta_{111} + \beta_{113} + \beta_{131} + \beta_{133} + \beta_{311} + \beta_{313} + \beta_{331} + \beta_{333} ) \)

とまとめることができます。

さらに、 \( \beta_{111} + \dots + \beta_{333} = -4( \alpha_{000} + \alpha_{111} ) \) という条件ですので

\( V = A\,\alpha_{000} + B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)
\( \quad \quad + \ I\,( -4( \alpha_{000} + \alpha_{111} ) ) \)

となります。

ここで、 \( A - 4 I \) を改めて \( A \) と置きなおす( \( H \) も同様)ことにより、

\( V = A\,\alpha_{000} + B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)

だけになります。

さらに、 \( \sum_{ijk} \alpha_{ijk} + \sum_{lmn} \beta_{lmn} = 0 \) という条件から、この左辺を \( - B \) 倍して上式の右辺に加え、 \( A, D, H \) を適宜置き直したことにすることで \( B\,( \alpha_{001} + \alpha_{010} + \alpha_{100} ) \) の部分を消し去ることができて、

\( V = A\,\alpha_{000} + D\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) + H\,\alpha_{111} \)

になります。

ここまで来れば、あとはサンプルで与えられている数値を代入して \( A, D, H \) の値を求めてやれば良くて、

\( V = - 2.324\,\alpha_{000} - 0.486\,( \alpha_{011} + \alpha_{101} + \alpha_{110} ) - 0.289\,\alpha_{111} \)

という式を得られます。あとはこれをお好きな言語で1行でコーディングして提出できます。

https://yukicoder.me/submissions/239962 (Perl, 54 bytes)

感想

というわけで、解くだけなら難しいアルゴリズムが必要なわけでもなく、★6はないなあというのが正直なところです。特に、サンプル4が追加されたことで、難易度がぐぐっと下がったように思います。

あと、このようなチャレンジ系の問題は、考える時間を24時間とか1週間とかもらえると嬉しい気がします。2時間で賞味期限が切れてしまうのは、もったいないです。

追記(2018/3/1)

出題当初はサンプルが3つあって、途中で1つ追加されて4つのサンプル(うち3つが線形独立)があったのですが、その後、サンプルが全部削除されてしまったようです。とか書いていたら新たなサンプル(元のサンプル1と実質同じ)が追加されたようです。そんなわけで、上で書いた解法は、サンプル数が足りないので、もはや通用しません。

No.620 ぐるぐるぐるりん 解説

問題

No.620 ぐるぐるぐるりん - yukicoder

所与の \( T, w, v, g_x, g_y \) に対して、

\( \left( \begin{array}c x_0 \\ y_0 \end{array} \right) = \left( \begin{array}c 1 \\ 0 \end{array} \right) \)

\( \left( \begin{array}c x_{t+1} \\ y_{t+1} \end{array} \right) = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \left( \begin{array}c x_t \\ y_t \end{array} \right) + \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

\( \left( \begin{array}c x_T \\ y_T \end{array} \right) = \left( \begin{array}c g_x \\ g_y \end{array} \right) \)

を満たし、かつ \( \sum_{t=0}^{T-1} ( u_{x,t}^2 + u_{y,t}^2 ) \) を最小化するような \( u_{x,t}, u_{y,t} \) を求めよ。

解説

\( M = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \)

と置きます。

満たすべき条件は要するに

\( \left( \begin{array}c g_x \\ g_y \end{array} \right) = M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) + \sum_{t=0}^{T-1} M^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

ということです。

\( M \) は拡縮と回転の合成変換となっており、拡縮倍率を表すスカラー \( s = \sqrt{(v+1)^2+w^2} \) と回転を表す行列 \( R = \left( \begin{array}{cc} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{array} \right) \) を用いて

\( M = s R \)

と表すことができます。

このうち、回転 \( R \) は \( \sum_{t=0}^{T-1} ( u_{x,i}^2 + u_{y,i}^2 ) \) の値に影響しませんから、

\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = R^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

と置くと、この問題の条件は

\( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) = \sum_{t=0}^{T-1} s^{T-1-t} \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \)

を満たし、かつ \( \sum_{t=0}^{T-1} ( u'_{x,t}^2 + u'_{y,t}^2 ) \) を最小化すると言い替えることができます。

これは、成分ごとに考えれば単なるスカラーの問題として解くことができて(*1)

\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = \cfrac{s^{T-1-t}}{\sum_i s^{2(T-1-i)}} \left( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) \right) \)

となります。

あとは \( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \) から \( \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \) を復元すれば完成です。

--------

(*1) 球と平面の接点の問題(原点 \( (0,0,0) \) を中心とする球が平面 \( ax+by+cz=d \) に接しているとき、その接点の座標を求めよ)の考え方で解くことができます。

感想

というわけで、ほぼ高校数学の範囲で厳密解を求めることができて、あとは具体的な数値を代入するだけですので、これで★4.5は過大気味ではないかとも思いましたが、実際に解けている人が非常に少なく、強い人も苦労しているようですので、競技プログラミング的には難しい問題のようですね。

No. 410 「出会い」ショートコード解説

はじめに

yukicoder コンテストで出題された問題 No. 410 「出会い」のショートコード(2016年8月13日現在)の解説です。

問題ページ: http://yukicoder.me/problems/no/410

ショートコード: http://yukicoder.me/submissions/110735

問題の概要

入力:

A B
C D

が与えられる(A,B,C,Dは整数)。(abs(A-C)+abs(B-D))*0.5 の値を出力せよ。

私の答案

tr - _|dc -e?sx?sy-d*vlxly-d*v+.5*p

35 bytes です。言語は Bash です。 tr と dc を呼び出しています。 dc は先日 yuki さんにお願いして導入してもらい、使えるようになりました。

dc とは?

逆ポーランド形式の無限精度の計算が行える卓上計算機」だそうです(出典: http://kazmax.zpp.jp/cmd/d/dc.1.html)。今日では、 RubyPython で精度を気にすることなく整数演算ができますが、かつて Perl の時代にはそういうわけにはいきませんでした。なまじっか Perl が使えてしまうせいで RubyPython を覚える気になれない私は、 dc にはまだまだお世話になっています。

コードの解説

まず、 tr - _ で、入力に含まれる - (マイナス)を全て _ (アンダースコア)に変換しています。これは、 dc の入力においては - (マイナス)は二項演算子であり、負号は _ (アンダースコア)で表すことになっているからです。(一方、出力においては負号は - (マイナス)です。つまり、 dc は自分が出力する数値を解釈できないという謎仕様です。)

次に、負号を変換した入力を dc に渡しています。 -e は perlruby の -e と同じで、スクリプトの直接指定です。そのスクリプトをトークンに分解すると、次のようになります。

? sx ? sy - d * v lx ly - d * v + .5 * p

? は、入力を1行読んで実行する、です。最初の ? で入力の A B が読まれ、次の ? で C D が読まれることになります。読まれた値は、スタックにプッシュされます。

sx は、スタックをポップして変数 x に格納する、です。最初の ? の実行後のスタックは A B ですので、 sx で x には B が入り、スタックは A だけになります。同様に、 sy で y には D が入り、スタックは A C になります。

- d * v という一連の命令が2回出てきます。 d はスタック先頭の値の複製、 v は(非負の)平方根です。つまり、スタック先頭の2つの値の差を2乗してその平方根を求めていますので、差の絶対値が得られます。

lx ly は、変数 x と y の値(つまり B と D )をスタックにプッシュします。

+ .5 * で、これらを足して 0.5 倍しています。 .5 *2 / のほうが短そうですが、デフォルトで商が整数になってしまうので、ここではうまくいきません。

p で結果を出力しています。

おわりに

解説の配信のとき、説明が必要っぽい雰囲気だと思ったので、書いてみましたが、いかがだったでしょうか。全く需要がない気もしますが、果たして最後まで読んでくれた人はいるのでしょうか。

gnupack 版 Emacs で IME の on/off に合わせてカーソルの色を変える方法

gnupack 版 Emacs とは

本家 GNU が配布している WindowsEmacs バイナリは、 IME が on のときに

  • 入力中の文字が画面に表示されない
  • C-x b などのキーシーケンスで b が IME に吸われる

などといった不具合があるため、日本語環境ではまともに使うことができません。(なお Emacs 自体が独自の辞書を備えた入力メソッド機能を内蔵しており、そちらを使えば上記の問題は起こりませんが、せっかく IME があるのだからそれを使いたいですよね。)

そこで、 gnupack というプロジェクトが、上記の問題を解決するパッチを当てた Emacs を独自にビルドし配布しています。これのお世話になっている人は多いと思います。私もそうです。

gnupack プロジェクト日本語トップページ - OSDN

(ところで、 gnupack が現在(2016年5月)単体で配布している最新の Emacs は 24.2 と若干古いのが気になります。今後も是非とも本家に追随するか、もしくは上記の問題を解消するパッチを本家に取り込んでもらうようにしてもらえると嬉しいです。なお Cygwin を含むフルパッケージのほうには Cygwin でビルドされた Emacs 24.5.1 が含まれているようですので、そちらを使えということかもしれませんが、 Emacs だけのために Cygwin を丸ごともう1セット導入するというのもなかなか厳しいものがあります。)

IME の on/off に合わせてカーソルの色を変える

例えば IME が on のときだけ Emacs のカーソルが赤くなるようにすると、とても快適です。これについて gnupack 版での設定方法を説明します。(なお MuleMeadow とは設定方法が異なります。また、以下の方法は本家 GNU 配布版 Emacs では使えません。)

やることは以下の3つです。いずれも ~/.emacs.d/init.d に書いておくといいと思います。

1.入力メソッドIME に設定

(setq default-input-method "W32-IME")

初期設定では default-input-method"japanese" に設定されているので "W32-IME" に変更します。この "W32-IME" という入力メソッド名は本家 GNU 配布版には存在しないものです。これを設定することにより、入力メソッドとして IME が使われるようになります。 C-\ (初期設定で toggle-input-medhod コマンドが割当てられている)を押して IME の on/off が切り替わるのを確かめてみてください。

2. [kanji] キーイベントの有効化

(global-set-key [kanji] 'toggle-input-method)

初期設定では [kanji] には ignore が割り当てられているので変更します。これを設定しなくても「半角/全角」キーを押せば IME の on/off は当然切り替わりますが、これを設定することにより、「半角/全角」キーを押して IME の状態を切り替えたときに、次に説明するフックが呼ばれるようになります。また [kanji] キーイベントは「半角/全角」キーを押したときだけでなく、例えば言語バーをマウスでクリックして IME の状態を切り替えたときなどにも発生するため、このときにもフックが呼ばれるようになります。

3.フックの登録

(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

IME が on になったときと off になったときにそれぞれ呼ばれるフックです。ここでカーソルの色を変えています。上記では IME が on のときに赤、 off のときに青ですが、好みに応じて変更してください。

まとめ

以下のコードをあなたの ~/.emacs.d/init.d の最後にコピペして下さい。

(setq default-input-method "W32-IME")
(global-set-key [kanji] 'toggle-input-method)
(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

幾何の問題

知っていればそのまんまですが、知らないと驚くと思います。(私は知らなかったので驚きました。ていうか、答えはわかっていますが解き方がわかりません。)

問題

\(t>0\) とし、点 \(P\) の座標を \((t,\dfrac{1}{2t})\) とします。

2点 \(A,B\) の座標をそれぞれ \((1,1),(-1,-1)\) とします。

このとき、 \(BP-AP\) を求めてください。

(\(BP\)は点\(B\)と点\(P\)との距離、\(AP\)は点\(A\)と点\(P\)との距離。その差を求めてください。)

解説

そうなのです!最初に「知っていればそのまんま」と書きましたが、「逆数のグラフが双曲線であることを」知っていれば、ということです。いや、ちっとも知りませんでした。

なるほど! \(\sqrt{b}-\sqrt{a}\) の形なので、有理化の要領で \(\sqrt{b}+\sqrt{a}\) を掛けたりしてみましたが、複雑化する一方でうまくいきませんでした。まるっと自乗してしまえばいいんですね。素晴らしいです。

解答

\[\begin{align}BP-AP &= \sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2} \\ (BP-AP)^2 &= \left(\sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2}\right)^2 \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\sqrt{\left((t-1)^2+(\dfrac{1}{2t}-1)^2\right)\left((t+1)^2+(\dfrac{1}{2t}+1)^2\right)} \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\left(t^2+(\dfrac{1}{2t})^2\right) \\ &= 4 \end{align}\]

よって \( |BP-AP| = 2 \) 。

\(t > 0 \) より \( BP-AP > 0 \) なので \( BP-AP = 2 \) 。

…ということのようです。合ってるかな?

1 から始めて 3x+1 と 4x+1 で生成される数の問題

ふと思い付いた問題ですが、自分ではよくわかりませんので、誰か解いて答えを教えてください。

\(x\) の初期値を \(1\) とします。
\(x\) に対して、次の操作 A または B を選んで、適用します。
A : \(x\) を \(3\) 倍してから \(1\) を加えます。(\(x:=3x+1\))
B : \(x\) を \(4\) 倍してから \(1\) を加えます。(\(x:=4x+1\))
これを任意の回数繰り返します。

例えば、最初に操作 B を行い(\( 1 \times 4 + 1 = 5 \))、次に操作 A を行うと(\( 5 \times 3 + 1 = 16 \))、 \(x\) の値は \(16\) になります。
これを、「 \(16\) の生成列は BA である」と表現します。

別の例として、 \(10000\) の生成列は ABBABBA です(確かめてみてください)。

ここで問題です。

異なる2つの生成列を持つような数は存在するでしょうか?
存在する場合には、例を示してください。
存在しない場合には、それを証明してください。

追記:寄せられた考察(2015年12月9日)

上記の問題に対して、何人かの方から、様々なアプローチの考察を頂きました。ありがとうございます。頂いた順に、結論だけ簡単にまとめて掲載します。(私の解釈に基づいて記載しているため、元々の表現と異なっていたり、結論自体が異なっているものもありますが、ご了承ください。また、最終的な結論の正しさが確認できないものについて、正しいと考えられる中間段階の結論を記載しているものもあります。)

  1. 最後の共通部分を取り除いた2つの異なる生成列の一方は A で終わり、もう一方は B で終わるため、生成される数は奇数である。
    ―― roiti (@roiti46)
  2. 最後の共通部分を取り除いた2つの異なる生成列を持つ数を \(36\) で割った余りは \(13\) である。
    ―― %20 (@henkoudekimasu)
  3. 2つの異なる生成列を持つ数は、4億以下には存在しない。
    ―― ろくかん松 (@rokukan)
  4. 最後の共通部分を取り除いた2つの異なる生成列の一方は AAAAAA で終わり、もう一方は BBB で終わる。
    ―― %20 (@henkoudekimasu)
  5. A のみからなる生成列と B のみからなる生成列とが同じ数を生成することはない。
    ―― %20 (@henkoudekimasu)
  6. 最後の共通部分を取り除いた2つの異なる生成列の一方は BBB で終わるので、生成される数を \(64\) で割った余りは \(21\) である。したがって、もう一方の生成列の最後の A の行う前の値を \(64\) で割った余りは \(28\) となる。
    ―― ぴろず (@p_shiki37)
  7. \( A = \begin{pmatrix} 3 & 1 \\ 0 & 1 \end{pmatrix} , B = \begin{pmatrix} 4 & 1 \\ 0 & 1 \end{pmatrix} \)
    と表現でき、これらを用いた2つの生成列を \( S_1 , S_2 \) とすると、
    \( {S_1}^{-1} S_2 = \begin{pmatrix} a & 1-a \\ 0 & 1 \end{pmatrix} \) の形になる。
    ―― ぬ (@nu4nu)
  8. 操作 A を \(3x+1\) の代わりに \(2x+1\) にした場合には、二進数で表した時に、 A は右に 1 を追加する操作、 B は右に 01 を追加する操作になるため、異なる生成列が同じ数を生成することはない。
    ―― roiti (@roiti46)
  9. 元の問題は、「\(n \ge 1 \) で定義される2つの異なる非負整数列 \( \{p[n]\},\{q[n]\} \) と正整数 \(X,Y \) であって、次を満たすものが存在するか」と同値。
    • \(p[1]=0,q[1]=1\) (「最後の操作が同じでない」と対応)
    • \( p[n+1]-p[n] \in \{0,1\} \) ( \(q\) も同様)
    • \( \sum_{k=1}^{X} 3^{p[k]} 4^{k-p[k]} = \sum_{k=1}^{Y} 3^{q[k]} 4^{k-q[k]} \)
    よって \( \#\{k|p[k]=0\} \equiv 0 \) mod \(3\) などが示される。
    ―― かならい (@sugarknri)

また、以下は私自身の考察です。

\(x\) の初期値を \(0\) にした場合、自明な解 A \(=\) B \(=1\) があります。
また、初期値を \(2\) にした場合、 ABAAAA \(=\) BBBBB \(=2389\) という解が見付かります(なので、解が存在しない証明で、初期値に依存せずに、このケースを含んでしまっているものは、誤りであることがすぐにわかります)。
初期値を他の自然数にした場合も含めて、これら以外に解は見付かっていません。

 

『シンプル・ライフゲーム』に参加した記念(解説なし)

CodeIQ で出題された『シンプル・ライフゲーム』というコードゴルフに参加しました。

codeiq.jp

Perl と C で最短を取ることができました。 Perl は初日からガチで臨んだので、全言語最短が取れて良かったです。 C は締切前日に気まぐれで始めて、ちゃんと競えないタイミングで最短を更新してしまったので、申し訳なかったです。

締切後に解答を公開したところ、 Perl の解説を angel さんが書いてくださいました! いつもながら的確でわかりやすいです。しかも、私のコードからさらに 3 文字も縮めています。

ange1.hateblo.jp

そして、 C の解説を、出題者の ozy さんが直々に書いてくださいました! 三連休の全てに仕事が入っている中、合間を縫って書いてくださったとのことです。

d.hatena.ne.jp

さらに、 CodeIQ MAGAZINE の公式の解説記事で、貴重な文字数をかなり割いて、 Perl の解説を書いてくださいました!「10の極意」など、魅せ方がさすがです。自分のコードなのに、ほほうと思ってしまいましたw

codeiq.jp

以上、 Perl も C も、 angel さんと ozy さんにすっかり解説していただいたので、私から付け足すことは何もありません。ありがとうございます!