AtCoder Beginner Contest 170

ABC

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

A - Five Variables

問題
何個までなら同じ実装を並べた方が楽なのか・・・。
後から見れば、入力部分とロジック部分を分けていることが一番手間になっている気がする。

思考過程
  1. 5つの値を全部、if文で0かどうか判定したい。
  2. 3つくらいまでならif文並べようかと思ったけど、5つは多く感じたので、入力値を配列で受け取ってfor文にした。
import java.util.Scanner;

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

        for (int i = 0; i < 5; i++) {
            if (x[i] == 0) {
                System.out.println(i + 1);
                return;
            }
        }
    }
}

ここまで1分18秒＋0ペナ。1004位。
ページ開くのに時間かかったわけでもないのに1000位にも入ってないって・・・。このタイムでそんなに遅いのか。


B - Crane and Turtle

問題
全探索するかO(1)数学するかちょっと考えて、これくらいだったらO(1)数学しても間違えないかと思って、実装量が少なそうなO(1)数学をすることにした。

思考過程
  1. 可能な足の総数の範囲は、2X～4X。
  2. 全部鶴（2X）と仮定した状態から、1匹ずつ亀に変えていけば、足の総数は2ずつ増えていくため、上記の範囲内の偶数は全て可能。
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();
        int y = sc.nextInt();
        sc.close();

        if (x * 2 <= y && y <= x * 4 && y % 2 == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで2分57秒＋0ペナ。400位。


C - Forbidden List

問題
わざわざミスが発生しやすそうな解き方してしまった気がする。
ミスりにくく実装量も少ない方法を最初に思いつきたい。

思考過程
  1. p_1～p_Nに含まれないかどうかは、Setのcontainsを使って判定する。
  2. Xから始めて、X-1, X+1, X-2, X+2, \cdotsの順に判定していければ、条件を満たしたところでそれが答えになる。
  3. 上記の順にループを回すには、for文の増分値を-1, +2, -3, +4, \cdotsするような感じにしたい。
  4. for文の形式では簡単には書けそうになく、増分値変数を用意し、毎回-1倍して絶対値を+1するようにした。
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 x = sc.nextInt();
        int n = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(sc.nextInt());
        }
        sc.close();

        int d = -1; // 増分値
        int now = x;
        while (true) {
            if (!set.contains(now)) {
                System.out.println(now);
                return;
            }
            now += d;
            d *= -1;
            if (d < 0) {
                d--;
            } else {
                d++;
            }
        }
    }
}

ここまで6分45秒＋0ペナ。359位。
A問題よりよっぽど手間取った気がするけど順位は上がっていく。


D - Not Divisible

問題
これは最初に思いついた単純な方法で通って割と成功だった。

思考過程
  1. 各値は、自身以下の値でしか割り切れないので、昇順ソートすれば自身より前しか見なくてよくなる。
  2. 自身より前全ての値で割り切れるかどうか実際に試すと、O(N^2)となりTLEしてしまうので、別の方法を考える。
  3. A_iについて調べた後、A_iをSetに追加する。
  4. A_iの調べ方は、A_iの約数の中にSetに含まれるものが1つもなければ割り切れない。
  5. A_iの約数を得るのがO(\sqrt{A_i})、Setに含まれる判定がO(1)なので、全体でO(N\sqrt{A_i})。10^8くらいなのでやや危ないが間に合いそう。
  6. 例２が1になってしまったので、同じ値が続く場合はカウントしないよう条件を追加。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

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();

        Arrays.sort(a);

        int ans = 0;
        Set<Integer> set = new HashSet<>();
        label:
        for (int i = 0; i < n; i++) {
            // 同じ値が複数存在する場合
            if (i < n - 1 && a[i] == a[i + 1]) {
                set.add(a[i]);
                continue;
            }
            // a[i]の約数リスト
            List<Integer> list = divList(a[i]);
            for (Integer e : list) {
                // 約数の中にsetに存在するものがあればNG
                if (set.contains(e)) {
                    continue label;
                }
            }
            set.add(a[i]);
            ans++;
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static List<Integer> divList(int n) {
        List<Integer> list = new ArrayList<>();
        int end = (int) Math.sqrt(n);
        for (int i = 1; i <= end; i++) {
            if (n % i == 0) {
                list.add(i);
            }
        }
        int i = end * end == n ? list.size() - 2 : list.size() - 1;
        for ( ; i >= 0; i--) {
            list.add(n / list.get(i));
        }
        return list;
    }
}

ここまで13分34秒＋0ペナ。141位。


E - Smart Infants

問題
TreeSet万歳。

