SuperCon2016に参加した話

参加記 プログラミング

Supercomputing Contest - Supercomputing Programing Contest Official Site

SuperCon2016の本選に参加しました．

キャンパスを間違えた

SuperConの会場は豊中キャンパスだったのですが，ぼくの調査不足により吹田キャンパスに行ってしまい，無限に時間を溶かしました．申し訳ないです．

大阪大学の学食は美味い

安くて美味しかったです．

色んな人にあった

みんな「THE・オタク」と言った感じで面白かったです．
ゲ・ドリンクくんは過度のストレスにより禿げてました．(マジ)
つよっしーくんは本名が「つよし」ではなかったです．
KO氏はデレステを片手でしていました．
うぃんじー氏はプロでした．
らて氏はルマンドの黄色と紫色の違いが分かるイケメンでした．

内容

n個の頂点，c色に塗り分け，d次の正則グラフの最短経路長の総和(ASPL)をなるべく小さくしようという問題．
SuperConなので東工大の「TSUBAME」を使って高速化しようみたいな感じです．
ぼくはそもそもグラフに関して疎く，今回の問題で沢山の知識を得ました．(ダイクストラ，ワーシャルフロイド，焼きなましとか)
言語はC言語(CUDA)を使いました． CUDAはGPUプログラミングに必要な環境で，TSUBAMEを使うためにはこれが必要でした．

方針としてはRandomに生成したグラフを重みの和が小さくなるようにつけかえていき，これ以上良くならなかったらASPLアスパラを計算して良くしていくという感じです．

ASPLはnが2048くらいになると死ぬほど時間がかかったので辛かったです．

結果

優勝は久留米高専の「GhostDiv」でした． そしてぼくたち沖縄高専「tsuraMI」は7位でした．つらみ．

4問目はなぜかぶっちぎりで1位でしたが，6問目は18位(最下位)など問題によって順位のブレがありました．
また，「GhostDiv」はGPU不使用でした．GPUを使わないチームは強いみたいな風潮があります．

感想

今回はjin先輩にコーディングなど任せっきりだったので，ぼくがやったことと言えばASPL高速化を考える(失敗したが)くらいしかしてません．反省しています．
そのためにはもっと競技力をつける必要があります．PCK，JOIがあることですし，蟻本等読んで勉強していきたいです．
来年は今年以上の結果を出せるようリベンジしたいです．

AOJ0010 - Circumscribed Circle of a Triangle

AOJ

計算するだけなんですけど，色々と面倒臭かった．

AOJ0010

参考:kanetaiの二次記憶装置

各点から円の中心までの距離(つまり半径)が全て等しいことを考える．

各点を { A(x_1, y_1)} { B(x_2, y_2)} { C(x_3, y_3)} と置く．
また中心の座標を{ P(x_p, y_p)} と置く．

半径が等しいということは

{ | \vec{PA}| = | \vec{PB}| = | \vec{PC}|}

これらを連立方程式として解けば{ x_p}と{ y_p}が求まる．

連立方程式は以下のようになる．

{ \begin{cases} \; 2(x_1 - x_2)x_p + 2(y_1 - y_2)y_p = x_1^2 + y_1^2 - x_2^2 - y_2^2 \\ \; 2(x_1 - x_3)x_p + 2(y_1 - y_3)y_p = x_1^2 + y_1^2 - x_3^2 - y_3^2 \end{cases}}

行列を用いて，

\begin{pmatrix} 2(x_1 - x_2) & 2(y_1 - y_2) \\ 2(x_1 - x_3) & 2(y_1 - y_3) \\ \end{pmatrix}

の逆行列と

\begin{pmatrix} x_1^2 + y_1^2 - x_2^2 - y_2^2 \\ x_1^2 + y_1^2 - x_3^2 - y_3^2 \\ \end{pmatrix}

の積を求めればよい．

また，半径の長さは先程の { | \vec{PA}| = | \vec{PB}| = | \vec{PC}|} どれか一つに代入して求める．

コード

#define sq(x) ((x) * (x))

signed main()
{
  int n;
  scanf("%d", &n);

  while (n--){
    double x1, y1, x2, y2, x3, y3;
    scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3);

    double a = 2 * (x1 - x2), b = 2 * (y1 - y2),
           c = 2 * (x1 - x3), d = 2 * (y1 - y3);
    double e = sq(x1) + sq(y1) - sq(x2) - sq(y2),
           f = sq(x1) + sq(y1) - sq(x3) - sq(y3);

    double x = (1 / (a * d - b * c)) * (d * e - b * f),
           y = (1 / (a * d - b * c)) * (-c * e + a * f);

    double r = sqrt(sq(x - x1) + sq(y - y1));
    printf("%.3f %.3f %.3f\n", x, y, r);
  }

  return 0;
}