AtCoder Beginner Contest 174

コンテスト前のレート：1820
レート通りのパフォーマンスが得られる順位：511位

A - Air Conditioner

問題
そこまで慌ててやってもいないとはいえ、動作確認せずに投げてもFirst ACの倍以上の時間がかかってる。

思考過程

1. かどうかを判定する。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        sc.close();

        if (x >= 30) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで0分32秒＋0ペナ。109位。

B - Distance

問題
2乗して比較することすら思いついていなかった。

思考過程

1. そのまんま、を計算（Math.hypot）し、と比較する。
2. double型で誤差が出るのはとか辺りからなので、この問題の制約では誤差は出ないはず。

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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int d = Integer.parseInt(sa[1]);
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            x[i] = Integer.parseInt(sa[0]);
            y[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (Math.hypot(x[i], y[i]) <= d) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ここまで3分00秒＋0ペナ。1059位。

C - Repsept

問題
数分考えてTLEになりそうな愚直解しか思いつかなかったので一旦飛ばす。
DとEを解いてからCとFを行ったり来たりして、だいぶ時間がかかったが一応通すことはできた。
Cを通すのが多少早かったところで、もはやパフォーマンスは大して上がりそうになかったので、Fが完全に行き詰るまではCに集中はしなかった。
ちなみに、解説の1行目の考察すらできておらず、完全に未証明なAC。

思考過程

1. 例２にある通り、が偶数の場合は。
2. がで割り切れるかどうかを愚直に試していくと、回の計算にもかかってしまい、になりそう。実際例３を試すと返って来ない。
3. がの倍数の場合も、のの位はやではないので。
4. 掛け算の筆算をイメージすると、となるは、下の桁から順に決めていけるのではないか。
   （、、、）
5. 掛け算の筆算の要領で、（はの下から桁目、はの桁数）と表せる。
6. を下から桁決めると、の下から桁まではで確定しているので、合計値は毎回下桁を捨てながら保持しておけばよく、保持する合計値は桁程度より増えることはない。
   これなら計算量はに定数倍が（上手くやればだが）とか付くくらいで、おそらくくらいな雰囲気なので間に合いそう。
7. 一応秒かけて見つからなければにする処理でも付けておこうかと思ったが、面倒なので付けずに提出し、通った。

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 k = Integer.parseInt(br.readLine());
        br.close();

        if (k % 2 == 0 || k % 5 == 0) {
            System.out.println(-1);
            return;
        }

        long now = 0;
        int ans = 0;
        while (true) {
            for (int i = 0; i <= 9; i++) {
                long val = now + k * i; // K * Xの下から何桁目かまでの合計

                // ALL'7'なら終了
                String s = String.valueOf(val);
                boolean flg = true;
                for (int j = 0; j < s.length(); j++) {
                    if (s.charAt(j) != '7') {
                        flg = false;
                        break;
                    }
                }
                if (flg) {
                    ans += s.length();
                    System.out.println(ans);
                    return;
                }

                // 下1桁が7の場合
                if (s.charAt(s.length() - 1) == '7') {
                    now = val / 10; // 下1桁捨てる
                    ans++;
                    // ここにbreakがあった方がいいけど忘れてる
                }
            }
        }
    }
}

ABDECと解いた時点で85分22秒＋2ペナ。1697位。

D - Alter Altar

問題
しょうもない実装ミスで1ペナ。

思考過程

1. 途中まで全部R、途中から全部Wにすることを目指す。
2. 一番前のWと一番後ろのRを入れ替える、ということを繰り返せば、色を変えるより損することはなさそう。
3. インデックスを上手く動かしながら、「一番前のW一番後ろのR」である限り処理を続ける。

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());
        char[] s = br.readLine().toCharArray();
        br.close();

        int ans = 0;
        int w = 0;
        int r = n - 1;
        while (w < r) {
            while (w < n && s[w] == 'R') {
                w++;
            }
            while (r >= 0 && s[r] == 'W') { // r <= 0になっていて1ペナ
                r--;
            }
            if (w < r) {
                ans++;
                w++;
                r--;
            }
        }
        System.out.println(ans);
    }
}

ABDと解いた時点で15分12秒＋1ペナ。511位。

E - Logs

問題
制約をちゃんと見ましょう。

思考過程

