2019-01-06

CODE FESTIVAL 2016 Final: F - Road of the King

問題記録 AtCoder DP 順列のDP

https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_f

問題概要

N個の町があり、これらの間にはひとつも道が存在しない。はじめ王様は町1におり、今いる町からN個の町のどれかへ移動することをM回繰り返す（移動元と移動先は同じでもいい）。各移動のたびに、移動元の町aから移動先の町bに一方通行の道が作られる。M回の移動の終了後に道だけを使って任意の2つの町が行き来できるようになっているという条件を満たすような移動の仕方が何通りあるか求めよ。

解法

移動の性質を考えると以下のことが言える。

性質1. 先に訪れた町は後に訪れるすべての町に必ず到達可能
性質2. 既出の町xへの後戻りが発生したとき、これまでに訪れているすべての町からxへ到達可能になる

性質1は移動によって有向辺が張られていく様子を想像するとわかりやすいと思う。性質2は性質1から導くことができる。さらにこれらを用いて以下のことが言える。

性質3. スタート地点である町1への後戻りが発生したとき、これまでに訪れているすべての町は相互に到達可能になる
性質4. 性質3によって相互に到達可能になった町のいずれかへの後戻りが発生したときも、同様にこれまでに訪れているすべての町は相互に到達可能になる
性質5. 上記の性質3, 4以外ですべての町が相互に到達可能になるようなことはない。

これは性質1より常に「町1->これまでに訪れているすべての町」が到達可能であることからわかる。ここまでを踏まえると以下のようなDPが立つ。

dp(i, S, T): i回の移動を行って、町集合Sに訪問済であり、町集合T内の町はすべて相互に到達可能になっているような移動の仕方の総数

求めたいのはdp(M, 全部の町, 全部の町)である。町集合の部分がネックになるが、実はこの問題では愚直に集合そのものを持つ必要はない。スタート地点である町1以外のすべての町は対称なので、必ず番号順に町を訪れると仮定してしまってよい。答えに関しては最後に[2, 3, ..., N]の任意の置換の総数(N-1)!を掛ければ辻褄を合わせられる。というわけでDPは以下のように軽くできる。

dp(i, j, k): i回の移動を行って、町1〜jまで訪れており、町1〜kがすべて相互に到達可能になっているような移動の仕方の総数

遷移は「町(1〜k)のどこかに移動する（これによって町(1〜jが)すべて相互に到達可能になる）」「町(k+1〜j)のどこかに移動する」「新しい町(j+1)に移動する」のどれかである。これらはO(1)で計算できるのでDPの計算量はO(N² M)となる。

感想

なんか考えてたらできた　うれしい

コード (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;

immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];

    auto dp = new long[][][](2, N, N);
    dp[0][0][0] = 1;

    int cur = 0;
    int tar = 1;

    foreach (i; 0..M) {
        foreach (j; 0..N) {
            foreach (k; 0..N) {
                dp[tar][j][k] = 0;
            }
        }
        foreach (j; 0..N) {
            foreach (k; 0..N) {
                if (dp[cur][j][k] == 0) {
                    continue;
                }
                if (j < N - 1) {
                    (dp[tar][j+1][k] += dp[cur][j][k]) %= MOD;
                }
                (dp[tar][j][k] += dp[cur][j][k] * (j - k) % MOD) %= MOD;
                (dp[tar][j][j] += dp[cur][j][k] * (k + 1) % MOD) %= MOD;
            }
        }
        swap(cur, tar);
    }

    long ans = dp[cur][N-1][N-1];
    foreach (i; 1..N) ans = ans * i % MOD;
    ans.writeln;
}

2019-01-05

AtCoder Grand Contest 028: C - Min Cost Cycle

問題記録 AtCoder AGC AGC #028 貪欲

https://atcoder.jp/contests/agc028/tasks/agc028_c

問題概要

N頂点の有向グラフがあり、各頂点iは2つの値Ai, Biを持っている。このグラフはすべての点対x, yに対して辺x->yが存在し、その重みはmin(Ax, By)である。グラフのすべての頂点をちょうど1回ずつ通るような有向サイクルのうち、含まれる辺の重みの和が最小となるときの値を求めよ。

N <= 10⁵

解法

サイクルを作ったとき、ある辺x->yのコストはAxもしくはByである。言い換えると各辺はAかBのどちらかに塗り分けられることになる。なので各頂点は「出る辺がAかBか」「入る辺がAかBか」で4パターンに分類することができる。このことからある頂点iを以下の4パターンに分類できる。

