DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦: C - グラフいじり

問題記録 AtCoder DDCC 有向グラフ 閉路

https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_c

問題概要

N頂点M辺の強連結な重み付き有向グラフが与えられる。ひとつの辺の重みを自由に変更できるとき、グラフのすべての単純サイクルについて、サイクル内に含まれる辺の重みの和が0となるようにすることができるか判定せよ。

N <= 300

M <= N2 - N

解法

ここの部分は以下の記事を言い換えてるだけなので、見ていない方はまずそちらから目を通すことをおすすめします。わかりやすいです。

まず辺の重みを変更できるという条件を一旦忘れて、辺の重みが全てそのままであるとき条件が満たせるかどうかを考える。これは実はDFS1回で判定可能である。具体的には通った辺の重みを足しながらDFSしていき、初訪問の頂点に当たったときはそのとき持っている合計重みをその頂点の値として記録しておく。訪問済みの頂点を再び訪れた場合、最初にその頂点に記録した値と現在持っている値が異なっていたら矛盾が生じるため条件は満たされない。逆にDFS全体でこのような矛盾が一度も生じなければ条件は満たされる。これはもし元の頂点に帰ってきたのであればどこかのサイクルをちょうど一回りしているはずで、サイクルをちょうど一回りしてるなら戻ってくるまでに取った重みの合計は0のはずなので、最初の値と同じでなければおかしい、という理屈である。

では辺をひとつ自由に変更できるという条件の元ではどうなるか。単純な方法として、変更する辺を総当たりするという方法が考えられる。この場合変更する辺eをひとつ決め、eが入っていく頂点を始点として上のDFSをやる。始点を固定する理由は、eを必ずサイクルの最後に訪れるようにするためである。上のDFSで矛盾が検出されるのはサイクルをちょうど一周したときで、このような始点の決め方をすればe上を移動した瞬間ちょうどサイクルができることになる。つまりeが関わっているサイクルすべてにおいて、eが最後の通る辺になる。これによって「もしe以外で矛盾が起きたらその時点でNG」「eで矛盾が起きたらちょうどよく調整が起きたことにして無視」という動きができる。これをすべての辺で試して、ひとつでもOKのものがあればOKということになる。

上の方法は辺の列挙にO(M), 1度のDFSでもO(M)かかりO(M2) = O(N4)となり間に合わない（DFSもO(M)なのは1度のDFSですべての辺を舐める必要があるため）。だがここである頂点vを始点とし、vに入る辺全部を変更候補として前段のDFSをやっても実は問題がない。なぜならこれらの辺は同じ単純サイクルには絶対に含まれないからである。ゆえにこのうちのひとつの辺の変更が他の辺の担当するサイクルに影響せず、独立に矛盾チェックを行うことができる。よって手続きとしては始点vを決めてDFSを行い、vに入ってくる辺で矛盾が起きたらカウントを+1し、カウントが2を超えたらNGとすればよい。もし無関係の辺で矛盾が起きたらこれまで同様即アウトとする。この方法では始点の総当たりでO(N), DFSでO(N2)の計O(N3)になるので通る。

感想

感覚でわかっても言葉で説明するのがむずい

コード (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 N = s[0];
    auto M = s[1];
    auto G = new Tuple!(int, long)[][](N);
    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long);
    }


    auto used = new bool[](N);
    auto cost = new long[](N);
    int cnt;

    bool dfs(int n, long c, int start) {
        if (used[n]) {
            if (cost[n] == c) return true;
            if (n != start) return false;
            if (cnt == 1) return false;
            cnt += 1;
            return true;
        }
        used[n] = true;
        cost[n] = c;
        foreach (e; G[n]) {
            if (!dfs(e[0], c+e[1], start)) return false;
        }
        return true;
    }

    foreach (start; 0..N) {
        used[] = false;
        cost[] = 0;
        cnt = 0;
        if (dfs(start, 0, start)) {
            writeln("Yes");
            return;
        }
    }

    writeln("No");
}

Educational DP Contest / DP まとめコンテスト: W - Intervals

問題記録 AtCoder DPまとめコンテスト DP

https://atcoder.jp/contests/dp/tasks/dp_w

問題概要

'0'と'1'のみからなる長さNの文字列を考える。M個のスコア条件(l, r, a)が与えられたとき、文字列の区間[l, r]のうち少なくとも1文字が'1'であればa点を得る。文字列を自由に構成できるとき、スコアの最大値を求めよ。

