新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

参加記録:AtCoder Beginner Contest #16

[参加記録] AtCoder Beginner Contest #16

コンテストURL


Welcome to AtCoder Beginner Contest #016 - AtCoder Beginner Contest #016 | AtCoder

結果

  • 初めて全問完答!
    • なかなか嬉しいです。

プログラム

A問題
  • 月Mと日Dが与えられるので、MがDで割り切れればYES、そうでなければNOを出力。
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int M = scan.nextInt();
        int D = scan.nextInt();

        if (M % D == 0)
            System.out.println("YES");
        else
            System.out.println("NO");
        
        scan.close();
    }

}
B問題
  • 3つの数字A, B, Cが与えられるので、CがA+BかA-Bか判定
    • どちらかわからない場合は?、どちらでもない場合は!を出力する
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int A = scan.nextInt();
        int B = scan.nextInt();
        int C = scan.nextInt();

        int sum = A + B;
        int sub = A - B;
        
        if (C == sum && C == sub) {
            System.out.println("?");
        }
        else if (C == sum) {
            System.out.println("+");
        }
        else if (C == sub) {
            System.out.println("-");
        }
        else {
            System.out.println("!");
        }
        
        scan.close();
    }

}
C問題
  • ユーザ数NとM個の友達の組Ai, Biが与えられるので、各ユーザの「友達の友達」の数を求める
    • 「友達の友達」には自分自身と友達の数は含めない。
  • 自分の解答は以下。
    • リストの配列が作れないのを初めて知った…仕方がないので二次元配列を使う。
    • 各ユーザの友達(friendList[i][j])について見ていき、その友達の中で、自分自身もしくは自分の友達でない者をカウントしていく。
    • 意外に条件文が複雑になって結構間違えました。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int M = scan.nextInt();
        int[] A = new int[M];
        int[] B = new int[M];
        int[][] friendList = new int[N + 1][M];
        int[] index = new int[N + 1];

        for (int i = 0; i < M; i++) {
            A[i] = scan.nextInt();
            B[i] = scan.nextInt();
            friendList[A[i]][index[A[i]]++] = B[i];
            friendList[B[i]][index[B[i]]++] = A[i];
        }

        for (int i = 1; i <= N; i++) {
            List<Integer> friends = new ArrayList<Integer>();
            for (int j = 0; j < M; j++) {
                if (friendList[i][j] == 0)
                    break;

                for (int k = 0; k < M; k++) {
                    int cur = friendList[friendList[i][j]][k];

                    if (cur == 0) {
                        break;
                    }

                    if (cur == i || friends.contains(cur)) {
                        continue;
                    }

                    boolean flag = true;
                    for (int l : friendList[i]) {
                        if (l == 0) {
                            break;
                        }
                        if (l == cur) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        friends.add(cur);
                    }
                }
            }
            System.out.println(friends.size());
        }

        scan.close();
    }

}
  • コンテストの解説での解答は以下。
    • 友達か否かをbooleanの二次元配列で管理。
    • 自分と、自分と友達でない者を選んで、共通の友達を探す
    • 共通の友達がいる=友達の友達(ただし、自分自身でなく、自分の友達でもない)
    • こういう綺麗な解答ができるようになりたいですね。
package y141206.c;

import java.util.Scanner;

public class Test1 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int M = scan.nextInt();
        int[] A = new int[M];
        int[] B = new int[M];
        for (int i = 0; i < M; i++) {
            A[i] = scan.nextInt() - 1;
            B[i] = scan.nextInt() - 1;
        }
        boolean[][] connect = new boolean[N][N];
        for (int i = 0; i < M; i++) {
            connect[A[i]][B[i]] = true;
            connect[B[i]][A[i]] = true;
        }
        
        for (int i = 0; i < N; i++) {
            int ret = 0;
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                if (connect[i][j]) continue;
                for (int k = 0; k < N; k++) {
                    if (connect[i][k] && connect[j][k]) {
                        ret++;
                        break;
                    }
                }
            }
            System.out.println(ret);
        }
        
        scan.close();
    }

}
  • コンテスト解説の別解。
    • ワーシャルフロイド法とやらで、全頂点間の最短距離を求める。
    • 距離が2=友達の友達
    • グラフを与えられて距離を求めるような問題が毎回解けないので、後で見直そう
import java.util.Scanner;

public class Test2 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int M = scan.nextInt();
        int[] A = new int[M];
        int[] B = new int[M];
        for (int i = 0; i < M; i++) {
            A[i] = scan.nextInt() - 1;
            B[i] = scan.nextInt() - 1;
        }
        int[][] dist = new int[N][N];
        int MAX = 999999;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = MAX;
            }
            dist[i][i] = 0;
        }
        
        for (int i = 0; i < M; i++) {
            dist[A[i]][B[i]] = 1;
            dist[B[i]][A[i]] = 1;
        }
        
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            int ret = 0;
            for (int j = 0; j < N; j++) {
                if (dist[i][j] == 2) {
                    ret++;
                }
            }
            System.out.println(ret);
        }
        scan.close();

    }

}
D問題
  • 多角形の各頂点の座標(Xi, Yi)と、線分の端点の座標(Ax, Ay), (Bx, By)が与えられる
    • 線分によって多角形がいくつに分断されたか求める
    • 線分が多角形の辺に重なったり、多角形の内部で止まったりすることはない
  • 自分の解答は以下。
    • 幾何の問題はいつも見た瞬間投げていましたが、交点の数から答えが交点÷2+1で求められることには気づけたので、頑張ってみました
    • 多角形の各辺について、線分と交差するか判定し、交点の数を求める
    • 線分との交差判定については、途中まで考えましたが最終的にググってしまった。
    • 最後交点の数に1足しているのは、最後の辺(X[N-1], Y[N-1]), (X[0], Y[0])との判定をしていないので、その分を足しています
    • 今思えばnum % 2 == 1の判定は要らないような…
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        double Ax = scan.nextDouble();
        double Ay = scan.nextDouble();
        double Bx = scan.nextDouble();
        double By = scan.nextDouble();

        int N = scan.nextInt();
        double X[] = new double[N];
        double Y[] = new double[N];

        for (int i = 0; i < N; i++) {
            X[i] = scan.nextDouble();
            Y[i] = scan.nextDouble();
        }

        int num = 0;
        for (int i = 0; i < N - 1; i++) {
            if (((Ax - Bx) * (Y[i] - Ay) + (Ay - By) * (Ax - X[i]))
                    * ((Ax - Bx) * (Y[i + 1] - Ay) + (Ay - By)
                            * (Ax - X[i + 1])) < 0.0) {

                if (((X[i] - X[i + 1]) * (Ay - Y[i]) + (Y[i] - Y[i + 1])
                        * (X[i] - Ax))
                        * ((X[i] - X[i + 1]) * (By - Y[i]) + (Y[i] - Y[i + 1])
                                * (X[i] - Bx)) < 0.0) {
                    num++;
                }
            }
        }

        if (num % 2 == 1) {
            num++;
        }

        System.out.println(num / 2 + 1);
        scan.close();
    }

}