山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

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) とすると、

{
R(\theta)
= 
  \left[
    \begin{array}{rr}
          \cos \theta & -\sin \theta \\
          \sin \theta &  \cos \theta \\
    \end{array}
  \right]
}

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

{
R(\dfrac{\pi}{2})
= 
  \left[
    \begin{array}{rr}
          0 & -1 \\
          1  &  0 \\
    \end{array}
  \right]
= R_1 
}

を用いて、

\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);
 
 
    }
}

C - Triangular Relationship

よく分からなかったので、解説記事を探すと、分かりやすい記事がありました。

pyteyon.hatenablog.com

なるほどといった感じです。

感想

勉強不足だなと感じたコンテストでした。一度解いた問題をもう一度解き直したり、他のコードを見て学んだ方が良いのかなと思います。