出る辺がAで入る辺がA: Aiは最終的なコストに含まれるが、Biは最終的なコストに含まれない。
出る辺がAで入る辺がB: AiもBiも最終的なコストに含まれる。
出る辺がBで入る辺がA: AiもBiも最終的なコストに含まれない。
出る辺がBで入る辺がB: Aiは最終的なコストに含まれないが、Biは最終的なコストに含まれる。

実は各Ai, Biを一緒くたにソートした上で小さい値から都合よく貪欲に取っていっても、上の塗り分けを適切にやればほとんどの場合そのような頂点の配置を実現できる。

唯一実現できないのが「すべての頂点からちょうど1つずつAかBを取っている」かつ「AとBのどちらも少なくとも1つ以上取っている」場合である。「すべての頂点からちょうど1つずつAかBを取っている」ということは、上でいうパターン2, パターン3の頂点が存在しないということである。ということはサイクルにおいてその頂点を境にA, Bが切り替わるような頂点が存在しないことになる。つまりサイクルの辺はすべてAもしくはすべてBのどちらかしかありえない。しかしこれは「AとBどちらも少なくとも1つ以上取っている」に矛盾する。よってこのようなとり方は不可能である、ということになる。

そのため最終的な解としては、まずAiとBiを全部並べてソートする（ただし値の頂点番号とA, Bの分類は覚えておく）。次に小さい方から貪欲にN個取る。もしこれが上の実現不可能パターンに当てはまらなければこの合計をそのまま答えとする。もし当てはまっているのであれば、そのままでは駄目なので辻褄をあわせる必要がある。単純に考えるとN番目と(N+1)番目を入れ替えればよさそうだが、このときこれらの頂点番号が一緒だと入れ替えても実現不可能パターンから外れない。なのでその場合にはN番目と(N+2)番目の入れ替えと(N-1)番目と(N+1)番目の入れ替えを試して小さい方を取るようにする。

計算量はソートの部分が一番重くてO(NlogN).

感想

わからなかった. 下界が簡単にわかる -> 実際にそれが（ほとんどの場合）達成できるという問題だと思えば結構類型的なのかな

コード (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;

void main() {
    auto N = readln.chomp.to!int;
    auto AB = N.iota.map!(_ => readln.split.map!(to!long).array).array;

    Tuple!(long, int, int)[] C;

    foreach (i; 0..N) {
        foreach (j; 0..2) {
            C ~= tuple(AB[i][j], i, j);
        }
    }
    C.sort!"a[0] < b[0]";

    long ans = 0;
    auto cnt1 = new int[](N);
    auto cnt2 = new int[](2);

    foreach (i; 0..N) {
        ans += C[i][0];
        cnt1[C[i][1]] += 1;
        cnt2[C[i][2]] += 1;
    }

    if (cnt1.map!(c => c == 1).all && cnt2[0] != 0 && cnt2[1] != 0) {
        if (C[N-1][1] == C[N][1]) {
            ans = min(ans - C[N-2][0] + C[N][0], ans - C[N-1][0] + C[N+1][0]);
        } else {
            ans = ans - C[N-1][0] + C[N][0];
        }
    }

    ans.writeln;
}

2019-01-05

Codeforces Hello 2019: D. Makoto and a Blackboard

問題記録 Codeforces 素因数分解期待値

https://codeforces.com/contest/1097/problem/D

問題概要

整数N, Kが与えられる。Nの約数のうちひとつを等確率で選び、それでNを割る、という操作をK回繰り返すとき、最終的なNの値の期待値を求めよ。

N <= 10¹⁵

K <= 10⁴

解法

Nの約数の数は最大ケースで30000個近くあるため、約数列挙して素朴なDPをやるのでは間に合わない。

Nを素因数分解した上で操作を考えてみると、一度の操作は素因数分解の指数のところをランダムに減らしていく操作に相当する。ここで各素因数について指数の減り方は独立なので、素因数ごとに独立に問題を解いていくことができる。つまりE(n, k)を整数nに対してk回操作を行ったあとの期待値とすると、

N = P0 ^ a × P1 ^ b × P2 ^ c × ...

と素因数分解されるとき、

E(N, K) = E(P0 ^ a, K) × E(P1 ^ b, K) × E(P2 ^ c, K) × ...

という風に独立にできる。指数部は最大でも50程度の値までしか取らず、素因数の数も同程度に収まるので、各素因数ごとにDPをしてEを求めていっても十分間に合う。

注意点として元のNが大きいせいでMODを取らずに掛け算するとオーバーフローする場合があるので気をつける。

感想

素因数ごとに独立！素因数ごとに独立！素因数ごとに独立！素因数ごとに独立！素因数ごとに独立！素因数ごとに独立！

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;

const ll MOD = 1000000007;

ll N, K, M;
vector<ll> P;
vector<ll> C;

ll powmod(ll a, ll x, ll m) {
    ll ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

ll solve2(ll p, ll c) {
    vector<VL> dp = vector<VL>(K+1, VL(c+3, 0));
    dp[0][c] = 1;

    REP(i, K) {
        REP(j, c+1) {
            ll v = dp[i][j] * powmod(j+1, MOD-2, MOD) % MOD;
            (dp[i+1][0] += v) %= MOD;
            (dp[i+1][j+1] -= v) %= MOD;
        }
        REP(j, c+1) {
            (dp[i+1][j+1] += dp[i+1][j]) %= MOD;
        }
    }

    ll ans = 0;

    REP(j, c+1) {
        ans += dp[K][j] * powmod(p % MOD, j, MOD) % MOD;
        ans %= MOD;
    }

    return (ans % MOD + MOD) % MOD;
}

void solve() {
    cin >> N >> K;
    ll n = N;

    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            P.push_back(i);
            C.push_back(0);
            M += 1;
        }
        while (n % i == 0) {
            C.back() += 1;
            n /= i;
        }
    }

    if (n > 1) {
        P.push_back(n);
        C.push_back(1);
        M += 1;
    }

    ll ans = 1;

    REP(i, M) {
        ans = ans * solve2(P[i] % MOD, C[i]) % MOD;
    }

    cout << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    solve();
}

