AtCoder Beginner Contest 108 の感想 - ヤマカサのプログラミング勉強日記

問題

abc108.contest.atcoder.jp

今回はB問題まで解くことができました。4月からAtCoderを始めたんですが、成長が見られません。

A - Pair

$[ 1, K]$ の区間に含まれる偶数と奇数の個数を考えます。 $K$ が偶数ならば、奇数の数と偶数の数は $\dfrac{K}{2}$ 個あります。 $K$ が奇数ならば、奇数の数は $\dfrac{K+1}{2}$ 個であり、偶数の数は $\dfrac{K - 1}{2}$ 個あります。

求める答えは、奇数の数と偶数の数を掛けた値となります。

B - Ruined Square

ベクトルの座標と頂点の座標を勘違いしたので、相当時間を使いました。

yukicoderで似たような問題を解いたことがあるので、解法は知っているつもりだったんですがね。その問題が下です。

No.55 正方形を描くだけの簡単なお仕事です。 - yukicoder

考え方

yukicoderの問題の解説しているサイトの方針が役に立ちます。

yukicoder No.55 - 正方形を描くだけの簡単なお仕事です。 - ゲームにっき（仮）別館（仮）

反時計回りに正方形の頂点が存在しているということなので、求める頂点は一意に決まることが分かります。

ここで、正方形ABCDの頂点を

$A = (x_1, y_1)$ , $B = (x_2, y_2)$ , $C = (x_3, y_3)$ , $D = (x_4, y_4)$

とします。

$\overrightarrow{AB}$ を $90^\circ$ 回転させたベクトルが $\overrightarrow{AD}$ となります。

座標の回転は、回転行列を用いて計算することができます。回転行列について、

回転行列 - Wikipedia

を参考にします。回転行列を $R(\theta)$ とすると、

となります。したがって、 $\theta = \dfrac{\pi}{2}$ のとき

を用いて、

$\overrightarrow{AD} = R_1\overrightarrow{AB}$

となります。座標Dは、 $\overrightarrow{OD}$ なので、上記より、

$\overrightarrow{OD} - \overrightarrow{OA} = R_1\overrightarrow{AB}$

$\overrightarrow{OD} = R_1\overrightarrow{AB} + \overrightarrow{OA}$

同様にして、 $\overrightarrow{DC}$ は $\overrightarrow{DA}$ を $90^\circ$ 回転させたベクトルとなります。

コード

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x1 = scan.nextInt();
        int y1 = scan.nextInt();
        int x2 = scan.nextInt();
        int y2 = scan.nextInt();
        scan.close();
        //int l = (int)Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        int v1x = x2 - x1;
        int v1y = y2 - y1;
        int x4 = -v1y + x1;
        int y4 = v1x + y1;
        int v2x = x1 - x4;
        int v2y = y1 - y4;
        int x3 = -v2y + x4;
        int y3 = v2x + y4;
 
        System.out.println(x3 + " " + y3 + " " + x4 + " " + y4);
 
 
    }
}