ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)(Rated範囲外)

ABC

コンテスト前のレート：2038
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：300位（1600点、102分21秒）

A - Five Integers

問題

思考過程
  1. 種類数を求めるのは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);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 5; i++) {
            set.add(sc.nextInt());
        }
        sc.close();

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

ここまで0分29秒＋0ペナ。54位。


B - Prefix?

問題
最初にこの問題からやればFA取れていたかもしれない。
他にもそういう人何人もいるけど。

思考過程
  1. StringのstartsWithを使うだけ。
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();
        String t = sc.next();
        sc.close();

        if (t.startsWith(s)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで1分05秒＋0ペナ。10位。


C - Chinese Restaurant

問題

思考過程
  1. 操作回数を全探索して都度判定にO(N)かけたのでは駄目。
  2. 料理p_iが位置p_iに移動するまで何回操作すればよいかを求め、それを「操作回数ごとに何個該当するか」という形にデータを持ち変える。
  3. すると、操作回数を全探索した時に操作回数が(i-1)～(i+1)であるものだけを調べればよいことになる。
  4. 操作回数0に対しては0, 1だけ調べればよさそうか？　→WA
  5. 0に対しては\{N-1, 0, 1\}、N-1に対しては\{N-2, N-1, 0\}のように端もちゃんと3箇所調べる必要があった。
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[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }
        sc.close();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[p[i]] = (p[i] - i + n) % n;
        }

        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[a[i]]++;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int val = c[(i - 1 + n) % n] + c[i] + c[(i + 1) % n];
            ans = Math.max(ans, val);
        }
        System.out.println(ans);
    }
}

ここまで8分54秒＋1ペナ。336位。


D - Unique Username

問題

思考過程
  1. N \leq 8なので順列全探索してよい。
  2. Mの制約は大きめなので、Tのいずれとも一致しない判定は、TをSetに入れることで毎回O(1)で行うようにする。
  3. '_'を間に1個以上入れるところも鳩ノ巣原理で最悪M+1回文字列生成すれば終わるので全探索してよいが、その全探索をどのように実装したらよいか。
    　
  4. やりたいことは組合せの全探索とほぼ同様で、'_'を追加できる残り回数分ネストした、i=0～(N-1)、j=i～(N-1)、k=j～(N-1)、\cdotsのような多重ループを回せればよく、これは再帰で実装できる。
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static Set<String> t;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
        }
        t = new HashSet<>();
        for (int i = 0; i < m; i++) {
            t.add(sc.next());
        }
        sc.close();

        boolean res = permutation(s, 0, 0, new String[n]);
        if (!res) {
            System.out.println(-1);
        }
    }

    // 順列全探索
    static boolean permutation(String[] org, int used, int idx, String[] wk) {
        if (idx == org.length) {
            int n = wk.length - 1;
            int[] a = new int[n];
            Arrays.fill(a, 1);
            String ans = toStr(wk, a);
            int rem = 16 - ans.length();
            // '_'の追加の仕方を全探索
            if (dfs(wk, a, 0, rem)) {
                return true;
            }
            return false;
        }

        for (int i = 0; i < org.length; i++) {
            if ((used >> i & 1) == 0) {
                wk[idx] = org[i];
                if (permutation(org, used | 1 << i, idx + 1, wk)) {
                    return true;
                }
            }
        }
        return false;
    }

    // wk：Sの順列
    // a：wkの各要素の間に入れる'_'の個数
    // idx：aの何番目以降に'_'を足すか
    // rem：'_'を足せる残り個数
    static boolean dfs(String[] wk, int[] a, int idx, int rem) {
        String ans = toStr(wk, a);
        if (ans.length() >= 3 && !t.contains(ans)) {
            System.out.println(ans);
            return true;
        }
        if (rem == 0) {
            return false;
        }
        for (int i = idx; i < a.length; i++) {
            a[i]++;
            if (dfs(wk, a, i, rem - 1)) {
                return true;
            }
            a[i]--;
        }
        return false;
    }

    static String toStr(String[] wk, int[] a) {
        StringBuilder sb = new StringBuilder();
        sb.append(wk[0]);
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i]; j++) {
                sb.append('_');
            }
            sb.append(wk[i + 1]);
        }
        return sb.toString();
    }
}

ここまで27分32秒＋1ペナ。131位。


E - Chinese Restaurant (Three-Star Version)

問題
差分計算で頭こんがらがって時間かかった。
順位表でFの方が解かれているのは見ていたので飛ばすことも考えてはいたが、完全に行き詰まることはなかったのでやり切った。

思考過程
  1. 料理p_iが位置p_iに移動するまで何回操作すればよいかを求めるところまではC問題と同じ。
  2. テーブルが円卓でなければ上記1.の中央値との差の総和でよいが、円卓の場合は中央値をどこにするかを全探索する必要がある。
  3. 一旦上記1.の結果に対して中央値との差の総和を求め、あとは差分計算をしていく。
