AtCoder Beginner Contest 179

コンテスト前のレート:1765
レート通りのパフォーマンスが得られる順位:574位

A - Plural Form

問題

思考過程
  1. 末尾の文字が's'かどうかを調べる。
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();

        if (s.charAt(s.length() - 1) == 's') {
            System.out.println(s + "es");
        } else {
            System.out.println(s + "s");
        }
    }
}

ここまで1分07秒+0ペナ。587位。


B - Go to Jail

問題

思考過程
  1. カウンタを用意しておき、条件を満たせば+1、満たさなければ0に戻す。
  2. カウンタが3になったところで"Yes"を出力して終了。
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[][] d = new int[n][2];
        for (int i = 0; i < n; i++) {
            d[i][0] = sc.nextInt();
            d[i][1] = sc.nextInt();
        }
        sc.close();

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (d[i][0] == d[i][1]) {
                cnt++;
                if (cnt == 3) {
                    System.out.println("Yes");
                    return;
                }
            } else {
                cnt = 0;
            }
        }
        System.out.println("No");
    }
}

ここまで3分11秒+0ペナ。400位。


C - A x B + C

問題
解き方が下手くそだった。
9割以上駄目だと思ったものを何故投げてしまったのか。

思考過程
  1. A \times B = N - Cに変形すると、A \times B1N-1になる組の数をそれぞれ求めて合計すればよいことになる。
  2. これは、1N-1について、それぞれの約数の数を求めればよいことになる。
  3. 単純にO(\sqrt{N})で約数列挙してみると、手元で実行したときに例3がぎりぎり2秒に収まってないかもくらい。 →4ケースTLE
  4. エラトステネスの篩を使って素因数分解を行い、各素因数の指数+1の積で約数の数を求めるように変更する。
import java.util.HashMap;
import java.util.Map;
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();

        Eratosthenes e = new Eratosthenes(n);
        long ans = 0;
        for (int c = 1; c < n; c++) {
            Map<Integer, Integer> soinsu = e.bunkai(n - c);
            long val = 1;
            for (Integer key : soinsu.keySet()) {
                val *= soinsu.get(key) + 1;
            }
            ans += val;
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static class Eratosthenes {
        int[] div;

        public Eratosthenes(int n) {
            if (n < 2) return;
            div = new int[n + 1];
            div[0] = -1;
            div[1] = -1;
            int end = (int) Math.sqrt(n) + 1;
            for (int i = 2; i <= end; i++) {
                if (div[i] == 0) {
                    div[i] = i;
                    for (int j = i * i; j <= n; j+=i) {
                        if (div[j] == 0) div[j] = i;
                    }
                }
            }
            for (int i = end + 1; i <= n; i++) {
                if (div[i] == 0) div[i] = i;
            }
        }

        public Map<Integer, Integer> bunkai(int x) {
            Map<Integer, Integer> soinsu = new HashMap<>();
            while (x > 1) {
                Integer d = div[x];
                soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);
                x /= d;
            }
            return soinsu;
        }

        public boolean isSosuu(int x) {
            return div[x] == x;
        }
    }
}

ここまで10分55秒+1ペナ。1370位。


D - Leaping Tak

問題
ライブラリを使い慣れてなくて、少しだけ\pm1の添え字ガチャをした。

思考過程
  1. 例1のようにS=\{1, 3, 4\}とすると、単純に考えれば、配るDPの時はi(i+1), (i+3), (i+4)の遷移を、もらうDPの時は(i-1), (i-3), (i-4)iの遷移を処理する必要があり、i, S共にO(N)なのでO(N^2)となってしまう。
  2. 配るDPだと遷移先を減らすことはできないと思ったので、もらうDPで遷移元の和を早く求められないかを考える。
  3. 遷移元が最大10個の連続した区間なので、連続区間の和を求められるセグメント木かBITを使いたくなる。
  4. ACLの移植をしたBIT(Fenwick Tree)があるので、せっかくなので使ってみることにする。
  5. これにより、各iについて、(i-R)(i-L)iの遷移をK回ずつ処理することになり、O(NKlogN)となった。
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]);
        int[] l = new int[k];
        int[] r = new int[k];
        for (int i = 0; i < k; i++) {
            sa = br.readLine().split(" ");
            l[i] = Integer.parseInt(sa[0]);
            r[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        int mod = 998244353;
        FenwickTree ft = new FenwickTree(n);
        ft.add(0, 1);
        for (int i = 1; i < n; i++) {
            long sum = 0;
            for (int j = 0; j < k; j++) {
                int ll = Math.max(i - r[j], 0);
                int rr = Math.max(i - l[j] + 1, 0);
                sum += ft.sum(ll, rr);
                sum %= mod;
            }
            ft.add(i, sum);
        }
        System.out.println(ft.sum(n - 1, n));
    }
}

