AtCoder Beginner Contest 021

AtCoderの過去問をやっています。20回目のC問題が理解できないので、次の21回目の問題を解いていきます。

A - 足し算

二進数に変換し、 $1$ が立っているビットを出力します。

コード

import java.util.ArrayList;
import java.util.Scanner;

public class ProblemA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        scan.close();
        String bin =  Integer.toBinaryString(N);

        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i < bin.length(); i++) {
            char c = bin.charAt(i);
            if(c == '1') {
                list.add((int)Math.pow(2, i));
            }
        }
        System.out.println(list.size());
        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

B - 嘘つきの高橋くん

隣接グラフとかを作るのかなと思ったんですが、B問題でそのような問題が出るとは思えないので、紙に書いて考えてみると見えてきました。

始点、終点、途中の町が被らなければ最短経路が存在します。なので、HashSetを使いサイズが小さくなるかどうかを見て解答を作りました。

コード

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int a = scan.nextInt();
        int b = scan.nextInt();
        int K = scan.nextInt();
        //int[] P = new int[K];
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < K; i++) {
            set.add(scan.nextInt());
        }

        scan.close();

        if(set.size() == K) {
            if(set.contains(a) || set.contains(b)) {
                System.out.println("NO");
            }else {
                System.out.println("YES");
            }
        }else {
            System.out.println("NO");
        }
    }
}

C - 正直者の高橋くん

深さ優先探索をするのかなと思ったんですが、調べてみるとワ―シャルフロイド法？やダイクストラ法で解けるようです。まだ勉強してないので、他の方法で考えることにしました。

通るとは思わなかったんですが、隣接行列の累乗を求めることで正解となりました。

隣接行列 - Wikipedia

コード

import java.util.Scanner;

public class ProblemC {
    static int N;
    static int a;
    static int b;
    static int q = 1000000007;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        a = scan.nextInt() - 1;
        b = scan.nextInt() - 1;
        int M = scan.nextInt();

        int [][]A = new int[N][N];
        int [][] B = new int[N][N];
        for(int i = 0; i < M; i++) {
            int x = scan.nextInt() - 1;
            int y = scan.nextInt() - 1;
            A[x][y] = 1;
            A[y][x] = 1;
            B[x][y] = 1;
            B[y][x] = 1;
        }
        scan.close();

        int [][] C = new int[N][N];
        for(int l = 0; l < N; l++) {
            if(B[a][b] != 0) {
                System.out.println(B[a][b]);
                System.exit(0);
            }
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    int t = 0;
                    for(int k = 0; k < N; k++) {
                        t += B[i][k] * A[k][j];
                    }
                    t = t % q;
                    C[i][j] = t;
                }
            }
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    B[i][j] = C[i][j];
                }
            }
        }
    }
}