AGC 055 A - ABC Identity
AGC 055 A - ABC Identity の解説を書いてみます。
考えていたこと
まずは、問題を見てから考えていたことを書いてみます。いらない場合は、下の解説まで飛んでください。
「Sを6個以下に分解」とあるのと、3文字を使うことから、「3!=6 なので、A, B, C の並び替えを利用するのかな」と考え始めました。つまり、
「A, B, C の順になるもの」
「A, C, B の順になるもの」
…
「C, B, A の順になるもの」
などを順番に作っていけないか、と考えました。それぞれ1つずつしか作れないなら、6個でうまくいくので。
が、よく考えると、「ABCABC」を分解するときに、ABC と ABC に分けてしまうと、1つのパターンで2つ作ることになってしまいます。なので、「パターンを好きに選んで、左から貪欲に作っていく」はダメそう、となりました。
とりあえず、1つ目の「良い文字列」を作る場合は、できるだけ長く作った方がいいんじゃないか、と考えました。もし「A, B, C の順になるもの」を作るなら、A を左から順番に採用して、もし n 個採用するなら、その後 B を n個採用、C を n個採用、と。
しかし、A の個数 n を変えると、B の開始場所、C の開始場所が動くので、とても数えにくいです。これを全パターンやるのも大変だし、これをやったあとに、2つ目以降の「良い文字列」を作っていくのは大変そう。
ということで、この方針も違うか、という感じ。
開始場所が動くのが面倒なので、もういっそ選べる場所を限定しまうのはどうだろう、と考えました。
長さが 3N なので、前N個、中N個、後N個に分けます。「A, B, C の順になるもの」を作るなら、前N個の中にあるAをできる限り使うようにします。B, C も同じように数えて、もしどれも x 個以上あるなら、x個ずつとってくればいいじゃないか、という感じ。
これは数えるのは楽そうだけど、実際にこれでうまくいくかはちゃんと考えないといけない。けれど、うまく行きそうな気がする。
解説
長さ $3N$ の文字列 $S$ を、3つのグループ、つまり、前 $N$ 個、中央 $N$ 個、後ろ $N$ 個に分けます。また、それぞれに含まれる A の個数を $a_0$, $a_1$, $a_2$ とし、$b_i$, $c_i$ も同様に決めます。
場所と文字の個数は、次の表のようになっています。
| 前 | 中 | 後 | |
|---|---|---|---|
| A | $a_0$ | $a_1$ | $a_2$ |
| B | $b_0$ | $b_1$ | $b_2$ |
| C | $c_0$ | $c_1$ | $c_2$ |
この状態では、各列、各行の和は $N$ 個です。
ここで、「A, B, C の順の良い文字列」を作ることを考えます。前 $N$ 個から A をとり、中央 $N$ 個から B をとり、後ろ $N$ 個から C をとって作るなら、それぞれ $\min (a_0, b_1, c_2)$ 個ずつ取り出した文字列を作ることができます。
他のパターンについても同じようにして文字列を作ってみます。全部で6パターンできますが、その中で最長のものを1つ選んで、実際にそれを作ることにしましょう。
もし、最長のものが「A, B, C の順の良い文字列」だったとして、さらに、$\min (a_0, b_1, c_2)=a_0$ であったなら、まだ使っていない文字の個数は次のようになります。
| 前 | 中 | 後 | |
|---|---|---|---|
| A | $0$ | $a_1$ | $a_2$ |
| B | $b_0$ | $b_1-a_0$ | $b_2$ |
| C | $c_0$ | $c_1$ | $c_2-a_0$ |
ここでのポイントは、次の3つです。
- どこかのマスが1つ以上 $0$ になる
- どのマスも負になることはない
- 各行の和・各列の和は、それぞれ同じだけ減る
どれも、操作の内容から明らかにわかることです。
さて、この操作、つまり、「各6パターンに対して、3つのグループから文字を取り出して最長のものを作っていく」という操作を、合計で4回やってみます。
このとき、9つのマスのうち、4つは $0$ になっています。そのため、どれかの行には、$0$ が2つ含まれているはずです（鳩ノ巣原理）。ここでは、前・中のA が $0$ になっていた場合を考えてみましょう（対称性から、他のケースも同様に考えられます）。
つまり、4回操作を行った後に、次のようになっていたとします。変化後の個数は、 $x_i'$ というような記号で表すことにします。
| 前 | 中 | 後 | |
|---|---|---|---|
| A | $0$ | $0$ | $a_2'$ |
| B | $b_0'$ | $b_1'$ | $b_2'$ |
| C | $c_0'$ | $c_1'$ | $c_2'$ |
先ほどのポイントでも書いた通り、「各行の和・各列の和は、それぞれ同じ数だけ減る」ので、1行目の和が $a_2'$ なら、3列目の和も $a_2'$ です。また、個数がマイナスにはならないので、 $b_2'=c_2'=0$ だとわかります。
また、$b_0'=x$, $b_1'=y$ とすると、どの列・行も、和は $x+y$ となることから、実は次のような個数になっていることがわかります。
| 前 | 中 | 後 | |
|---|---|---|---|
| A | $0$ | $0$ | $x+y$ |
| B | $x$ | $y$ | $0$ |
| C | $y$ | $x$ | $0$ |
なので、$x$ や $y$ が正なら、「B, C, A をそれぞれ $x$ 個ずつ使う」「C, B, A をそれぞれ $y$ 個ずつ使う」という操作を追加で行えば、ぜんぶの文字を使い切ることができます。
こうして、「各6パターンに対して、3つのグループから文字を取り出して最長のものを作っていく」という操作を行うと、6回以内で、問題文にあるような分解を行うことができることがわかりました。
あとはこれを書くだけです。提出 #26968203