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

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

AtCoder Beginner Contest 107 の感想

問題

abc107.contest.atcoder.jp

今回はC問題まで解くことができました。レートを意識するならば早解きとWAを出さないことが大事ですが、当面はC問題を解けるかどうかを意識したいです。

A - Train

 N - i + 1 が答えとなります。

直ぐに式が思いつかなくても、数値例を見ると式が思い浮かびますね。

B - Grid Compression

実装系の問題です。ある行か列の全てが'.' であれば、その行または列を取り除きます。

コードが酷いですが、きれいな書き方が思い浮かびませんでした。

コード

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

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int H = scan.nextInt();
        int W = scan.nextInt();
        char [][]a = new char[H][W];
        String []k = new String[H];
        for(int i = 0; i < H; i++) {
            String s = scan.next();
            k[i] = s;
            for(int j = 0; j < W; j++) {
                a[i][j] = s.charAt(j);
            }
        }
        scan.close();

        List<String> list = new ArrayList<String>();
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                char c = k[i].charAt(j);
                if(c == '#') {
                    list.add(k[i]);
                    break;
                }
            }
        }
        int h = list.size();
        char [][]b = new char[h][W];
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < W; j++) {
                b[i][j] = list.get(i).charAt(j);
            }
        }
        List<String> list2 = new ArrayList<String>();
        for(int j = 0; j < W; j++) {
            for(int i = 0; i < h; i++) {
                if(b[i][j] == '#') {
                    String d = "";
                    for(int m = 0; m < h; m++) {
                        d += b[m][j];
                    }
                    list2.add(d);
                    break;
                }
            }
        }
        char [][]e = new char[h][list2.size()];
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < list2.size(); j++) {
                e[i][j] = list2.get(j).charAt(i);
            }
        }
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < list2.size(); j++) {
                System.out.print(e[i][j]);
            }
            System.out.println();
        }
    }
}

C - Candles

累積和を使う問題だと思ったんですが、解説を見るとその必要はないみたいですね。

累積和については、

累積和 - yukicoder Wiki

が分かりやすいとおもいます。

考え方

まず初めに、隣り合うロウソクの距離を格納した配列  y_i を用意します。この配列のサイズは  N - 1 となります。

この  y の累積和の配列を  B とします。 K 本のロウソクを付けるときに歩く距離は、原点にいることを無視し、 i から  i + K - 1 番目のロウソクに付けるとすると、

 B_{i + K - 1} - B_{i}

となります。原点から歩く距離を考慮すると、

上記の距離に

 | x_i |, | x_{i + K - 1} | の小さい方を足したものになります。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        long []x = new long[N];
        for(int i = 0; i < N; i++) {
            long t = scan.nextLong();
            x[i] = t;
        }
        scan.close();
        if(N == 1) {
            System.out.println(Math.abs(x[0]));
            System.exit(0);
        }
        if(K == 1) {
            long min = Math.abs(x[0]);
            for(int i = 0; i < N; i++) {
                if(min < Math.abs(x[i])) {
                    min = Math.abs(x[i]);
                }
            }
            System.out.println(min);
            System.exit(0);
        }
        long []y = new long[N - 1];
        for(int i = 0; i < N - 1; i++) {
            y[i] = Math.abs(x[i + 1] - x[i]);
        }
        long []B = new long[N];
        B[0] = 0;
        for(int i = 1; i < N; i++) {
            B[i] = y[i - 1] + B[i - 1];
        }
        long min = Long.MAX_VALUE;
        for(int i = 0; i <= N - K; i++) {
            long t = B[i + K - 1] - B[i] + Math.min(Math.abs(x[i]), Math.abs(x[i + K - 1]));
            if(min > t) {
                min = t;
            }
        }
        System.out.println(min);
    }
}

感想

B問題で時間がいつもよりかかってしまったので、早く解けるように訓練する必要があると思います。

また、C問題も解法はすぐに思いついたんですが、実装とケアレスミスがあったので、結果的に時間をロスしてしまいました。累積和についてまた確認しようと思います。