AtCoder Beginner Contest 240(Rated範囲外)

ABC

コンテスト前のレート：2060
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：260位（2000点、59分23秒）

A - Edge Checker

問題

思考過程
  1. a+1=bまたはa=1, b=10の場合"Yes"。
import java.util.Scanner;

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

        if (a + 1 == b || a == 1 && b == 10) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分02秒＋0ペナ。100位。


B - Count Distinct Integers

問題

思考過程
  1. a_iを全部Setに入れて要素数を答える。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(sc.nextInt());
        }
        sc.close();

        System.out.println(set.size());
    }
}

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


C - Jumping Takahashi

問題

思考過程
  1. i-1回時点であり得る座標の集合Sが求まっているとすると、i回目時点ではSの各要素+a_iと+b_iがあり得る。
  2. この集合SをSetで管理することにする。
  3. Xを超える値は保持している必要がないので、データ量をO(X)に抑えるため格納しないことにする。（O(Nb)が十分小さいのでそこまでする必要はなかった）
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        sc.close();

        Set<Integer> set = new HashSet<>();
        set.add(0);
        for (int i = 0; i < n; i++) {
            Set<Integer> wk = new HashSet<>();
            for (int e : set) {
                if (e + a[i] <= x) {
                    wk.add(e + a[i]);
                }
                if (e + b[i] <= x) {
                    wk.add(e + b[i]);
                }
            }
            set = wk;
        }
        if (set.contains(x)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで4分07秒＋0ペナ。64位。


D - Strange Balls

問題

思考過程
  1. スタックのようなデータ構造（末尾の要素しか削除しないのでListでも計算量は増えない）で管理しながらシミュレーションを行う。
  2. ただし、ボールの個数分の要素を積み上げていると、末尾から個数を数えるのに計算量がかかってしまうため、＜値、個数＞の形で保持するようにする。
import java.io.PrintWriter;
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);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        List<Obj> list = new ArrayList<>();
        int total = 0;
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            // リストが空か、末尾の値が異なる場合
            if (list.isEmpty() || list.get(list.size() - 1).a != a[i]) {
                Obj o = new Obj();
                o.a = a[i];
                o.c = 1;
                list.add(o);
                total++;
            // 末尾の値が同じ場合
            } else {
                Obj o = list.get(list.size() - 1);
                o.c++;
                total++;
                if (o.c == a[i]) {
                    list.remove(list.size() - 1);
                    total -= a[i];
                }
            }
            pw.println(total);
        }
        pw.flush();
    }

    static class Obj {
        int a, c;
    }
}

ここまで8分35秒＋0ペナ。104位。


E - Ranges on Tree

問題
問題を理解するのに時間がかかった。その上問題の理解不足で1ペナ。

思考過程
  1. 要するに、葉の数をKとすると、葉に1～KをDFSでたどり着いた順番に割り振って、葉iについては「i i」を出力し、葉以外の頂点については部分木に含まれる葉の番号の最小と最大を出力すればよい。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int n;
    static List<List<Integer>> list;
    static int cnt;
    static int[] v;
    static String[] ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        n = Integer.parseInt(sa[0]);
        list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            list.get(a).add(b);
            list.get(b).add(a);
        }
        br.close();

        v = new int[n];
        ans = new String[n];
        dfs(0, -1);
        PrintWriter pw = new PrintWriter(System.out);
        for (String s : ans) {
            pw.println(s);
        }
        pw.flush();
    }

    static int[] dfs(int x, int p) {
        // 葉
        if (x != 0 && list.get(x).size() == 1) {
            cnt++;
            v[x] = cnt;
            ans[x] = v[x] + " " + v[x];
            return new int[] {v[x], v[x]};
        // 葉以外
        } else {
            int l = n;
            int r = 0;
            for (int c : list.get(x)) {
                if (c != p) {
                    int[] res = dfs(c, x);
                    l = Math.min(l, res[0]);
                    r = Math.max(r, res[1]);
                }
            }
            ans[x] = l + " " + r;
            return new int[] {l, r};
        }
    }
}

ここまで27分48秒＋1ペナ。479位。


F - Sum Sum Max

問題
やるだけなのだがやる気になれず、G問題を見たり諦めてAHCをやろうかと考えたりしていた。

思考過程
  1. 各テストケースについて、O(M)はかけられないが、O(N)はかけてよい。
  2. 現在のBの値とAの値を管理しながら、x, yを順に処理していく。
  3. i回目部分のBの差分は、x_i \times y_i、Aの差分は台形の面積を求めるイメージ。
  4. Bの値が正から負に変わるところでは、負になる直前のAも求めて答えとのmaxを取る必要がある。
  5. 答えの初期値を-infにしていてWAになり、x_1に変更。
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 t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            int n = Integer.parseInt(sa[0]);
//          int m = 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]);
            }

            long ans = x[0]; // 5
            long val = 0; // 現在のA
            long now = 0; // 現在のB
            for (int i = 0; i < n; i++) {
                long v1 = (long) x[i] * y[i];
                long next = now + v1;
                long v2 = ((now + x[i]) + next) * y[i] / 2;
                long nextv = val + v2;
                // 4
                if (now > 0 && next < 0) {
                    long y1 = now / -x[i];
                    long n1 = now + x[i] * y1;
                    long v3 = ((now + x[i]) + n1) * y1 / 2;
                    ans = Math.max(ans, val + v3);
                }

                now = next;
                val = nextv;
                ans = Math.max(ans, val);
            }
            pw.println(ans);
        }
        pw.flush();
        br.close();
    }
}

ここまで64分00秒＋2ペナ。345位。



Gは二項係数が絡んだ計算になりそうだとは思ったが、重複が排除しにくい形しか思い浮かばず20分ほど余らせて撤退。
このブログを書き始めた。



最終結果：ABCDEFの6完2000点、74分00秒、403位、パフォーマンス1883相当
レート変動：2060（Unrated）


ノルマとの15分の差は、読解力と気力の問題だったかなという感じ。
AHC008がなかなか上手くいっておらず、疲れが取れてなさそうな状態。