import java.util.ArrayList;
import java.util.Collections;
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[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }
        sc.close();

        // 思考過程1
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[p[i]] = (p[i] - i + n) % n;
        }
        List<Integer> list = new ArrayList<>(n * 2);
        for (int i = 0; i < n; i++) {
            list.add(a[i]);
        }
        Collections.sort(list);

        // 初期解
        int mi = n / 2;
        int mid = list.get(mi);
        long val = 0;
        for (int i = 0; i < n; i++) {
            val += Math.abs(list.get(i) - mid);
        }
        long ans = val;

        int l = 0;
        while (l < n) {
            // 先頭要素にnを足したものを末尾に追加し、
            // 後ろからn個の要素に対して答えを求める
            int pl = l;
            int pv = list.get(l);
            int nv = pv + n;
            list.add(nv);
            l++;
            // 同一値が続く場合、その分スキップ
            while (l < n && list.get(l) == pv) {
                list.add(nv);
                l++;
            }

            // 例
            // (2,) 3, 3, 3, 4, 5, 7, 7, 8, 8, 12 から
            // (2, 3, 3, 3,) 4, 5, 7, 7, 8, 8, 12, 13, 13, 13 への差分計算
            // midは1個目の7　→　mid2は2個目の8
            int mid2 = list.get(l + mi);
            long v1 = (long) (mid2 - mid) * (mi - (l - pl)); // 4, 5の増分
            long v2 = (long) (mid2 - mid) * (n - mi - (l - pl)); // 8(2個目), 12の減分
            long v3 = (long) (mid - pv) * (l - pl); // 3がなくなる分
            long v4 = (long) (nv - mid2) * (l - pl); // 13が追加される分
            long v5 = 0; // mid～mid2の各要素 7, 7, 8(1個目)
            int end = pl + mi + l - pl;
            for (int i = pl + mi; i < end; i++) {
                v5 -= list.get(i) - mid;
                v5 += mid2 - list.get(i);
            }
            val = val + v1 - v2 - v3 + v4 + v5;
            ans = Math.min(ans, val);
            mid = mid2;
        }
        System.out.println(ans);
    }
}

ここまで71分48秒＋1ペナ。268位。


F - Best Concatenation

問題

思考過程
  1. 順序を決めなければならないので、DPではなく貪欲でできないか考える。
  2. 基本的には合計数値が大きいものが後ろ。
  3. 数値が同じ場合はS_i内の'X'の位置や個数で変わるし、合計数値が僅差でも優先順がひっくり返ることはありそう。
    　
  4. 特定の2つの文字列の順序を決めようとしたら、それぞれの文字列内でのスコアは順序では変わらず、変わるのは「前に置く方の'X'の個数と後ろに置く方の合計数値の積」の部分。
  5. Tの内T_{i}とT_{i+1}部分の2つを入れ替えても他の部分には影響しないので、結局上記4.をそのまま比較関数にしてソートすればよいことになる。
import java.util.PriorityQueue;
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();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
        }
        sc.close();

        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> {
            long v1 = (long) o1.x * o2.rate;
            long v2 = (long) o2.x * o1.rate;
            return Long.compare(v2, v1);
        });
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            for (int j = 0; j < s[i].length(); j++) {
                char c = s[i].charAt(j);
                if (c == 'X') {
                    o.x++;
                } else {
                    int d = c - '0';
                    o.rate += d;
                    o.val += o.x * d;
                }
            }
            que.add(o);
        }

        long ans = 0;
        long x = 0;
        while (!que.isEmpty()) {
            Obj o = que.poll();
            ans += o.val;
            ans += x * o.rate;
            x += o.x;
        }
        System.out.println(ans);
    }

    static class Obj {
        int x, rate; // x：'X'の個数、rate：合計数値
        long val; // 1つの文字列内でのスコア
    }
}

ここまで85分32秒＋1ペナ。161位。



GやExをやるには残り時間が足りない。

Gは1文字目が同じもの同士にグループ分け、その中で2文字目が同じ同士にグループ分け、\cdotsとかしていきたそうな感じで、そういうのってtrie木とかでできるんだっけ？
使えるようになりたいとずっと思ってるけど勉強できていないままなんだけど。
とか思いつつExを見る。

ExはKMP法で出現位置を調べて区間スケジューリングのようなことをすれば求められそうだけど、Tに短いものが多いと該当数が多すぎて計算量が駄目そうくらいまで考えて終了。
解説チラ見したら全然違っていた。



最終結果：ABCDEFの6完2000点、90分32秒、183位、パフォーマンス2274相当
レート変動：2038（Unrated）


パフォ2200台くらいの成績ならとりあえず満足。
GとExは弱いと自覚している分野でもあるので仕方ない。
その内やる気が出てきた時に埋めることにする。