https://atcoder.jp/contests/agc029/tasks/agc029_c

問題概要

N個の文字列が順番に並んでおり、それぞれの長さが数列Aとして与えられる。すべての文字列は自分の左にある文字列より辞書順で真に小さい、という制約のもとで、そのような文字列の列が存在するか判定せよ。存在する場合には、そのような文字列の列を構成するために必要な最小の文字の種類数を求めよ。

N <= 2×10⁵

A <= 10⁹

解法

明らかに単調性があるので2分探索をする。このとき問題は「使える文字の種類数xが与えられたとき、題意を満たす文字列を作れるか」という判定問題になる。

最初の文字列から順に構成していくことを考えると、辞書順で小さい順という制約上、許される限り辞書順の小さい文字列を作っていくべきである。つまり作るべき文字列は「長さがAiかつ辞書順で前の文字列を超えないという条件を満たすもののうち、辞書順で最も小さい文字列」ということになる（ただし最初の文字列は全部aで埋めることにする）。

実際にそのような文字列を構成していく。隣り合う文字列S[i-1]とS[i]について、既にS[i-1]が定まっており、これからS[i]を決めていくものとする。このとき、A[i-1]とA[i]の大小関係から、以下のようにS[i]を決めることができる。

A[i-1] = A[i]のとき: S[i]はS[i-1]の末尾の文字をひとつインクリメントした文字列になる。もし末尾の文字がそれ以上インクリメントできないのであれば、足し算の繰り上がりのように、その桁は0に戻して隣の桁をインクリメントする。
A[i-1] > A[i]のとき: S[i-1]の長さがA[i]に一致するよう、S[i-1]の余分な末尾を切り落とした文字列Tをつくる。このときTはS[i-1]のprefixであり、このままだとS[i-1] > Tになってしまうので、↑と同じ要領でTの末尾をインクリメントし、これをS[i]とする。
A[i-1] < A[i]のとき: S[i-1]の長さがA[i]に一致するよう、S[i-1]の末尾に'a'を詰めこむ。これをS[i]とする。

もしインクリメントしたとき文字種が溢れてしまうようであれば、その文字種類数では構成不可能、ということになる。

あとはこれを実際にシミュレートしていけばよい。文字の種類数が膨大になるので、実際には文字列を扱うというよりも最大10⁹ケタのx進数(xは最大の文字種類数)を扱うような感じでやる。自分の実装では、巨大な桁数の場合にはほとんどの桁が0であるということを利用して、0でない桁だけをスタックで持つ、という感じにした。上述したとおり構成時に要求される操作は末尾を切ったりインクリメントしたりといった操作だけなので、数の任意の場所にアクセスできる必要はなく、一番うしろだけすぐ参照したり操作したりができればよいため。

感想

かなり意味わからないこと書いてるんじゃないか疑惑があってこわいね　あと自分の実装の計算量わからん

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

alias Digit = Tuple!(long, "n", long, "keta");

bool incr(ref DList!Digit queue, long keta, long base) {
    if (queue.empty || queue.back.keta != keta) {
        queue.insertBack(Digit(1L, keta));
        return true;
    } else if (queue.back.n + 1 < base) {
        queue.back.n += 1;
        return true;
    }

    long prev_keta = keta + 1;
    while (!queue.empty && queue.back.keta + 1 == prev_keta && queue.back.n + 1 == base) {
        if (queue.back.keta == 1) {
            return false;
        } else {
            prev_keta--;
            queue.removeBack;
        }
    }

    if (queue.empty || queue.back.keta + 1 != prev_keta) {
        queue.insertBack(Digit(1L, prev_keta - 1));
    } else {
        queue.back.n += 1;
    }

    return true;
}

bool check(int N, const long[] A, long base) {
    DList!Digit queue;

    foreach (i; 1..N) {
        if (A[i] > A[i-1]) {
            continue;
        }
        while (!queue.empty && queue.back.keta > A[i]) {
            queue.removeBack;
        }
        if (!incr(queue, A[i], base)) {
            return false;
        }
    }

    return true;
}

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;

    if ((N-1).iota.map!(i => A[i+1] - A[i] > 0).all) {
        writeln(1);
        return;
    }

    long hi = 10^^9 + 1;
    long lo = 1;
    while (hi - lo > 1) {
        long mid = (hi + lo) / 2;
        if (check(N, A, mid))
            hi = mid;
        else
            lo = mid;
    }

    hi.writeln;
}

nebukuro09の日記

AtCoder Grand Contest 029: C - Lexicographic constraints

問題概要

解法

感想

コード (D言語)