seriruの技術屋ブログ

競技プログラミングやゲーム開発など技術に関することを発信します

AtCoder Beginner Contest 108

AtCoder Beginner Contest 108 に飛び入り参加しました。結果はA,Bの2完でした。難しかったですね...

A Pair

最初にK以下の整数を偶数と奇数に分割します。例えば K = 6 のとき、

偶数: 2, 4, 6 奇数: 1, 3, 5

となります。
求めるのは「偶数と奇数ひとつずつの組」なので、答えは (偶数の個数) * (奇数の個数) になります。

sample code :

Submission #3113127 - AtCoder Beginner Contest 108

B Ruined Square

座標の回転の問題です。様々な解法が考えられますが、今回は計算を簡単にするために複素数とベクトルを使って残りの座標を計算します。

まず、与えられた $P_1 (x_1, y_1) ,P_2 (x_2, y_2)$ が以下の図のようだったとします。

f:id:ryo_seriru:20180903021645p:plain

点は反時計回りに打つので、残りは図のようになります。
このとき、 $P_3$ は $P_1$ を $P_2$ を中心に $-90^{\circ}$ 回転させたものになっています。これを踏まえ、複素平面を利用して $P_1$ を $-90^{\circ}$ 回転させます。

その前準備として、各点を $z_i=x_i + iy_i$ $i=1,2,3,4$ と複素数に対応させます。
複素平面で $-90^{\circ}$ 回転させるのは, 点に $-i$ を掛けるのと同義です。
(なぜそうなるかは, 複素平面 - Wikipediaなどをご覧ください。)
よって、以下の等式が成り立ちます。

$-i(z_2 - z_1) = z_3 - z_2$

これを展開すると、

$x_3 + iy_3 = (x_2 + y_1 - y_2) + i(y_2 - x_1 + x_2)$

となります。従って、

$x_3 = x_2 + y_1 - y_2, y_3 = y_2 - x_1 + x_2$

と求められました。

同様に、 $P_4$ は $P_2$ を $P_1$ を中心に $90^{\circ}$ 回転させたものになっています。
これも計算すると、

$x_4 = x_1 + y_1 - y_2, y_3 = y_1 - x_1 + x_2$

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

sample code:

Submission #3126302 - AtCoder Beginner Contest 108

※この問題を解くに当たって多大なヒントを頂きました。 ⚡すく⚡さん、ありがとうございました。

こんな感じに考えました pic.twitter.com/R7Dusi2rWN
— ⚡すく⚡ (@0214sh7) September 2, 2018

Cは後で書きます＞＜