ACL Beginner Contest

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

A - Repeat ACL

問題

思考過程
  1. "ACL"をK回改行なしで出力し、最後に改行を出力する。
import java.util.Scanner;

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

        for (int i = 0; i < k; i++) {
            System.out.print("ACL");
        }
        System.out.println();
    }
}

ここまで0分40秒+0ペナ。350位。


B - Integer Preference

問題
もうちょっと思考停止でできる方法を思いつきたかった。
というか以下に思考過程を書いてみると、全然論理が成り立っていない。

思考過程
  1. 区間[A,B]区間[C,D]に共通部分があれば"Yes"。
  2. 基本形としては、A \leq C \leq B \leq DC \leq A \leq D \leq Bのようになるイメージ。
  3. C \leq A \leq B \leq Dのように包含されるケースもあるが、いずれの場合もC \leq BA \leq Dを満たしていれば交差しそう。

交差しない条件なら、明らかにB \lt CまたはD \lt Aだった。

import java.util.Scanner;

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

        if (c <= b && a <= d) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで4分54秒+0ペナ。1052位。


C - Connect Cities

問題

思考過程
  1. 入力を処理した後の連結成分の数-1が答え。
  2. 連結成分の数を取得できるようにしてあるDSUを貼る。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

        System.out.println(uf.num() - 1);
    }
}

/**
 * Disjoint Set Union(Union Find)
 */
class DSU {
    // 省略(提出参照)
}

提出
ここまで7分39秒+0ペナ。495位。


D - Flat Subsequence

問題
セグ木はまだACLを移植できていなかったので、元々持っていた自前のものを使った。

思考過程
  1. 遷移のことを考えると、最後に使った値に着目したDPをしたくなる。
  2. dp[i][j]i番目まで見て、最後の値がjの場合の最大長」とすると、空間計算量だけでO(NA_{max})になってしまう。
  3. これをやったとして、iからi+1には、j=A_i以外の部分は丸ごとコピーするだけなので、保持しておく情報としてはdp[j]しかいらない。
  4. 遷移は、(A_i-K)(A_i+K)の最大値+1dp[A_i]に設定していけばよい。
  5. 上記の最大値は、DPの情報をセグ木にしておけばO(logA_{max})で取得できるので、全体でO(NlogA_{max})となる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.function.BiFunction;

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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        int mx = 300001;
        // 区間の最大値を取得するセグ木
        SegTree<Integer> st = new SegTree<>(mx, 0, (v1, v2) -> Math.max(v1, v2));
        for (int i = 0; i < n; i++) {
            int l = Math.max(0, a[i] - k);
            int r = Math.min(mx, a[i] + k + 1);
            int max = st.query(l, r);
            st.update(a[i], max + 1);
        }
        System.out.println(st.query(0, mx));
    }

    static class SegTree<T> {
        // 省略(提出参照)
    }
}

提出
ここまで18分28秒+0ペナ。234位。


E - Replace Digits

問題
遅延セグ木はACLの移植も間に合ってなければ、どういうことができるのかも未学習の状態だったが、なんとか通すことはできた。

