新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

参加記録:AtCoder Regular Contest 036

[参加記録] AtCoder Regular Contest 036

コンテストURL

Welcome to AtCoder Regular Contest 036 - AtCoder Regular Contest 036 | AtCoder

結果

  • A, B問題の200点+C問題部分点10点の計210点
    • 最後ぎりぎりで部分点を取れたお陰で160位くらいから70位くらいに。
    • 4級になった!

プログラム

A問題
  • N日目における睡眠時間tiが与えられ、連続した3日間のtiの合計がK以下になる場合に寝不足になる
    • 寝不足になる場合は何日目になるか、ならない場合は-1を出力
  • 自分の解答は以下。
    • 単純に3連続のtiを足しただけ
    • 問題文を読み違えて尺取法みたいなのを実装しようとして変数名がlだったりします
public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Main().calc();
    }
    
    public void calc() {
        int N = in.nextInt();
        int K = in.nextInt();
        int[] t = new int[N];

        for (int i = 0; i < N; i++) {
            t[i] = in.nextInt();
        }

        int sum = 0;

        for (int l = 0; l < N - 2; l++) {
            sum = t[l] + t[l + 1] + t[l + 2];

            if (sum < K) {
                out.println(l + 3);
                out.close();
                return;
            }
        }
        
        out.println(-1);
        out.close();
    }
}
B問題
  • N個の各地点の高さhiが与えられる
    • s<=t<=uのときhs <= ... <= ht <= .. <= huとなる場合、(s, t, u)の組を山であるとする
    • このとき、最大の山の大きさu - s + 1(横幅)を求める
  • 自分の解答は以下。
    • 左右にどれだけ小さくなる値が連続するかを表すL[i], R[i]をそれぞれの地点について求める
    • L[i] + R[i] + 1の最大値で横幅を求められる
    • 解説だとtが端っこ or tの左右が自分より小さいときのみ計算する方法だったけどそれでO(N)なのか…
public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Main().calc();
    }

    public void calc() {
        int N = in.nextInt();
        int[] h = new int[N];

        for (int i = 0; i < N; i++) {
            h[i] = in.nextInt();
        }

        // 左/右に連続して小さくなっていく値がいくつ続いているか?
        // ex) 3 5 6 1 2 6 4
        //   L: 0 1 2 0 1 2 0
        //   R: 0 0 1 0 0 1 0
        int[] L = new int[N + 1];
        int[] R = new int[N + 1];

        int ans = 0;

        for (int i = N - 2; i >= 0; i--) {
            if (h[i] > h[i + 1]) {
                R[i] = R[i + 1] + 1;
            }
        }

        for (int i = 1; i < N; i++) {
            if (h[i - 1] < h[i]) {
                L[i] = L[i - 1] + 1;
            }
        }
        
        for (int i = 0; i < N; i++) {
            ans = Math.max(ans, L[i] + R[i] + 1);
        }

        out.println(ans);
        out.close();
    }
}
C問題
  • 0, 1, ?で構成されたN文字の文字列Sが与えられる
    • どの部分を取り出しても、含まれている0の個数と1の個数の差がK以下になるように、?に0か1を入れる
    • そのような文字列の個数はいくつあるか出力する
  • 自分の10点解答
    • 再帰で?に0と1を入れて全通りの文字列を作成
    • 各文字列の部分文字列を取り出して0と1の個数の差がK以下になるものを探索
    • 解説ではDPを使用。何回聞いてもDPはよくわからないなぁ…
public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Main().calc();
    }

    int N, K;
    char[] S;
    int ans = 0;

    void saiki(int n, char[] s) {
        if (n == N) {
            ans += test(s);
            return;
        }
        
        if (S[n] == '?') {
            s[n] = '0';
            saiki(n + 1, s);
            s[n] = '1';
            saiki(n + 1, s);
        }
        else {
            s[n] = S[n]; 
            saiki(n + 1, s);
        }
    }
    
    int test(char[] s) {
        int l, r = 0;
        for (l = 0; l < N; l++) {
            r = l;
            int one = 0;
            int zero = 0;
            while (r < N && Math.abs(one - zero) <= K) {
                if (s[r++] == '0') {
                    zero++;
                }
                else {
                    one++;
                }
            }
            
            if (Math.abs(one - zero) > K) {
                return 0;
            }
        }
        
        return 1;
    }

    public void calc() {
        N = in.nextInt();
        K = in.nextInt();
        S = in.next().toCharArray();
        
        char[] arg = new char[N];

        saiki(0, arg);

        out.println(ans);
        out.close();
    }
}