AtCoder Beginner Contest 189

コンテスト前のレート:1850
レート通りのパフォーマンスが得られる順位:491位(1500点、67分54秒)

A - Slot

問題

思考過程
  1. C_1=C_2かつC_2=C_3かどうかを判定する。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] c = sc.next().toCharArray();
        sc.close();

        if (c[0] == c[1] && c[1] == c[2]) {
            System.out.println("Won");
        } else {
            System.out.println("Lost");
        }
    }
}

ここまで0分52秒+0ペナ。297位。


B - Alcoholic

問題

思考過程
  1. 例1を見ると、普通に計算したのでは小数が出てくるので、誤差回避のため全て100倍して計算する。
  2. V_i \times P_iを足していって、X \times 100を超えた時点で何杯目かを出力する。
  3. V_i \times P_i \times NX \times 10010^8までしかいかないので、オーバーフローはしない。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] v = new int[n];
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            p[i] = sc.nextInt();
        }
        sc.close();

        x *= 100;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += v[i] * p[i];
            if (sum > x) {
                System.out.println(i + 1);
                return;
            }
        }
        System.out.println(-1);
    }
}

ここまで3分21秒+0ペナ。264位。


C - Mandarin Orange

問題
実行時間制限が1.5秒であることに気付いていなかった。

思考過程
  1. (l, r)を決めたら、xは範囲内のA_iの最小値。
  2. 制約が微妙な大きさだが、前から順に上手いこと情報を更新しながら見ていく必要があるか?
  3. いや、(l, r)の組を全探索するとして、N^2 \leq 10^8なので、ループの中身が軽ければ通りそう。
    工夫しようとしたらとても5分やそこらでできそうにはないので、TLEなら仕方ないと思ってこれでいくことにする。
  4. 念のため入力はScannerではなくBufferedReaderを使っておく。
  5. 個数は最小値\times皿数となるが、内側ループ内で最小値は逐次更新、皿数も念のため毎回計算ではなくインクリメントとしておく。 →159msで余裕だった。
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int min = a[i];
            int cnt = 0;
            for (int j = i; j < n; j++) {
                min = Math.min(min, a[j]);
                cnt++;
                int val = min * cnt;
                ans = Math.max(ans, val);
            }
        }
        System.out.println(ans);
    }
}

ここまで8分29秒+0ペナ。207位。


D - Logical Expression

問題

思考過程
  1. 最後が"AND"ならy_{N-1}x_Nが両方Trueである必要があって・・・などと動きを手作業で追ってみようとするが、面倒くさくなり、とりあえずDPを実装しようとしてみながら考える。
  2. dp[i][j] := i番目まで見て最後がjの場合の通り数」とする。
  3. S_i(0-indexed)が"AND"の場合、
    y_{i+1}Falseにするには、y_iFalseならx_{i+1}はどちらでもよいので2倍、y_iTrueならx_{i+1}False限定なのでそのままの値を加算。
    y_{i+1}Trueにするには、y_ix_{i+1}が共にTrueである必要があるので、y_i=Trueの通り数そのまま。
  4. S_iが"OR"の場合は逆のことをすればよい。
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = br.readLine();
        }
        br.close();

        long[] dp = new long[n + 1]; // 最後がFalseの通り数
        long[] dp1 = new long[n + 1]; // 最後がTrueの通り数
        dp[0] = 1;
        dp1[0] = 1;
        for (int i = 0; i < n; i++) {
            if (s[i].equals("AND")) {
                dp[i + 1] = dp[i] * 2 + dp1[i];
                dp1[i + 1] = dp1[i];
            } else {
                dp1[i + 1] = dp1[i] * 2 + dp[i];
                dp[i + 1] = dp[i];
            }
        }
        System.out.println(dp1[n]);
    }
}

ここまで15分24秒+0ペナ。178位。


E - Rotate and Flip

問題

