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

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

AtCoder Beginner Contest 021

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];
                }
            }
        }
    }
}