ks2mのブログ

A - Swap Digit
- 思考過程
B - New Place
- 思考過程
C - Roller
- 思考過程

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

A - Swap Digit

思考過程

全ての桁について片側が大きくなるように偏らせる。
答えの桁数は $2N$ 程度なのでBigIntegerを用いて普通に掛け算してしまっても大丈夫そう？
結果的に通ったのでヨシだが、本当は $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$ 。
$K$ 回操作するとすると、 $S$ の後ろの $N-K$ 文字の順序関係は変わらないので、 $S$ の後ろ何文字の連続する部分文字列が $T$ の連続とは限らない部分列となっているか、後ろから貪欲に突き合わせて調べる。
個数が合っているなら、上記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$ 回以上行うと、同じ値が $2$ つ以上隣り合うところが $1$ 箇所はできる。
$B$ の要素が全て異なる場合、初めから $A=B$ でなければNo。なおこれを実装忘れて1ペナ。
　
$B$ に同じ値が $2$ つ以上隣り合うところが存在する場合、とりあえずそこを起点としてみる。
おおよそ $A$ が $B$ をrotateさせた数列になっていればできそうだと思ったりしたが、実験してみると同じ値の連続を $1$ 個にまとめた後の並びを見て、 $B$ が $A$ に部分列として含まれていればYesとなることがわかる。
$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$ 数の大小関係がわかるようになる。
あとは適当なソートアルゴリズムのようなことをすればできそう？