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と実質同じ)が追加されたようです。そんなわけで、上で書いた解法は、サンプル数が足りないので、もはや通用しません。