ARC 136

Sun, Feb 27, 2022

A - A ↔ BB

文字列のうち A or B が連続する区間はいったん全ての A を BB にしてその区間の文字を B のみからなるようにした後に先頭から近い方の BB を A に変換していくのを繰り返すのが最適.

例 CABAC -> CBBBBBC -> CAABC

模範解答を見て知ったが string(n, 'A') とすると A が $n$ 文字の並んだ文字列を生成できるらしい. またどうやら C++ の string で str1 += str2 とするのは str2 の長さ分を加える計算量しか掛からないっぽい. str1 += str2 は str1 に push_back で str2 の要素を1個ずつ入れるのと計算量としては変わらないっぽい.

string string_cancat(int n) {
    string s = "";
    rep(i, n) s += ('a' + (i % 5));
    return s;
}

void test(int n) {
    clock_t t = clock();
    string s = string_cancat(n);
    double time = (double)(clock() - t) / CLOCKS_PER_SEC;
    printf("n = %10d:\ttime = %.9lf sec\n", n, time);
}

void solve() {
    int n = 10;
    while (n < 100000000) {
        test(n);
        n *= 10;
    }
}

n =         10: time = 0.000002000 sec
n =        100: time = 0.000009000 sec
n =       1000: time = 0.000013000 sec
n =      10000: time = 0.000090000 sec
n =     100000: time = 0.000807000 sec
n =    1000000: time = 0.012396000 sec
n =   10000000: time = 0.049614000 sec

提出コード

B - Triple Shift

問題

解説 AC バブルソート風にソートするのは思いついたが, 重複要素があったときに任意の並び順にできることが思いつかなかった.

含まれる数字の分布が一致しなかったら No. これは自明.

以下含まれる数字の分布が同じ場合を考える.

(i) 全要素が違うのとき

$A$, $B$ ともにバブルソートと同じようにして数をなるべく昇順にソートする. (最後の2つの要素だけ大小関係が逆になることがあるので厳密には昇順にできないこともある. ) ソートした数列が一致すれば Yes, 違ったら No を出力.

(ii) 数に重複要素があるとき

このときは2つの数列を必ず一致させることができる.

これを示すために

重複要素は隣り合うように並べることができる
連続する2つの重複要素を X とひとかたまりとみなしたとき, X は任意の場所に移動できる.
x x y z という並びがあったときに x x z y とすることができる

ことを示す.

まずバブルソートと同じ要領で一番小さい値が先頭に来るように操作を繰り返すと確実に重複要素が隣り合うような区間ができる.

x x y のような並びがあったとき操作を繰り返すと y x x という並びにすることができる. x x を一つの要素 X としてみるとこれは X y -> y X という swap 操作ができるということである. よって swap 操作を繰り返すことで X は任意の場所に移動できる.

x x y z という並びがあったとき x x y z -> x z x y -> x x z y より2回の操作で x x の右隣にある2つの要素 swap できる.

以上のことを合わせると重複要素があると任意の2要素を swap できることがわかる. これより, 重複要素がある場合は昇順にソートすることができるので常に数列は一致させることができる.

提出コード

ARC 136

Table of Contents

A - A ↔ BB

B - Triple Shift