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