2019-01-04

NJPC2017: G - 交換法則

問題記録 AtCoder NJPC NJPC2017 文字列

https://atcoder.jp/contests/njpc2017/tasks/njpc2017_g

問題概要

2つの文字列に対する演算子@が次のとおり定義される。

s@t = min(s,t) + max(s,t)

ここで+は結合を表し、max/minは辞書順比較での大小を表す。文字列Sが与えられたとき、その文字列を1文字ずつに分解した後、@演算子と()のみを使った式によってSを復元できるか判定せよ。

|S| <= 3000

解法

はじめに文字列に含まれる中で辞書順で最も小さい文字を求める。以降ではこれがaだったと仮定して話を進める。

自明なケースから処理する。まず先頭の文字がaでなければ明らかに復元は明らかに不可能である。またaaaxxx...のようにaが先頭の連続した部分にしか含まれていない場合には必ず復元可能である（最初にaaaを作ってあとから別の文字をくっつけていけばいい）。

上の自明な2ケースを除くと、残るのは「先頭がa」かつ「aの繰り返しであるような部分が2箇所以上ある」文字列である。この文字列は例えば aaxxxaxaaaxx のような形をしている。この文字列をxとaの境で区切ると、aaxxx / ax / aaaxx のような形になる。ここでこの3つのそれぞれに区切られた文字列は必ず作れる、ということに注意する（なぜなら↑で見たとおりaが先頭かつaが先頭の連続部分にしか含まれていないという自明ケースに当てはまっているため）。すると次の問題はこれらの文字列をこの順番で繋げることは可能か？という点に移る。そしてこれは最初の問と全く同じ構造をしているので、この文字列列に対して再帰的に同じ処理をしていけば答えを出すことが可能である。最初の問が文字同士の比較だったのに対し再帰版の問が文字列同士の比較になっているが、最初の問で「文字」を「長さ1の文字列」として扱ってしまえば完全に同じ形の問題として扱える。

1度の処理でO(S²)かかるが、引数となる文字列列の要素数は必ず半分以下になっていくため、再帰の深さはO(log(|S|))で済む。よって全体でO(S² log(|S|)).

感想

実装は確かに再帰なんだけどやってることはボトムアップという感じがあってこんがらがった

