AtCoder Beginner Contest 177

ABC

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

A - Don't be late

問題
こういうA問題はちょっと凡ミスが怖い。

思考過程
  1. 待ち合わせ場所までの所要時間を考えて、D / Sの切り上げがT以下ならYes。
  2. それでも良さそうだが、切り上げとかめんどくさいので、距離で考えて、S \times T \geq Dと判定する。
import java.util.Scanner;

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

        if (s * t >= d) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分11秒＋0ペナ。498位。


B - Substring

問題
B問題で2重ループが出て普段より難しめだと思ったけど、やっぱりB問題の難易度は平均100くらいほしいと思う。

思考過程
  1. 制約が1000でO(|S|^2)とかでも間に合うので、TをSの何文字目からの部分文字列とするかを全部試す。
  2. 例えばSが5文字でTが3文字の場合、開始位置は0 \sim 2文字目までを調べればよいなどと思い浮かべながら、for文の終了条件の境界を間違えないように注意する。
  3. 各開始位置について|T|文字中何文字一致したかをカウントし、その最大値を|T|から引いたものが答え。
    （逆に不一致数の最小値を求めれば、最後に引く必要がないが、コンテスト中で慌ててたらそんなことにも気付かず・・・。）
import java.util.Scanner;

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

        int max = 0;
        for (int i = 0; i <= s.length - t.length; i++) {
            int cnt = 0;
            for (int j = 0; j < t.length; j++) {
                if (s[i + j] == t[j]) {
                    cnt++;
                }
            }
            max = Math.max(max, cnt);
        }
        System.out.println(t.length - max);
    }
}

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


C - Sum of product of pairs

問題
こういう_NC_2通り全探索したいけどO(N^2)は間に合わない系統の問題にかなりの苦手意識があったりするが、なんとかあまり詰まらずに済んだ。

思考過程
  1. 掛け算をするっぽいので、とりあえずオーバーフロー回避のため入力をlong型で受け取ってみる（が意味はなかった）。
  2. ExcelにN \times Nの表を書いてみると、公式解説に載っている図のようになり、A_1 \times (A_2 \sim A_N) + A_2 \times (A_3 \sim A_N) + \cdotsのように求められることがわかる。
  3. これを後ろから計算していけば、上記の括弧内は毎回A_iを1つずつ足していけばよくなる。
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(" ");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(sa[i]);
        }
        br.close();

        int mod = 1000000007;
        long ans = 0;
        long sum = 0; // a[i + 1]から最後までの和
        for (int i = n - 2; i >= 0; i--) {
            sum += a[i + 1];
            sum %= mod;
            ans += sum * a[i];
            ans %= mod;
        }
        System.out.println(ans);
    }
}

ここまで7分57秒＋0ペナ。403位。


D - Friends

問題
貼るだけだった。

思考過程
  1. 問題文の前半でUnionFindっぽさを感じる。
  2. 例１についてUnionFindを使った後には、
    \{1, 2, 5\}
    \{3, 4\}
    のようなグループができる。
  3. これを縦に切れば、出力例１の説明通り、\{1, 3\}, \{2, 4\}, \{5\}になる。
  4. 縦に切っていくつに分ける必要があるかと言えば、最大の連結成分の要素数分なので、それが答え。
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 m = Integer.parseInt(sa[1]);
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            a[i] = Integer.parseInt(sa[0]) - 1;
            b[i] = Integer.parseInt(sa[1]) - 1;
        }
        br.close();

        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < m; i++) {
            uf.union(a[i], b[i]);
        }

        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, uf.size(i));
        }
        System.out.println(max);
    }

    // 以下ライブラリ

    static class UnionFind {
        int[] parent, size;

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
                size[py] += size[px];
            }
        }

        int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }

        /**
         * xを含む連結成分のサイズ
         */
        int size(int x) {
            return size[find(x)];
        }
    }
}

