AGC に参加して、B 完でした。

## AtCoder Grand Contest 29

問題一覧：

## A - Irreversible operation

問題概要: WとBからなる長さNの文字列がある。 "BW" を "WB" に置換する操作を最大で何回行えるか数えよ。

考察：例えば WBWBW なら

WBWBW
WBWWB
WWBWB
WWWBB

のように3回操作できます。

操作ができなくなるのは "BW" が出現しないときなので、上述のように W..B.. という並びのときです。

これは W→0, B→1 に置き換えればソートとみなせます。だから転倒数を数えればいいです。参考: [転倒数については競プロ参戦記で書きました](https://note.mu/vain0x/n/n0037d6468812)

今回は 0, 1 しか出現しないので、BIT は必要なくて、B=1 の個数を変数で持ってループを回せばOK。

筆者の回答 [AC]

## B - Powers of two

問題概要：正の整数が書かれたボールがN個ある。和が2の冪になるようなボールをペアをいくつ作れるか求めよ。

考察：例えば 1, 3, 3, 13 なら (1 + 3 = 4), (3 + 13 = 16) という2つのペアが作れます。

これは貪欲法で解けます。値が大きいボールから順番にみていって、それとペアにできるボールがあればペアにする、という手順です。実装はやや重め。

正当性について、本番中はなんとなくしか分かりませんでしたが、解説生放送によると「値が最大のボールが作るペアが一意であること」からいえるようです。値が最大のボールを x とし、それとペアになるボールを y とします。 0 < y < x なので x < x + y ≤ 2x となります。 x~2x までの範囲に2の冪 2^t (= x + y) というのは最大で1つなので、y も1つです。

筆者の回答 [AC]

## C - Lexicographic constraints

問題概要：N個の文字列 S(i) からなるリストがある。文字列 S(i) の長さは A(i) である。リストは辞書式順序について真に昇順である。文字の種類の最小数を求めよ。(文字はアルファベットにかぎらず、無限にあるとする。)

考察： **解けませんでした**

例えば A = (2, 2, 2, 2, 2) なら、 S = (aa, ab, ba, bb, ca) というリストが条件を満たすので、文字の種類は3種類 (a, b, c) あればいいことが分かります。一方、文字の種類が2つ (a, b) しかなかったら、長さ2の文字列は4種類しかないので明らかにリストは存在しません。したがって、このケースでの文字の種類の最小数は 3 です。

ここでは文字は a, b, c, .. ではなく 0, 1, 2, .. という数値で区別することにします。S(i) は文字列というより数列とみなします。

ただし各要素の値は 0 から K (文字の種類の個数) 未満、という制限があって、これは K 進数であるともいえます。

まず S(0) = (0, 0, 0, ...) (長さ A(0)) です。ここから次の文字列としてありうる最小の文字列、つまり辞書順で次の文字列を計算していく方針で考えました。

S(i) より S(j) のほうが長いケース (A(i) < A(j)) では、単に文字列の後ろに 0 を足すだけでいいです。

S(i) が S(j) より短いケース (A(i) ≥ A(j)) では、長い部分を切り落として最後の文字を +1 すればいいです。長さが同じケースも同様に、最後の文字を +1 すればいいです。ただし、最後の文字が K-1 だと繰り上がりが発生します。

文字の種類の個数 K を2分探索して、上述の方法でリストを構成してみて、矛盾するか確認すれば解ける。と思って実装したんですが WA がいっぱい出たので諦めました……

筆者の回答 [WA]