AtCoder Beginner Contest 230(Rated範囲外)

コンテスト前のレート：2028
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：268位（1500点、21分46秒）

A - AtCoder Quiz 3

問題

思考過程

1. が桁までしかないので、ならした値を"AGC0"に連結すればよさそう。
2. と思って提出しようとスクロールしたら例３が目に入り、の場合に"0"を増やす処理を追加する。

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();
        sc.close();

        String s = "AGC0";
        if (n < 10) {
            s += "0";
        }
        if (n >= 42) {
            n++;
        }
        System.out.println(s + n);
    }
}

ここまで1分59秒＋0ペナ。397位。

B - Triple Metre

問題

思考過程

1. 場合分け等頑張らなくても、StringのindexOfメソッドを使えば、部分文字列であるかどうかを調べられる。
2. の長さは最大文字しかないので、は"oxx"を個も結合しなくても、個くらいで足りる。
3. （"oxxoxx..."の場合と"xoxxoxx..."の場合を考えれば個で足りることがわかるが、明らかに大は小を兼ねる構造をしているものを本番でギリギリを攻めようとも思わないので）念のため少し多めに繋げておく。

import java.util.Scanner;

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

        String t = "oxxoxxoxxoxxoxxoxxoxx";
        if (t.indexOf(s) != -1) {
            System.out.println("Yes");
        } else 
            System.out.println("No");
    }
}

ここまで3分23秒＋0ペナ。76位。

C - X drawing

問題
問題の内容が全然頭に入ってこないし、ノリで判定を書き始めたら全然合わないし、とを間違えるし、散々だった。
30分以上かけて解けず一旦飛ばしてDへ。
Eまで解いてから戻ってきた後、冷静に式を立て直したら今度は5分ほどで解けた。

思考過程

1. 例１について問題文の操作を手作業で行ってみると、要するにを中心とした×印が、のマス目の途中で終わらずに端まで続いている形になっており、そのようなフィールドの一部分を長方形に切り取るらしいことがわかる。
   　
2. 切り取る長方形領域が例えばより右下の方にあるとすると、長方形の上辺か左辺のどこから入ってくるかがわかれば、そこから右下に塗っていけばいいが、右下に限定しても簡単には立式できず、実際にはさらに場合分けが山ほどありそうなのでなんか難しそう。
3. 長方形内の全マスについて、×印の部分に当たっているか判定する方針で考える。
   　
4. をからではなくからの位置に直したら、これにループカウンタを足して、の場合に黒？　上手くいかないからどこか符号逆だったかな？　などと数式ガチャを数十分続ける。
   　
5. 冷静に考え直すと、長方形内で注目しているマスの座標はと表すことができ、これが操作１のマスに該当するとすると、が成り立つことになる。
6. これは と に変形できるので、ならば黒とする。
7. 操作２も上記5.のをに変えて同様。

ソース内入力部分のは、から始まる座標で考えようとした結果だが、上記の式から判定する上では意味がなかった。

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long a = sc.nextLong() - 1;
        long b = sc.nextLong() - 1;
        long p = sc.nextLong() - 1;
        long q = sc.nextLong();
        long r = sc.nextLong() - 1;
        long s = sc.nextLong();
        sc.close();

        int h = (int) (q - p);
        int w = (int) (s - r);
        char[][] ans = new char[h][w];
        for (int i = 0; i < h; i++) {
            Arrays.fill(ans[i], '.');
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // a + k == p + i
                // b + k == r + j
                if (p + i - a == r + j - b) {
                    ans[i][j] = '#';
                }
                // a + k == p + i
                // b - k == r + j
                if (p + i - a == b - r - j) {
                    ans[i][j] = '#';
                }
            }
        }
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < h; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }
}

ABDECと解いた時点で68分45秒＋1ペナ。887位。

D - Destroyer Takahashi

問題
区間スケジューリング問題とほぼ同様。

思考過程

1. でソートし、左から調べていって、まだ壊れていない壁があればその壁の右端からの列にダメージを与える。ということを貪欲に繰り返す。
2. 壊せている範囲の更新の際、ズレるといったことがないように気を付ける。例１で最初の壁を壊した時に、まで壊したことになるように帳尻を合わせる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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]);
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.l = Integer.parseInt(sa[0]);
            o.r = Integer.parseInt(sa[1]) + 1;
            arr[i] = o;
        }
        br.close();

        Arrays.sort(arr, (o1, o2) -> o1.r - o2.r);
        int ans = 0;
        int now = 0;
        for (Obj o : arr) {
            if (now < o.l) {
                ans++;
                now = o.r + d - 2;
            }
        }
        System.out.println(ans);
    }

    static class Obj {
        int l, r;
    }
}

ABDと解いた時点で41分37秒＋0ペナ。1051位。

E - Fraction Floor Sum

問題
とりあえず無理矢理通しただけという感じ。

思考過程

1. の範囲は普通に計算し、それ以降はの値が同じになるが複数個になっていくので、それが何個になるのかを求めたい。
2. 書き出してみると、例えばではであり、前からまでは普通に計算、残りは後ろからが個、が個という形になっている。
3. ところがによっては何故か、が個というところを前半と後半の処理で二重カウントしたり、どちらもカウントしなかったりしてしまう。
4. ソース内つ目のfor文の抜け方を試行錯誤するが、WA。
5. 後半の処理を合計が個になるまで行うというやっつけロジックで帳尻を合わせてなんとかAC。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

        List<Long> list = new ArrayList<>();
        long ans = 0;
        long sum = 0;
        for (long x = 1; ; x++) {
            long v = n / x;
            list.add(v);
            if (x * x > n) {
                break;
            }
            ans += v;
            sum = x;
            if (x * x == n) {
                break;
            }
        }
        for (int i = 1; i < list.size(); i++) {
            long d = list.get(i - 1) - list.get(i);
            sum += d;
            ans += i * d;
            if (sum == n) {
                break;
            }
        }
        System.out.println(ans);
    }
}

ABDEと解いた時点で62分20秒＋1ペナ。882位。

残り時間は、一応FとGを両方見つつも、Gが解けそうになかったのでF寄りで費やす。
区間和でが出てこなければ通りかなとは思いつつ、が出てくるとどれだけ重複するのかはよくわからず。
DPも考えはしていたけど遷移わからん。

最終結果：ABCDEの5完1500点、73分45秒、936位、パフォーマンス1393相当
レート変動：2028（Unrated）

Cで冷静になれなかったのと、Eを貼るだけにできていなかったのが敗因かなという感じ。
そこまでできていても、CやDの問題を読むだけでだいぶ時間取られているので21分はかなり厳しいが。

Fを解ければ挽回できたんだし、昔から言ってるけどやっぱりDPが弱いのもなんとかしないと。