ここまで12分03秒＋0ペナ。343位。
ほぼ貼るだけの4分で解いてこの順位だと、もし貼るものが用意できていなかったらと思うと恐ろしい・・・。
UnionFindは、size配列を作らず、parent配列で親の要素に-sizeを入れる改良をするのをサボり続けている状態。


E - Coprime

問題
計算量をよく考えずにとりあえず投げたら通ってしまったおかげで勝てた。

思考過程
  1. setwise coprimeはただ累積GCDが1かどうかを調べるだけ。
  2. pairwise coprimeは、各A_iが持つ素因数に重複がないことが条件となる。
  3. A_iを素因数分解し、全体の素因数Setに追加していく。追加の際、既にSetに含まれていたらpairwise coprimeではないとする。
  4. 素因数分解は単純にやればO(\sqrt{A_i})だが、素因数が重複した時点で残りは調べる必要がないので、全てのA_iが最悪計算量になることはあり得ず、平均的にはだいぶ早いのではないかと思い、とりあえず一番愚直に近い方法で提出してみる。

提出した瞬間に、途中で打ち切るのを忘れていたことに気付くが、通ったのでヨシ。もし駄目だったら多分エラトステネスの篩にたどり着くことにはなったと思うが、果たしてそれがすぐに出てきたかどうか・・。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
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();

        Set<Integer> set = new HashSet<>();
        int gcd = a[0];
        boolean p = true;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> map = bunkai(a[i]);
            for (Integer o : map.keySet()) { // a[i]の素因数を処理
                if (!set.add(o)) { // addは重複要素追加時にfalse
                    p = false;
                }
            }
            gcd = gcd(gcd, a[i]);
        }
        if (p) {
            System.out.println("pairwise coprime");
        } else if (gcd == 1) {
            System.out.println("setwise coprime");
        } else {
            System.out.println("not coprime");
        }
    }

    // 以下ライブラリ

    static Map<Integer, Integer> bunkai(int n) {
        Map<Integer, Integer> soinsu = new HashMap<>();
        int end = (int) Math.sqrt(n);
        int d = 2;
        while (n > 1) {
            if (n % d == 0) {
                n /= d;
                if (soinsu.containsKey(d)) {
                    soinsu.put(d, soinsu.get(d) + 1);
                } else {
                    soinsu.put(d, 1);
                }
                end = (int) Math.sqrt(n);
            } else {
                if (d > end) {
                    d = n - 1;
                }
                d++;
            }
        }
        return soinsu;
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

ここまで20分04秒＋0ペナ。148位。
レート通りのパフォーマンスを出すには31分18秒がノルマであったので、1ペナでも出していたら危なかった。

F - I hate Shortest Path Problem

問題
1時間以上の時間がありながら解けず。
5完まで十分早かったのと、正解者数の伸びが鈍かったので、あまり必死になってはいなかったが。

例えば、以下のような入力があった場合、

5 7 // H W
3 4
5 6
1 3
5 5
3 4

　 　 → → 　 　 　
　 　 　 　 → → 　
→ → → 　 　 　 　
　 　 　 　 → 　 　
　 　 → → 　 　 　
1行目・・・{1=1, 2=2, 5=5, 6=6, 7=7}
2行目・・・{1=1, 2=2～4, 7=7}
3行目・・・{2=4～6, 7=7}
4行目・・・{2=[4, 6], 7=7}
5行目・・・{2=5～6, 7=7}
のように始点と到達範囲を管理できないかと思ったが、実装途中で時間切れ。
上記の4, 5行目のように、分断されたり、分断した部分がくっついたりなどのケースを考えていて、どうしようかと悩んでいる間に終わった。
たとえ実装し切れたとしても、計算量がかなり怪しい。

公式解説を見ると、始点と終点を管理していくという考えだけは合っているような気もするが、データの持ち方や更新の仕方などの考察が足りなかったのかな・・・。
なお、遅延セグ木は未だに持っていない。


F - I hate Shortest Path Problem（2020/8/31追記）

公式解説通りだが、上記とは逆に終点の方をキーにして解けたので追記。
具体的には以下のような情報を管理する。

　 　 → → 　 　 　
　 　 　 　 → → 　
→ → → 　 　 　 　
　 　 　 　 → 　 　
　 　 → → 　 　 　
■終点→始点情報のマップ
1行目・・・{1=1, 2=2, 5=5, 6=6, 7=7}
2行目・・・{1=1, 2=2, 7=7}
3行目・・・{4=2, 7=7}
4行目・・・{4=2, 7=7}
5行目・・・{5=2, 7=7}

■始点→終点の横の移動距離セット（※上記のマップと対応した順番に記載しているが、実際は値の小さい順に自動ソートさせる）
1行目・・・{0, 0, 0, 0, 0}
2行目・・・{0, 0, 0}
3行目・・・{2, 0}
4行目・・・{2, 0}
5行目・・・{3, 0}

どちらのデータ構造も、1行分の処理としては、終点が下移動NG区間内の情報を削除し、NG区間が右端に付いてなければNG区間の1つ右のマスを終点とした情報を追加する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.SortedMap;
import java.util.TreeMap;

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int[] a = new int[h];
        int[] b = new int[h];
        for (int i = 0; i < h; i++) {
            sa = br.readLine().split(" ");
            a[i] = Integer.parseInt(sa[0]) - 1;
            b[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        TreeMap<Integer, Integer> map = new TreeMap<>(); // キー：終点、値：始点
        MultiTreeSet<Integer> set = new MultiTreeSet<>(); // 始点→終点の横の移動距離
        for (int i = 0; i < w; i++) {
            map.put(i, i);
            set.add(0);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < h; i++) {
            SortedMap<Integer, Integer> sub = map.subMap(a[i], b[i]);
            for (Integer key : sub.keySet()) {
                set.remove(key - sub.get(key)); // 終点がNG区間のものの移動距離情報を削除
            }
            // NG区間の1つ右のマスに対応する始点情報がない場合（ある場合は元のものが最も右なので更新不要）
            // かつ、NG区間が右端に付いていない場合
            if (!map.containsKey(b[i]) && !sub.isEmpty() && b[i] < w) {
                int s = sub.get(sub.lastKey()); // 最も右の始点
                map.put(b[i], s);
                set.add(b[i] - s);
            }
            sub.clear(); // NG区間の終点情報を削除
            if (set.size == 0) {
                pw.println(-1);
            } else {
                pw.println(set.first() + i + 1);
            }
        }
        pw.flush();
    }

    // 以下ライブラリ

    static class MultiTreeSet<T> {
        TreeMap<T, Integer> map = new TreeMap<>();
        int size = 0;

        void add(T e) {
            map.put(e, map.getOrDefault(e, 0) + 1);
            size++;
        }

        void remove(T e) {
            if (e != null && map.containsKey(e)) {
                int val = map.get(e);
                if (val == 1) {
                    map.remove(e);
                } else {
                    map.put(e, val - 1);
                }
                size--;
            }
        }

        T first() {
            return map.firstKey();
        }
    }
}

TreeMapとかを駆使して解ける問題を落としたのは結構悔しい。
上記ソース中のMultiTreeSet、標準では重複要素を格納できないTreeSetしか存在しないのでなんとなく作っておいたものの、これまで全く出番がなかったのだが、それを使える機会を逃したのでさらに悔しい。



最終結果：ABCDEの5完、20分04秒、238位、パフォーマンス2094
レート変動：1778→1814


直近4回のレート推移が-45、-28、+31、+36となっており、ほぼV字回復に成功した形。
5月以降黄パフォが出るようになってきたのだが、直近21回のパフォーマンスが黄7回、青7回、水6回、緑1回と、水以下が依然として多いので、下振れを減らすことでレート1900台を目指したい。