AtCoder Beginner Contest 106 の感想 - ヤマカサのプログラミング勉強日記

問題

今回はC問題まで解くことができました。

Tasks - AtCoder Beginner Contest 106

A - Garden

数学の問題です。

縦と横に幅 $1$ yard の道があるので、全体の面積からその部分を引けばよいです。

$AB - A - B + 1$

が答えになります。 $+ 1$ となっているのは、道の面積を引く上で重なっている部分が $1$ となるので、余分に引いた分を足しています。

B - 105

素直に全探索しました。

C - To Infinity

問題文を良く読めば簡単な問題です。

S において、S の先頭から $1$ が連続する個数を $a$ とします。例えば、S = 11532 ですと、 $a = 2$ です。また、S = 82111 だと $a = 0$ です。

$a \leq K$ のとき、答えは1で、それ以外の場合は $S$ の 1以外の数字が左から初めて現れる数字です。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String S = scan.next();
        long K = scan.nextLong();
        scan.close();
        int l = S.length();
        int []num = new int[S.length()];
        for(int i = 0; i < l; i++) {
            num[i] = Integer.parseInt(S.substring(i, i + 1));
        }

        long sum = l;
        if(sum >= K) {
            int cnt1 = 0;
            for(int i = 0; i < l; i++) {
                if(num[i] == 1) {
                    cnt1++;
                }else {
                    break;
                }
            }
            if(cnt1 >= K) {
                System.out.println(1);
                System.exit(0);
            }
        }

        int ans = 0;
        for(int i = 0; i < l; i++) {
            if(num[i] != 1) {
                ans = num[i];
                break;
            }
        }
        System.out.println(ans);

    }
}

D - AtCoder Express 2

多分、二次元累積和の典型問題です。

二次元の累積和については、

paiza.hatenablog.com

が分かりやすいと思います。

なぜ二次元で考えたかというと、入力例1 の列車の状況は下の図のようになっています。

f:id:yamakasa3:20180819040042p:plain

この例では $[ 1, 2]$ の範囲の列車の数を数えるということですが、図のように一次元で考えるとどのようにして数え上げれば良いのか、僕には分かりませんでした。それと、範囲を超えたときの処理をどうするのかを考えると難しいと思います。

二次元配列を $A_{L, R}$ として、 $A_{L, R}$ の値は、区間 $[ L, R]$ に存在する列車の数を表すとします。

求める答えは、 $A_{p, p}$ , $A_{p, q}$ , $A_{q, p}$ , $A_{q, q}$ を頂点とする四角形の内部の $A_{i, j}$ を足し上げることで求められます。この求め方を高速にやるために、二次元累積和を使います。

コード

import java.util.Scanner;

public class ProblemD {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int Q = scan.nextInt();
        int [][]A = new int[N + 1][N + 1];
        for(int i = 0; i < M; i++) {
            int L = scan.nextInt();
            int R = scan.nextInt();
            A[L][R] ++;
        }
        int [][]B = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                B[i][j] += A[i][j] + B[i][j - 1];
            }
        }
        int [][]C = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                C[j][i] += B[j][i] + C[j-1][i];
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < Q; i++) {
            int p = scan.nextInt();
            int q = scan.nextInt();
            int cnt = C[q][q] - C[q][p - 1] - C[p - 1][q] + C[p - 1][p - 1];
            sb.append(cnt).append("\n");
        }
        scan.close();
        System.out.println(sb.toString());

    }
}

感想

D問題は、TLEとなる解法はコンテスト中に思いついたんですが、おそらく二次元のいもす法を使うんだと思い調べてる最中に、タイムアップとなりました。