SuperCon2001本選課題案

(* 本課題は、IPSJ-PSC2001で出された問題を参考にして作られています。 *)

課題説明

奇妙な宇宙を考えます。空間は2次元で、その空間に存在する無数の星たちも 厚みのない2次元星ばかりです。しかし、ちゃんと質量は持っている。そうした 星たちが、ある時刻に存在する位置を初期位置として、T単位時間後の位置を 求めるのが今回の問題です。1単位時間を冲とします。また、星が移動した場合、 偶然同じ座標に2つ以上の星が重なることが起きるかもしれません。しかし、 この宇宙では、それも許されるものとします。つまり、重なって消滅することも、 分裂することもないということです。さらに、この宇宙には果てはあるのですが、 その果てに到達した場合はどうなるかということは考えないことにします。

質量を持つもの同士間では、ある距離以内においては引き合う力(張力)が働きます 。しかし、ある距離以上離れた場合には、まったく力が働かなくなるものとここでは 仮定します。

質量を持つ2つの物体間の運動を考えるのは簡単ですが、たくさんの星同士の 運動を予測することは困難です。そこで、次のような仮定をもうけ、予測を可能と します。

課題の定式化

以上のことを整理し、定式化すると次のようになります。(ただし、この定式化は 現実の物理現象を反映しているわけではない)

2つの星Si、Sjの質量をそれぞれmi, mj、距離ベクトル*「ベクトルについて」を参照を ri,jとし、2つの星の間に働く力Fi,j

   Fi,j = (mi * mj)/|ri,j|2 * ri,j     ---- (1)
と決める。ただし、最後のri,jは、ベクトルの方向だけを示し、 大きさは1とする。

一方、質量mの物体が加速度αで運動しているとき、物体は

   F = m α       --- (2)
の力を受ける。式(1)、(2)から、星Siが星jから受ける 加速度成分αi,jが次のように計算できる。
   αi,j = mj/|ri,j|2 * ri,j
速度ベクトルがあることから加速度もベクトルで表現されることに注意。

そして、星Siが他のすべての星S0...Sn-1から 受ける力によって生じる加速度αi

   αi = SUM(αi,j) ,   j=0,..., n-1
とする。

なお、2つの星の間の距離が32以上離れているときは、両者に力は加わらないと 考えるので、そのとき2つの星の間に生じる加速度成分も0となる。

加速度がわかれば、星Siの凾博條ヤ後の速度、および位置を決めることが できる。時刻tとし、冲時間後をt+1とすると、速度v, 位置pの変化は次のようになる。

   vt+1i = vti + αti * 冲,
   pt+1i = pti + vti * 冲,

丸めについて:力を計算するにあたり、2点間の距離を求める時、x成分、y成分の差を 求めたあと、一度丸めを行う。また、加速度成分を計算するときも、距離で除算した あと、X成分とY成分の値は整数値に丸めることを行う。

問題

N個の星に関する初期データ(質量、位置、速度)が与えられ、T時間後の位置を求める プログラムを書きなさい。

(1)入力データ

入力データは次の関数で与えられます。
   void supercon2k1_get_config(int problem_no, 
                           int * size, int * n_steps, double * dt);
   void supercon2k1_get_data(int problem_no, double * a);
ここで、

なお、u, vは速度ベクトルのX方向成分とY方向成分をあらわしている。

(2)出力データ

出力データは、入力データの配列aとまったく同じ形式になっていなければならない。 そして、次の関数によって正しい計算が行なわれたかをチェックします。
   void supercon2k1_verify(int problem_no, double * a);

(3)使用するプログラミング環境

C言語、および、MPIライブラリを使います。

(4)プログラミング上の注意

SGI Origin2000では、doubleは64ビットとなります。

宇宙は有限と、その境界は縦横共にdoubleの値を越えることはないものとします。 また、当然座標は正負を考えます。この宇宙の中心は(0,0)です。

(5)使用するコンピュータ環境

プログラミング中は4CPUでテストしてください。本選審査は32cpuで行ないます。 プログラミング中であっても、32cpuでテストしたい場合はバッチを使ってください。

(注)ベクトルとは

ベクトルとは、大きさと方向を持った数学的な実在と考える。ベクトルAを (a,b)と表記する。これを図示すると、次のような絵になる。

ベクトルAは横a、高さbで表される方向を持ち、大きさSQRT(a^2+b^2)を持つ。この大きさの ことをノルムと呼び、|A|とあらわす。 たとえば、ベクトル(3,4)の場合、横3、縦4の方向を持ち、ノルムは5となる。

ベクトルに関する簡単な公式を載せておく。ベクトル(a,b), (c,d)、定数kと すると、

  (a,b) + (c,d) = (a+b, c+d)
  (a,b) - (c,d) = (a-b, c-d)
  k * (a,b) = (k*a, k*b)
となる。 2つの点(x1,y1), (x2,y2)があったとき、その距離ベクトルr1,2を 次のように定義する。
  (x2-x1, y2-y1)