N, M <= 2*105

-109 <= a <= 109

解法

文字列を左から構成していくものとして、以下のDPを考える。

dp(i): 最後に'1'を置いたのがi文字目であるときの最大スコア

dp[i]の値を決めるときのことを考えてみる。もしiに被っている区間が [x, y] のひとつだけで、この区間のスコアがaだったとすると、遷移は以下のようになる。

dp[i] = max( max(dp[0〜x-1] + a), max(dp[x〜i-1]) )

この式は「もし最後に1を置いたのがxより前であるなら、ここで1を置いたとき初めて[x, y]が有効になって自動的にa点が入る」と「既にx〜i-1のどこかに1を置いているのでiに新たに1を置いても何も起こらない」の2パターンを見て大きい方を取る、ということを表している。（dp[i]ではiに1を置いたときのことを考えているので、どちらが取られるにせよaの値は織り込まれているという点に注意する）

ひとつのiに対して被る区間が複数ある場合でも考え方は同じ（「区間が被らない場所から遷移してくる場合にはその区間の点数を足す」「区間が被っている場所から遷移してくる場合には点数は足さない」）。つまり現在のiに被っているすべての区間[x, y]について、dp[0] 〜 dp[x-1]に一律にその区間の点数を足しておいた上で、dp[0〜i-1]までのmaxをとるとdp[i]の値となる。

これは尺取りみたいなやつとかで現在のiに被っている区間を管理しつつ、新たな区間[x, y]が入ってきたらdp[0]〜dp[x-1]にスコアを加算する、抜ける区間があったらdp[0]〜dp[x-1]から最初に足したぶんのスコアを引く、dp[i]の値にはdp[0]〜dp[i-1]のmaxを採用する、という操作で実現できる。区間加算、区間maxができればよいので遅延セグ木とかを使えばok.

解法

kmjpさんの解説を読んで解いた。既に確定しているはずの過去のdpテーブルの値を弄る、というところに凄い違和感があってなかなか腑に落ちなかったが、お気持ち的にはDPテーブルを活用して遷移の前計算をしているという風に捉えればいいんだろうか

コード (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 INF = 1L<<59;

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

    auto st = new LazySegmentTree!(long, long, max, (a,b)=>a+b, (a,b)=>a+b, (a,b)=>a, -INF, 0L)(N+1);
    st.table[] = 0L;
    auto pq = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[1] > b[1]")();

    for (int i = 1, p = 0; i <= N; ++i) {
        while (p < M && i >= LRA[p][0]) {
            pq.insert(tuple(LRA[p][0], LRA[p][1], LRA[p][2].to!long));
            st.update(0, LRA[p][0]-1, LRA[p][2].to!long);
            ++p;
        }

        auto v = st.query(0, i-1);
        st.update(i, i, v);

        while (!pq.empty && pq.front[1] <= i) {
            st.update(0, pq.front[0]-1, -pq.front[2].to!long);
            pq.removeFront;
        }
    }

    st.query(0, N).writeln;
}



class LazySegmentTree(T, L, alias opTT, alias opTL, alias opLL, alias opPrd, T eT, L eL) {
    T[] table;
    L[] lazy_;
    int n;
    int size;

    this(int n) {
        this.n = n;
        size = 1;
        while (size <= n) size <<= 1;
        size <<= 1;
        table = new T[](size);
        lazy_ = new T[](size);
        table[] = eT;
        lazy_[] = eL;
    }

    void push(int i, int a, int b) {
        if (lazy_[i] == eL) return;
        table[i] = opTL(table[i], opPrd(lazy_[i], b - a + 1));
        if (i * 2 + 1 < size) {
            lazy_[i*2] = opLL(lazy_[i*2], lazy_[i]);
            lazy_[i*2+1] = opLL(lazy_[i*2+1], lazy_[i]);
        }
        lazy_[i] = eL;
    }

    T query(int l, int r) {
        if (l > r) return eT;
        return query(l, r, 1, 0, n-1);
    }