コード (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;


bool solve(string[] a) {
    auto n = a.length.to!int;
    auto m = a.reduce!min;
    if (a.front != m) return false;


    int[] tmp = [0];

    foreach (i; 1..n) {
        if (a[i-1] != m && a[i] == m) {
            tmp ~= i;
        }
    }

    if (tmp.length == 1) return true;


    string[] aa;

    foreach (i; 0..tmp.length.to!int) {
        int l = tmp[i];
        int r = i + 1 >= tmp.length ? a.length.to!int : tmp[i+1];
        string s;
        foreach (j; l..r) {
            s ~= a[j];
        }
        aa ~= s;
    }

    return solve(aa);
}


void main() {
    auto S = readln.chomp;
    auto T = S.length.iota.map!(i => S[i].to!string).array;
    writeln( T.solve ? "Yes" : "No" );
}

2019-01-03

CODE FESTIVAL 2018 Final: G - Chicks and Cages

問題記録 AtCoder コドフェス2018本戦 DP

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_g

問題概要

N羽のひよこがいて、ひよこiの大きさはAiである。ひよこをM個のケージに分けて入れるとき、各ひよこは自分とおなじケージにいるひよこの大きさの和と等しいストレスを受ける。全ひよこのストレスの和を最小化するようにひよこを分けたとき、その最小値を求めよ。

N, M <= 2000

解法

DPをしようと思うと、以下のような形になる。

DP(i, j): i匹目までのひよこをj個のケージに分けて入れたときの最小値

このDPで遷移を普通にやろうとすると次のグループの大きさを全て見る必要があるため、累積和を使ってもO(N)かかってしまい、状態数のO(NM)と合わせてO(N² M)と厳しいオーダーになってしまう。

想定解ではこの遷移を高速化する。そのために必要なアイデアは「数の多いグループには小さいひよこを入れた方が良い」ということである。ひよこiが羽数nのケージに入った場合、最終的な値には A[i] × n が加算される。つまり全部のひよこについての A[i] × (ケージの羽数) を足した数が最終的な値ということになる。よって仮にすべてのケージの羽数が定まっているならば、A[i]の小さいひよこをnの大きいケージに貪欲に割り当てていくのが当然最適となる。つまりAを小さい順に並べて、大きいケージから順番に詰め込んでいくことになる。

以上の考察より、DPの遷移を次のとおり高速化できる。まずAを小さい順にソートする。先の考察に従えば、1つのグループはソート後のAの連続部分列になる。さらに「小さいひよこほど大きいケージへ」が最適であるため、後ろのひよこに作るケージは前に作るケージと同じサイズかもしくは小さいはずである。これによって考慮するべきケージのサイズが後半ほど枝刈りできて通るようになる（前からケージを作っていくとして、これからサイズnのケージを作るとき、これまで作ったm個のケージはすべてサイズn以上と仮定できる。ということはこれまでの割当でひよこを最低でも n * m 匹は使っているはずで、もしこの数が今見てるひよこのインデックスを追い越していたらNGなので、そのサイズ以上のケージの計算は飛ばせる）。

公式解説によると上の方法をとった場合の計算量はO(NMlogN).

感想

いや、わからん……………… 「ひよこiの寄与はA[i]*ケージのサイズ」に着目しないと始まらない感じだが、着目できていたとてDPのこういう高速化に使う発想はちょっと出てきそうにない　うぐぐ

コード

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;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto A = readln.split.map!(to!long).array;
    A.sort();

    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = B[i] + A[i];

    auto dp = new long[][](N+1, M+1);
    foreach (i; 0..N+1) fill(dp[i], 1L<<59);
    dp[0][0] = 0;

    foreach (i; 0..N) {
        foreach (j; 0..M) {
            foreach (k; i..N) {
                int size = k - i + 1;
                if (size * j > N) break;
                dp[k+1][j+1] = min(dp[k+1][j+1], dp[i][j] + (B[k+1] - B[i]) * size);
            }
        }
    }

    dp[N][M].writeln;
}

2019-01-01

SoundHound Inc. Programming Contest 2018 (春): C - 広告

問題記録 SoundHound2018春 AtCoder 2部グラフ最大安定集合

https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c

問題概要

各マスが '*' もしくは '.' で構成されたr行c列のグリッドが与えられる。'.'のマスに広告を打てるが、広告を打ったマスの上下左右4マスには広告を打つことができなくなる。最大で何マスに広告を打つことができるか求めよ。

r, c <= 40

解法

'.'マスを頂点とし、上下左右で繋がった'.'マス間に辺を張ったグラフを考えると、問われているのは「このグラフの最大安定集合のサイズを求めよ」と同じことである。
グリッドグラフは2部グラフである。
2部グラフの最大安定集合は最大フローを用いて求めることができる。

2部グラフの最大安定集合の具体的な求め方は↓のdrkenさんのスライドを見ればわかる（ありがとうございます）。

二部グラフの最小点被覆と最大安定集合と最小辺被覆の求め方

