NJPC2017: G - 交換法則

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