AtCoder Beginner Contest 107 の感想

問題

abc107.contest.atcoder.jp

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

A - Train

が答えとなります。

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

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

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

考え方

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

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

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

上記の距離に

の小さい方を足したものになります。

コード

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