AtCoder Beginner Contest 109 の感想

AtCoder Beginner Contest 109

Tasks - AtCoder Beginner Contest 109

今回はC問題まで解くことができました。AtCoderを始めてから5ヶ月が経過しましたが、成長が感じられません。パフォーマンスも安定してないしね。

それでは、振り返っていきます。

A - ABC333

なんか投げやりな問題ですね。

が奇数であれば、”Yes”、偶数であれば"No"です。

B - Shiritori

しりとりが完成しているかどうかを調べる問題です。入力された文字に重複がないことと、それぞれの文字の先頭と末尾をチェックします。

コード

import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;
 
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        Set<String> set = new LinkedHashSet<String>();
        String[] W = new String[N];
        for(int i = 0; i < N; i++) {
            String t = scan.next();
            set.add(t);
            W[i] = t;
        }
        scan.close();
        if(N != set.size()) {
            System.out.println("No");
            System.exit(0);
        }
        char c = W[0].charAt(W[0].length() - 1);
        for(int i = 1; i < N; i++) {
            if(c != W[i].charAt(0)) {
                System.out.println("No");
                System.exit(0);
            }
            c = W[i].charAt(W[i].length() - 1);
        }
        System.out.println("Yes");
    }
}

C - Skip

解説の解き方と若干違いますが、僕のはソートをしている分効率が悪かったですね。

考え方

を昇順に並び替えます。

以降では昇順に並び替えたものとして考えます。次の数列 を考えます。

各都市を訪れるための歩幅が に該当するわけですが、都市をまたいで別の都市に到着することはできません。

例えば、 から へと一歩で動くことは考えなくて良いということです。ここで、 を無視して、最初に に居るとします。この時の歩幅 の最大値は の最大公約数になります。

公約数ではない場合、通り越してしまう都市が存在することになります。 の最小値は なので、 以外で考えます。

数列 の最大公約数を とします。位置 から へと行くことができれば、答えは になります。そうでない場合、答えは です。

その調べ方は、 が の倍数であるかどうかをチェックすればよいです。一つでも倍数となるものがあれば、 からその都市へ行くことができます。

コード

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int N = scan.nextInt();
        int X = scan.nextInt();
        int[]x = new int[N];
        for(int i = 0; i < N; i++) {
            x[i] = scan.nextInt();
        }
        scan.close();
        if(N == 1) {
            int ans = Math.abs(X - x[0]);
            System.out.println(ans);
            System.exit(0);
        }else if(N == 2) {
            int l = Math.abs(x[0] - x[1]);
            int l1 = Math.abs(x[0] - X);
            int l2 = Math.abs(x[1] - X);
            if(l1 % l != 0 && l2 % l != 0) {
                System.out.println(1);
            }else {
                System.out.println(l);
            }
            System.exit(0);
        }
        Arrays.sort(x);
        int[] k = new int[N - 1];
        for(int i = 0; i < N - 1; i++) {
            k[i] = x[i + 1] - x[i];
        }
        int g = gcd(k[0], k[1]);
        for(int i = 2; i < N - 1; i++) {
            g = gcd(g, k[i]);
        }
 
        int m = g;
        int []r = new int[N];
        for(int i = 0; i < N; i++) {
            r[i] = Math.abs(X - x[i]);
        }
 
        for(int i = 0; i < N; i++) {
            if(r[i] % m != 0) {
                System.out.println(1);
                System.exit(0);
            }
        }
        System.out.println(m);
 
 
    }
    static int gcd(int m, int n) {
        if(m < n) return gcd(n, m);
        if(n == 0) return m;
        return gcd(n, m % n);
    }
}

D - Make Them Even

実装系の問題です。解説を見て理解しました。

表を一筆で塗りつぶすように探索をしていきます。そして、奇数となる要素を集めます。最後に奇数から奇数へのパスを列挙します。そんな感じです。

コード

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int H = scan.nextInt();
        int W = scan.nextInt();
        int[][]a = new int[H][W];
        int cnt = 0;
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                int t = scan.nextInt();
                a[i][j] = t;
                if(t % 2 == 1) {
                    cnt++;
                }
            }
        }
        scan.close();
        StringBuilder sb = new StringBuilder();
        int[][] list = new int[H * W][2];
        int[] list2 = new int[cnt];
        int index = 0;
        int cnt2 = 0;
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                int k = 0;
                if(i % 2 == 1) {
                    k = W - j - 1;
                }else {
                    k = j;
                }
                if(a[i][k] % 2 == 1) {
                    list2[cnt2] = index;
                    cnt2 ++;
                }
                list[index][0] = i;
                list[index][1] = k;
                index++;
            }
        }
        int l = cnt;
        if(cnt % 2 == 1) {
            l --;
        }
        int n = 0;
        for(int i = 0; i < l; i+=2) {
            for(int j = list2[i]; j < list2[i+1]; j++) {
                int a1 = list[j][0] + 1;
                int a2 = list[j][1] + 1;
                int a3 = list[j+1][0] + 1;
                int a4 = list[j+1][1] + 1;
                sb.append(a1 + " " + a2 + " " + a3 + " " + a4);
                sb.append("\n");
                n++;
            }
        }
        System.out.println(n);
        System.out.println(sb.toString());
    }
}

感想

そんな難しい問題はなかったと思いましたが、結果には表れませんでした。頑張って競技プログラミングの問題を解いていますが、結果に表れないと苦しいです。