思考過程
  1. 各幼稚園から最大レートを知りたいので、TreeSetを幼稚園数分用意したくなる。
  2. 各最大レートの最小値を知りたいので、最大レートを集めたTreeSetを1つ用意したくなる。
  3. レートが同じときに重複要素とみなされないように、幼児オブジェクトの比較メソッドには適当にインデックスの比較も入れておく。
  4. 転園操作をした時に、全てのTreeSetを対数以下のオーダーで更新できるかを考える。以下の通りで可能。
    • 転園する幼児Cを特定する・・・幼児配列を用意しておけばO(1)
    • 転園元を特定する・・・幼児オブジェクトに幼稚園番号を持たせておけばO(1)
    • 転園元から幼児Cを取り出す・・・オブジェクトをキーにremoveすればO(logN)
    • 転園先に幼児を追加する・・・addはO(logN)
    • 最小値や最大値の取得・・・firstやlastはO(logN)
    • 最大レートSetの更新・・・各幼稚園のSetのremoveやaddと同様にしてO(logN)
  5. Setが空の場合や、転園する幼児が転園元で最大レートかどうか、転園先で最大レートかどうかに注意する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

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]);

        Obj[] arr = new Obj[n]; // 幼児オブジェクト配列
        List<TreeSet<Obj>> list = new ArrayList<>(); // 幼稚園分のSet
        for (int i = 0; i < 200000; i++) {
            list.add(new TreeSet<>());
        }
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.i = i;
            o.a = Integer.parseInt(sa[0]);
            o.b = Integer.parseInt(sa[1]) - 1;
            arr[i] = o;
            list.get(o.b).add(o);
        }
        int[] c = new int[q];
        int[] d = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            c[i] = Integer.parseInt(sa[0]) - 1;
            d[i] = Integer.parseInt(sa[1]) - 1;
        }
        br.close();

        // 最大レートSet
        TreeSet<Obj> top = new TreeSet<>();
        for (int i = 0; i < 200000; i++) {
            TreeSet<Obj> set = list.get(i);
            if (!set.isEmpty()) {
                top.add(set.first());
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            Obj o = arr[c[i]]; // 転園する幼児C
            TreeSet<Obj> bef = list.get(o.b); // 転園元
            TreeSet<Obj> aft = list.get(d[i]); // 転園先
            Obj b0 = bef.first(); // 転園元の最大
            bef.remove(o); // 幼児Cを転園元から削除
            // 幼児Cが転園元の最大の場合
            if (b0 == o) {
                // 最大レートSetから幼児Cを除いて次点を追加
                top.remove(o);
                if (!bef.isEmpty()) {
                    top.add(bef.first());
                }
            }
            o.b = d[i];
            if (aft.isEmpty()) {
                // 転園先が0人なら幼児Cが最大
                top.add(o);
            } else {
                // 幼児Cが転園先の最大より大きければ入れ替え
                Obj a0 = aft.first();
                if (o.a > a0.a) {
                    top.remove(a0);
                    top.add(o);
                }
            }
            aft.add(o); // 幼児Cを転園先に追加
            pw.println(top.last().a);
        }
        pw.flush();
    }

    // 幼児オブジェクト
    static class Obj implements Comparable<Obj> {
        int i, a, b;

        @Override
        public int compareTo(Obj o) {
            if (a != o.a) {
                return o.a - a; // aの降順
            }
            return i - o.i; // 重複回避のため
        }
    }
}

ここまで34分31秒＋0ペナ。160位。
パフォ見込みは2100くらいとかになっており、Fが簡単でない限りはプラスになりそうだと一安心。


F - Pond Skater

問題
ただBFSするだけの見た目をしているのに正解者数の伸びがそれほどではなく、今回は大勝できるのではと思ったが、そんなに甘くはなく。正しい枝刈りが下手。
WAが2ケース残ったまま終了。

思考過程
  1. ただ4方向に移動するBFSをすればよいと思うが、遷移にO(K)かけるとTLEしそう。
  2. 手前から見ていって、最短距離を更新できなかった時点で打ち切れば、同じマスは1回しか調べずに済むので間に合いそう。　→例１が6になる。
    マス(2, 3)→(2, 4)の移動で(2, 4)が5になっており、(1, 4)から下に行って(2, 4)と(3, 4)を5にする処理が、(2, 4)の更新失敗により(3, 4)まで処理されていなかった。
  3. 更新値が元の値「未満」ではなく「以下」なら打ち切らないようにしてみて、計算量怪しそうだけどとりあえず投げてみる。　→案の定TLEだけどたった3ケースだけ。
  4. 異なる方向から更新が入っているときに打ち切るのが駄目っぽいので、DPテーブルを、縦方向の移動でたどり着いた場合の距離と、横方向の（以下同文）の2つにしてみる。
  5. 更新値は両者の最小値+1、縦方向に移動するときは縦方向テーブルを更新できるところまでの移動で打ち切り、横方向も同様としてみる。　→2ケースWA。

コンテスト後にテーブルを4つにしてみたけど結果は変わらず。どこが駄目なのかは後日ゆっくり考える。



最終結果：ABCDEの5完、34分31秒、422位、パフォーマンス1884
レート変動：1791→1801

AGC045で下がった後、順調に少しずつ回復。
レートが完全に青になってから約7ヶ月半。4ヶ月で100上がるくらいのペースなので、やっぱり当面は1800維持、下がっても1700前半までは落とさないのが目標。