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

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

AtCoder Beginner Contest 109 の感想

AtCoder Beginner Contest 109

Tasks - AtCoder Beginner Contest 109

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

f:id:yamakasa3:20180909012236p:plain

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

A - ABC333

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

 A \times B が奇数であれば、”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

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

考え方

 x_i を昇順に並び替えます。

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

 L_i = x_{i + 1} - x_{i}

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

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

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

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

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

コード

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

感想

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