    T query(int l, int r, int i, int a, int b) {
        if (b < l || r < a) return eT;
        push(i, a, b);
        if (l <= a && b <= r) {
            return table[i];
        } else {
            return opTT(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b));
        }
    }

    void update(int l, int r, L val) {
        if (l > r) return;
        update(l, r, 1, 0, n-1, val);
    }

    void update(int l, int r, int i, int a, int b, L val) {
        if (b < l || r < a) {
            push(i, a, b);
        } else if (l <= a && b <= r) {
            lazy_[i] = opLL(lazy_[i], val);
            push(i, a, b);
        } else {
            push(i, a, b);
            update(l, r, i*2, a, (a+b)/2, val);
            update(l, r, i*2+1, (a+b)/2+1, b, val);
            table[i] = opTT(table[i*2], table[i*2+1]);
        }
    }
}

Educational DP Contest / DP まとめコンテスト: T - Permutation

問題記録 AtCoder DPまとめコンテスト DP 順列のDP

https://atcoder.jp/contests/dp/tasks/dp_t

問題概要

整数Nと長さN-1の文字列Sが与えられる。Sは'>'と'<'のみからなり、長さNの数列における隣り合う値の大小関係を表す。(1, 2, ..., N)のすべての順列のうちSの表す大小関係に従うものは何通りあるか。

N <= 3000

解法

値を左から確定させていくことを考えると、単純なDPは以下のようになる。

dp(i, j, T): i番目まで決めていて、最後に置いた値がjであり、残っている未使用の値の集合がTであるような場合の数

このとき遷移は、対応する文字が'>'であればTの中からjより小さい値を選び、'<'であればjより大きい値を選ぶ、という形になる。このことを踏まえると、ひとつ前に選んだ数字とこれから選ぶ数字の大小関係が本質的な情報である。よって状態を以下のようにまとめてしまうことができる。

dp(i, j): i番目まで決めていて、最後に置いた値が「残っている未使用の値のうちj番目に小さい値」であるような場合の数

もし直前に「残っている中で2番目に小さい値」を置いており、次の記号が'<'であるとする。すると今回置けるのは「残っている中で2番目以上の値」である（以下の画像参照）。

f:id:fluffyowl:20190108124728p:plain

このようにすると前回取った値と大小記号だけで次に取れる値が決まるのでdpを埋めていくことができる。上の例でいくと、i回目に2を置いて記号が'<'のとき、遷移は dp[i][2] を dp[i+1][2～4] に一律に足す操作となる。これは区間への加算になるが、いもす法とかでうまいことやれば i -> i+1 の遷移全体をO(N)で計算できるので、結局O(N2)で最終的な答えが出せる。

上の説明は配る視点で書いたが自分の実装ではもらうDPでやっているのでそちら視点でも一応書いておく。たとえば今回のjが3で記号が<であれば、前回のjは0〜3のどれか。よって dp[i][j] += sum(dp[i-1][0〜j]) というような遷移になる。累積和等を使えば区間sumをとる部分がO(1)で処理できるようになるのでこちらも最終的にはO(N2)でできる。

感想

このまとめ方は思いつかなかった 下手に挿入DPを知っていたせいかとにかく値を入れる順番を固定しようとする方向にしか頭が行かず

（追記）コード書いたときはもらうDPで考えてたけど記事書いてたら自然と配る視点になったので配る方の説明も入れた

コード (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 N = readln.chomp.to!int;
    auto S = readln.chomp;

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

    foreach (i; 1..N) {
        if (S[i-1] == '>') {
            long s = dp[i-1][N-i];
            foreach_reverse (j; 0..N-i) {
                (dp[i][j] += s) %= MOD;
                (s += dp[i-1][j]) %= MOD;
            }
        } else {
            long s = dp[i-1][0];
            foreach (j; 0..N-i) {
                (dp[i][j] += s) %= MOD;
                (s += dp[i-1][j+1]) %= MOD;
            }
        }
    }

    long ans = 0;
    foreach (j; 0..N)
        (ans += dp[N-1][j]) %= MOD;
    ans.writeln;
}

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

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 <= 105

解法

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

  1. 出る辺がAで入る辺がA: Aiは最終的なコストに含まれるが、Biは最終的なコストに含まれない。
  2. 出る辺がAで入る辺がB: AiもBiも最終的なコストに含まれる。
  3. 出る辺がBで入る辺がA: AiもBiも最終的なコストに含まれない。
  4. 出る辺が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;
}

Codeforces Hello 2019: D. Makoto and a Blackboard

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

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

問題概要

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

N <= 1015

K <= 104

解法

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

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(S2)かかるが、引数となる文字列列の要素数は必ず半分以下になっていくため、再帰の深さはO(log(|S|))で済む。よって全体でO(S2 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" );
}