/**
 * Fenwick Tree(Binary Indexed Tree)
 */
class FenwickTree {
    // 思考過程4のリンク先参照
}

ここまで23分58秒+1ペナ。443位。


E - Sequence Sum

問題
ABC167-Dと似たような問題。
こういうのダブリングで簡単にできるようになりたいけど、できそうになかったのでループ検出で頑張った。
実装が下手で手間かけてしまったと思ったが、D解いた時点より多少順位上がってるので普通くらいか。

思考過程
  1. 問題文の漸化式に従って数列を求めていくと、M回以内に同じ値が現れ、以降同じ数列のループになる。
  2. Setを使って値が既出かどうかを調べ、既出であれば、一旦そこを起点とする。
  3. もう一度同じ値が出てくるまで処理を続け、その時の周期dと合計値sumを求める。
  4. 残りの処理回数をrとし、sum \times \lfloor r / d \rfloorを答えに足す。
  5. 残った処理回数r \% d回分は再び愚直に計算する。
  6. 例1でd=0により0除算が発生したので、上記3.まででN回に達している場合はそこで終了する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

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

        Set<Long> set = new HashSet<>();
        long ans = x;
        long now = x;
        int i = 1;
        set.add(now);
        // A_2~既出検出まで
        for ( ; i < n; i++) {
            now = now * now % m;
            ans += now;
            if (!set.add(now)) {
                i++;
                break;
            }
        }

        long sum = 0;
        int d = 0;
        set.clear();
        // 周期分の項数と合計を求めるための2周目
        for ( ; i < n; i++) {
            now = now * now % m;
            ans += now;
            if (!set.add(now)) {
                i++;
                break;
            }
            sum += now;
            d++;
        }
        // 思考過程6
        if (i == n) {
            System.out.println(ans);
            return;
        }

        // 思考過程4
        long r = n - i;
        ans += sum * (r / d);
        // 思考過程5
        r %= d;
        for (int j = 0; j < r; j++) {
            now = now * now % m;
            ans += now;
        }
        System.out.println(ans);
    }
}

ここまで44分18秒+1ペナ。369位。


F - Simplified Reversi

問題
D問題と比べ、EやFの方が知識がなくても解ける可能性がある問題だったと思う。
本当は下記思考過程4のところで色々遠回りしたけど省略。

思考過程
  1. O(N^2)の二次元配列を用意しようとするとTLEより前にMLEになりそう。
  2. 縦方向と横方向でそれぞれ最初に白石が出てくる位置の配列を用意し、普通に更新していくと、クエリで指定される位置が後ろの方だと更新にN回近くかかってしまい、全体でO(N^2)となってしまう。
  3. 上記2の配列を更新していった場合、まだ置いていない位置だけ見れば、単調増加になっている。
    例えば例1でQuery2まで処理したとき、'1 x'のクエリに対しては、x=02では2x=34では4が最初の白石の位置。
  4. TreeMapを使い、最初の白石の位置とそれが変わるxを管理する。(キー:値に該当する範囲の上端、値:最初の白石の位置)
  5. 縦方向マップで取得した値が横方向マップに追加する情報のキーになり、値はクエリのxとなるのが基本だが、例1のQuery3のように、既に壁になっているより後ろを指定されたときに、{4=2}→{4=3}と更新しないよう注意する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
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 n = Integer.parseInt(sa[0]);
        int q = Integer.parseInt(sa[1]);
        long ans = (long) (n - 2) * (n - 2);
        TreeMap<Integer, Integer> mapx = new TreeMap<>();
        TreeMap<Integer, Integer> mapy = new TreeMap<>();
        mapx.put(n - 1, n - 1);
        mapy.put(n - 1, n - 1);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int x = Integer.parseInt(sa[1]) - 1;
            if (sa[0].equals("1")) {
                int b = mapx.get(mapx.ceilingKey(x));
                ans -= b - 1;
                mapy.put(b, Math.min(x, mapy.getOrDefault(b, n - 1)));
            } else {
                int b = mapy.get(mapy.ceilingKey(x));
                ans -= b - 1;
                mapx.put(b, Math.min(x, mapx.getOrDefault(b, n - 1)));
            }
        }
        System.out.println(ans);
        br.close();
    }
}

ここまで78分46秒+1ペナ。423位。



終結果:全完、83分46秒、449位、パフォーマンス1865
レート変動:1765→1775 (+10)


C問題でやらかしていた以外は、概ね400位台の推移で、安定したペースで解けていた。
ただ、D問題以降は実装に時間がかかり過ぎていたとも思う。