思考過程
  1. 各操作を数式に変えてみる。
  2. 90度回転の方法はxyを入れ替えるような感じだった覚えがあったので、それを元に例1を見て符号を合わせる。
  3. 操作3については、(軸の位置)+(軸から元の位置までの距離)と考え、p+(p-x)となる。
    • 1:xy  y-x
    • 2:x-y  yx
    • 3:x2p-x  yy
    • 4:xx  y2p-y
       
  4. これらの操作を先にA_i回行っておけば、B_iが何であろうとO(1)で答えられる。
  5. 適当に上記4操作を組み合わせてみると、どのような組み合わせで操作を行っても、xA_i回操作した後の値は一次式で表せる。
  6. 答えのX座標をax+bの形とした場合、a\pm1のどちらか、bO(pM)くらいの値、xは操作前のX_{B_i}またはY_{B_i}となることがわかる。
     
  7. あとはクエリへの答え方。クエリをA_iでソートし、各クエリに対してA_iに達するまで操作を進めながら答えていくことを考えるが、「A_iに達するまで進める」というような管理が面倒だし、ソートすることで計算量悪化もするので、操作の履歴を全部持っておいて、クエリは普通に入力順に答えるようにした。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            x[i] = Integer.parseInt(sa[0]);
            y[i] = Integer.parseInt(sa[1]);
        }

        int m = Integer.parseInt(br.readLine());
        int[] ax = new int[m + 1]; // 答えのX座標をax+bとした時のa
        int[] ay = new int[m + 1]; // 答えのY座標をay+bとした時のa
        long[] bx = new long[m + 1]; // 答えのY座標をax+bとした時のb
        long[] by = new long[m + 1]; // 答えのY座標をay+bとした時のb
        boolean[] c = new boolean[m + 1]; // 答えのax+bのxにxを使うかyを使うか
        ax[0] = 1;
        ay[0] = 1;
        c[0] = true;
        for (int i = 0; i < m; i++) {
            String[] sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            if (t == 1) {
                ax[i + 1] = ay[i];
                ay[i + 1] = -ax[i];
                bx[i + 1] = by[i];
                by[i + 1] = -bx[i];
                c[i + 1] = !c[i];
            } else if (t == 2) {
                ax[i + 1] = -ay[i];
                ay[i + 1] = ax[i];
                bx[i + 1] = -by[i];
                by[i + 1] = bx[i];
                c[i + 1] = !c[i];
            } else {
                long p = Integer.parseInt(sa[1]);
                if (t == 3) {
                    ax[i + 1] = -ax[i];
                    ay[i + 1] = ay[i];
                    bx[i + 1] = 2 * p - bx[i];
                    by[i + 1] = by[i];
                } else {
                    ax[i + 1] = ax[i];
                    ay[i + 1] = -ay[i];
                    bx[i + 1] = bx[i];
                    by[i + 1] = 2 * p - by[i];
                }
                c[i + 1] = c[i];
            }
        }

        int q = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]);
            int b = Integer.parseInt(sa[1]) - 1;
            long vx = (long) (c[a] ? x[b] : y[b]) * ax[a] + bx[a];
            long vy = (long) (c[a] ? y[b] : x[b]) * ay[a] + by[a];
            pw.println(vx + " " + vy);
        }
        br.close();
        pw.flush();
    }
}

ここまで48分34秒+0ペナ。206位。



F問題は解けず。
それらしいDPを試みるが、振り出しに戻るところを正しく処理できず、例4が合うことなく終了。



終結果:ABCDEの5完、48分34秒、311位、パフォーマンス2050
レート変動:1850→1872(+22)


今回のFのような確率DPの問題、水diffくらいまでの比較的基本的なものならだいたいできるとは思うのだが、まだ苦手意識がある状態。
だいたいいつも正解者数の伸びはそれほど大きくなく、全体的に苦手な人が多い印象なので、克服できれば有利になれる分野になりそうだが・・・。

レートは、4ヶ月間くらい1700程度で安定 → 約1650まで落ちる → 5ヶ月間くらい1780程度で安定 → 約1640まで落ちる → 2ヶ月間くらい1860程度で安定 といった形で推移しているところで、とりあえずあともう2ヶ月間くらい今のレートを維持できるといいなという感じ。