AtCoder Regular Contest 154

ARC

コンテスト前のレート：2025
レート通りのパフォーマンスが得られる順位：333位（1200点、66分15秒）

A - Swap Digit

問題

思考過程
  1. 全ての桁について片側が大きくなるように偏らせる。
  2. 答えの桁数は2N程度なのでBigIntegerを用いて普通に掛け算してしまっても大丈夫そう？
  3. 結果的に通ったのでヨシだが、本当はA, Bそれぞれmod取ってから掛け算しないとO(N^2)だった。でも後からコメントの内容に変えても1465ms→1387msでほぼ変わらず。何でだろう。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

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());
        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();
        br.close();

        for (int i = 0; i < n; i++) {
            if (a[i] < b[i]) {
                char t = a[i];
                a[i] = b[i];
                b[i] = t;
            }
        }

        BigInteger ba = new BigInteger(String.valueOf(a));
        BigInteger bb = new BigInteger(String.valueOf(b));
        BigInteger m = BigInteger.valueOf(998244353);
        BigInteger ans = ba.multiply(bb).mod(m);
        // BigInteger ans = ba.mod(m).multiply(bb.mod(m)).mod(m);
        System.out.println(ans.toString());
    }
}

ここまで3分40秒＋0ペナ。178位。


B - New Place

問題

思考過程
  1. まず登場する各文字の個数が異なれば-1。
  2. K回操作するとすると、Sの後ろのN-K文字の順序関係は変わらないので、Sの後ろ何文字の連続する部分文字列がTの連続とは限らない部分列となっているか、後ろから貪欲に突き合わせて調べる。
  3. 個数が合っているなら、上記2.で対応せずに残ったSの前何文字かを適切に操作すれば必ず作れる。
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());
        char[] s = br.readLine().toCharArray();
        char[] t = br.readLine().toCharArray();
        br.close();

        int[] cs = new int[26];
        int[] ct = new int[26];
        for (int i = 0; i < n; i++) {
            cs[s[i] - 'a']++;
            ct[t[i] - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cs[i] != ct[i]) {
                System.out.println(-1);
                return;
            }
        }

        int x = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            while (x >= 0 && s[i] != t[x]) {
                x--;
            }
            if (x >= 0 && s[i] == t[x]) {
                x--;
            } else {
                System.out.println(i + 1);
                return;
            }
        }
        System.out.println(0);
    }
}

ここまで10分00秒＋0ペナ。100位。


C - Roller

問題

思考過程
  1. 操作を1回以上行うと、同じ値が2つ以上隣り合うところが1箇所はできる。
  2. Bの要素が全て異なる場合、初めからA=BでなければNo。なおこれを実装忘れて1ペナ。
    　
  3. Bに同じ値が2つ以上隣り合うところが存在する場合、とりあえずそこを起点としてみる。
  4. おおよそAがBをrotateさせた数列になっていればできそうだと思ったりしたが、実験してみると同じ値の連続を1個にまとめた後の並びを見て、BがAに部分列として含まれていればYesとなることがわかる。
  5. Bの起点は上記3.で固定して、Aの起点を全探索して突き合わせを行う。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            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]);
            }
            sa = br.readLine().split(" ");
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                b[i] = Integer.parseInt(sa[i]);
            }

            List<Obj> lista = runLength(a);
            List<Obj> listb = runLength(b);
            int sizea = lista.size();
            int sizeb = listb.size();
            int b1 = -1; // Bの起点
            for (int i = 0; i < sizeb; i++) {
                if (listb.get(i).c > 1) {
                    b1 = i;
                    break;
                }
            }
            // 2
            if (b1 == -1) {
                boolean flg = true;
                for (int i = 0; i < n; i++) {
                    if (a[i] != b[i]) {
                        flg = false;
                        break;
                    }
                }
                if (flg) {
                    pw.println("Yes");
                } else {
                    pw.println("No");
                }
                continue;
            }

            boolean flg = false;
            int b2 = b1 + sizeb;
            // 5. Aの起点全探索
            for (int a1 = 0; a1 < sizea; a1++) {
                int a2 = a1 + sizea;
                int x = a1;
                boolean flg2 = true;
                // 部分列として含まれるかの判定
                for (int y = b1; y < b2; y++) {
                    Obj ob = listb.get(y % sizeb);
                    boolean flg3 = false;
                    while (x < a2) {
                        Obj oa = lista.get(x % sizea);
                        x++;
                        if (oa.v == ob.v) {
                            flg3 = true;
                            break;
                        }
                    }
                    if (!flg3) {
                        flg2 = false;
                        break;
                    }
                }
                if (flg2) {
                    flg = true;
                    break;
                }
            }
            if (flg) {
                pw.println("Yes");
            } else {
                pw.println("No");
            }
        }
        pw.flush();
        br.close();
    }

    // ランレングス圧縮
    static List<Obj> runLength(int[] a) {
        List<Obj> list = new ArrayList<>();
        Obj o = new Obj();
        o.v = a[0];
        o.c = 1;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == o.v) {
                o.c++;
            } else {
                list.add(o);
                o = new Obj();
                o.v = a[i];
                o.c = 1;
            }
        }
        list.add(o);
        if (list.size() > 1) {
            Obj o1 = list.get(0);
            Obj o2 = list.get(list.size() - 1);
            if (o1.v == o2.v) {
                o1.c += o2.c;
                list.remove(list.size() - 1);
            }
        }
        return list;
    }

    static class Obj {
        int v, c;
    }
}

ここまで54分46秒＋1ペナ。214位。



残りはほぼDに費やす。Dで煮詰まってEとFも問題を見たが、題意も理解できず。

Dで考えたのは、まず質問の回数はNlogNくらい。
ランダムに質問するとYesが返ってくる可能性の方がかなり高そう。
Noが返ってきたら何がわかるか？　P_i, P_jの少なくとも片方は\frac{N}{2}以下。
kを固定して(i, i, k)でiを全探索したら、\frac{P_k}{2}以下である要素が列挙できる。
これを繰り返せば2N回くらいで1が特定できる。
1が特定できれば、以降の質問では2数の大小関係がわかるようになる。
あとは適当なソートアルゴリズムのようなことをすればできそう？

くらいまでは考えられており、1を特定するところまで実装したくらいで時間切れ。



最終結果：ABCの3完1200点、59分46秒、319位、パフォーマンス2047
レート変動：2025→2027（+2）


Dは惜しいところまでいったと思うが、ソートを自力で書き慣れておらず、解説見ると2N回をN回に減らさないと怪しい気もするので、実際に通すにはまだあと最低30分以上は必要そう。
まあ解法がおおよそ合っていただけでも。

同レート帯の中では知識も実装力もなさそうなんだけど、ほんとどうやって戦っているんだろう。
勘だけまあまあいいのかもしれない。