1. どの丸太を何回ずつ切るか、個を個に割り振る組み合わせを全探索するのは全然間に合わない。
2. 回切る場合に各丸太を何回ずつ切るかが決まっているとして、それを回にした場合、回の場合で一番長い丸太の切断回数を回増やすのが最適。
3. 各丸太について、切断回数と、回切断した場合の長さを持たせておき、の降順のPriorityQueueに入れて、回処理すればいいのでは。　→よく見たらはではなくだったのでTLE
   　
4. 答えを決め打ちすれば、各丸太を何回切ればいいかがわかるので、その合計が以下であるかどうかを調べる。
5. 答えの二分探索を行う。全体で。

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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int k = Integer.parseInt(sa[1]);
        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 ok = 1000000000;
        int ng = 0;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (count(a, mid) <= k) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        System.out.println(ok);
    }

    static long count(int[] a, int val) {
        long cnt = 0;
        for (int i = 0; i < a.length; i++) {
            cnt += (a[i] - 1) / val;
        }
        return cnt;
    }
}

ABDEと解いた時点で36分44秒＋2ペナ。792位。

F - Range Set Query（2020/8/3追記）

問題
解けず。色が26種類しかない（英小文字からなる文字列で同様のことをする）問題を見たことがある気がして、そこから何かヒントをつかめないかと思ったが、その過去問が見つからず。ABC-Eになかったっけ・・・。
クエリをかの順に並び替えることは一瞬思いついたが、ちゃんと深掘りできず。

（2020/8/3追記）
解説見て解いたので追記。

思考過程

1. 解説通り以下の処理を行う。
   1. 各色についてつ前の位置を保持しておく配列を作成する。
   2. クエリをでソートした後、BITを使いながらの小さい順にクエリに答えていく。
   3. クエリを入力順に再ソートした後、答えを出力する。
      　→TLE。多分時間制限3秒なら通ると思うのだが・・。
      　
2. 解法は合っているはずなので、定数倍改善を考える。
   1. 上記1-1の配列作成を入力と同時に行ったり、Mapではなく配列を使ったりしてみる。
   2. クエリを全部配列に格納してからソートするのではなく、PriorityQueueを使う。
   3. 結果出力のための再ソートを省略するため、別のソートしない配列にもクエリを格納しておく。
      　→AC。上記1は多分あまり意味ないが、2と3で600msずつくらい縮まってる気がする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;

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

        sa = br.readLine().split(" ");
        int[] pre = new int[n + 1]; // 1つ前の同色の位置
        int[] last = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int c = Integer.parseInt(sa[i]);
            pre[i + 1] = last[c];
            last[c] = i + 1;
        }

        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.r - o2.r); // クエリ回答用
        Obj[] arr = new Obj[q]; // 結果出力用
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.i = i;
            o.l = Integer.parseInt(sa[0]);
            o.r = Integer.parseInt(sa[1]);
            que.add(o);
            arr[i] = o;
        }
        br.close();

        BIT bit = new BIT(n);
        int j = 1;
        while (!que.isEmpty()) {
            Obj o = que.poll();
            while (j <= o.r) {
                bit.add(j, 1);
                if (pre[j] > 0) {
                    bit.add(pre[j], -1);
                }
                j++;
            }
            o.ans = bit.sum(o.r) - bit.sum(o.l - 1);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            pw.println(arr[i].ans);
        }
        pw.flush();
    }

    static class Obj {
        int i, l, r, ans;
    }

    // 以下ライブラリ

    static class BIT {
        int n;
        int[] arr;

        public BIT(int n) {
            this.n = n;
            arr = new int[n + 1];
        }

        void add(int idx, int val) {
            for (int i = idx; i <= n; i += i & -i) {
                arr[i] += val;
            }
        }

        int sum(int idx) {
            int sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += arr[i];
            }
            return sum;
        }
    }
}

最終結果：ABCDEの5完、95分22秒、1804位、パフォーマンス1262
レート変動：1820→1775

DとEでミスがなく、Fに浮気せずCを解けば40分くらいでパフォ1450くらいだったかもしれないが、それでもレートへのダメージはそんなに大して変わらないし、無理矢理にでもCを通せただけマシだったかと思う。緑diff落とすのはもうやだ。

F問題は仕方ないとも思ったけど、水diffで辛い。ABCで水diff落としたのはABC151以来の約7か月ぶり。AGCでは落としてるけど。