感想

知ってればやるだけだが知らなかったのでやれなかったし記事を書いた

コード (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;

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto A = H.iota.map!(_ => readln.chomp).array;

    auto G = new BipartiteGraph(H * W);
    int cnt = 0;

    foreach (r; 0..H) {
        foreach (c; 0..W) {
            if (A[r][c] == '*') {
                cnt += 1;
                continue;
            }
            foreach (k; 0..2) {
                int nr = r + k;
                int nc = c + 1 - k;
                if (nr >= 0 && nr < H && nc >= 0 && nc < W && A[nr][nc] == '.') {
                    G.add_edge(r * W + c, nr * W + nc);
                }
            }
        }
    }

    G.construct;
    writeln(G.maximum_independent_set.length.to!int - cnt);
}

class BipartiteGraph {
    int n;
    int[][] adj;
    bool[] color;

    this (int n) {
        this.n = n;
        adj = new int[][](n);
        color = new bool[](n);
    }

    void add_edge(int u, int v) {
        adj[u] ~= v;
        adj[v] ~= u;
    }

    bool construct() {
        auto used = new bool[](n);

        bool dfs(int u, bool c) {
            if (used[u])
                return color[u] == c;

            used[u] = true;
            color[u] = c;

            if (adj[u].map!(v => used[v] && color[v] == c).any)
                return false;
            if (adj[u].map!(v => !used[v] && !dfs(v, c^1)).any)
                return false;

            return true;
        }

        foreach (u; 0..n)
            if (!used[u] && !dfs(u, 0))
                return false;

        return true;
    }

    int[] minimum_vertex_cover() {
        int s = n;
        int t = n + 1;
        auto ff = new FordFulkerson(n + 2, s, t);
        foreach (i; 0..n) if (color[i] == 0) ff.add_edge(s, i, 1);
        foreach (i; 0..n) if (color[i] == 1) ff.add_edge(i, t, 1);
        foreach (i; 0..n) if (color[i] == 0) foreach (j; adj[i]) ff.add_edge(i, j, 1);
        ff.run;

        auto used = new bool[](n);
        auto G = new int[][](n);
        foreach (i; 0..n) if (color[i] == 1) foreach (j; adj[i])
            if (ff.flow[j][i])
                G[j] ~= i;
            else
                G[i] ~= j;

        void dfs(int u) {
            if (used[u]) return;
            used[u] = true;
            foreach (v; G[u]) dfs(v);
        }

        foreach (i; 0..n) if (!used[i] && color[i] == 0 && ff.flow[s][i]) dfs(i);

        return n.iota.filter!(i => (color[i] == 0 && !used[i]) || (color[i] == 1 && used[i])).array;
    }

    int[] maximum_independent_set() {
        int[] ret;
        int[] mvc = minimum_vertex_cover;

        if (mvc.empty)
            return n.iota.array;

        for (int i = 0, j = 0; i < n; ++i) {
            if (mvc[j] == i) {
                if (j + 1 < mvc.length)
                    ++j;
            } else {
                ret ~= i;
            }
        }

        return ret;
    }
}


class FordFulkerson {
    int N, source, sink;
    int[][] adj;
    int[][] flow;
    bool[] used;

    this(int n, int s, int t) {
        N = n;
        source = s;
        sink = t;
        assert (s >= 0 && s < N && t >= 0 && t < N);
        adj = new int[][](N);
        flow = new int[][](N, N);
        used = new bool[](N);
    }

    void add_edge(int from, int to, int cap) {
        adj[from] ~= to;
        adj[to] ~= from;
        flow[from][to] = cap;
    }

    int dfs(int v, int min_cap) {
        if (v == sink)
            return min_cap;
        if (used[v])
            return 0;
        used[v] = true;
        foreach (to; adj[v]) {
            if (!used[to] && flow[v][to] > 0) {
                auto bottleneck = dfs(to, min(min_cap, flow[v][to]));
                if (bottleneck == 0) continue;
                flow[v][to] -= bottleneck;
                flow[to][v] += bottleneck;
                return bottleneck;
            }
        }
        return 0;
    }

    int run() {
        int ret = 0;
        while (true) {
            foreach (i; 0..N) used[i] = false;
            int f = dfs(source, int.max);
            if (f > 0)
                ret += f;
            else
                return ret;
        }
    }
}

2019-01-01

AtCoder Grand Contest 029: C - Lexicographic constraints

問題記録 AtCoder AGC AGC #029 辞書順文字列

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;
}