思考過程
  1. 後ろからやれば、ならしでO(N)とかO(NlogN)とかにできるのでは・・と思ったら、最終状態だけでなく毎回出力なので、前から処理していくしかない。
  2. 愚直に値を書き換えていたらO(N^2)になってしまうが、そもそも仮に値を書き換えるのを高速にできたとしても、毎回20万桁の余りを求めるだけでTLEな気がする。
  3. 書き換えた部分の差分を計算することを考える。
     
  4. 値の書き換えについては、値が変わる位置と値をマップで管理することで高速化する。
    例えば例1の推移を以下のように表す。(キーは、10^Nの位のNに相当)
    • 初期状態は[0=1]
    1. [0=1, 2=2, 6=1]
    2. [0=1, 2=2, 4=7]
    3. [0=3, 6=7]
    4. [0=3, 6=2, 7=7]
    5. [0=3, 3=1, 5=3, 6=2, 7=7]
  5. 同じ値が続く部分(マップのキーとキーの間)の和は、事前に19ごとに累積和を求めておく。
  6. 上記のマップ情報を元に、更新したい区間に含まれるエントリ分の和を引いて、更新後分を足す。
     
  7. 引くときの計算量は、更新区間内の値変化箇所によるが、一度処理するとそこは値変化箇所ではなくなるので、引くときの値変化箇所数は全体でならしO(Q)になる。
  8. 累積和パートも含め、全体の計算量はO(DN + QlogQ)くらいのつもり。
  9. 境界部分の更新パターンに注意して頑張って実装する。(パターンの考慮漏れで1回WA。)
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 n = Integer.parseInt(sa[0]);
        int q = Integer.parseInt(sa[1]);
        int[] l = new int[q];
        int[] r = new int[q];
        int[] d = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            r[i] = n - Integer.parseInt(sa[0]) + 1;
            l[i] = n - Integer.parseInt(sa[1]);
            d[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        int mod = 998244353;
        // 1~9ごとの累積和
        // dp[1][0] = 1
        // dp[1][1] = 11
        // ・・・
        // dp[9][8] = 99999999
        // ・・・
        long[][] dp = new long[10][n];
        for (int i = 1; i < 10; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i < n; i++) {
            dp[1][i] = dp[1][i - 1] * 10 % mod;
        }
        for (int i = 1; i < n; i++) {
            dp[1][i] += dp[1][i - 1];
        }
        for (int i = 2; i < 10; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[1][j];
                dp[i][j] %= mod;
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        long ans = dp[1][n - 1];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(0, 1);
        for (int i = 0; i < q; i++) {
            SortedMap<Integer, Integer> sm = map.subMap(l[i], r[i]);
            Integer ok = map.lowerKey(l[i]);
            if (ok == null) {
                ok = l[i];
            }
            int ov = map.get(ok);
            ok = l[i];

            // 更新区間内の元の値分を引く
            for (int key : sm.keySet()) {
                // ans -= sum[r-1] - sum[l-1]のイメージ
                if (key > 0) {
                    ans -= dp[ov][key - 1];
                }
                if (ok > 0) {
                    ans += dp[ov][ok - 1];
                }
                ok = key;
                ov = sm.get(key);
            }
            // ans -= sum[r-1] - sum[l-1]のイメージ
            ans -= dp[ov][r[i] - 1];
            if (ok > 0) {
                ans += dp[ov][ok - 1];
            }
            sm.clear();

            map.put(l[i], d[i]);
            if (!map.containsKey(r[i])) {
                map.put(r[i], ov);
            } else if (map.get(r[i]) == d[i]) {
                map.remove(r[i]);
            }

            // ans += sum[r-1] - sum[l-1]のイメージ
            ans += dp[d[i]][r[i] - 1];
            if (l[i] > 0) {
                ans -= dp[d[i]][l[i] - 1];
            }

            ans %= mod;
            if (ans < 0) {
                ans += mod;
            }
            pw.println(ans);
        }
        pw.flush();
    }
}

ここまで84分44秒+1ペナ。401位。


F - Heights and Pairs

問題
解けず。正解者数と残り時間的にできる可能性があるとも思っていなかった。

思考過程
  1. 全員の身長が異なるとすると、全部で(2N)! / (2^NN!)通りくらい?(自信なし)
  2. ここから同じ身長二人のペアが存在する通り数を引くことを考えたい。
  3. 残り時間数分では無理。

 


終結果:ABCDEの5完、89分44秒、407位、パフォーマンス1759
レート変動:1754→1755 (+1)


貼るだけでできたC、D問題では大きく順位を上げられているし、遅延セグ木なしでE問題勝負できてレートも減らなかったので、十分な結果だったかなと思う。
でもACL Practice Contestあと4問なるべく早めにやらなくては・・・。