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 の個数を a0, a1, a2 とし、bi, ci も同様に決めます。

場所と文字の個数は、次の表のようになっています。

A a0 a1 a2
B b0 b1 b2
C c0 c1 c2

この状態では、各列、各行の和は N 個です。

ここで、「A, B, C の順の良い文字列」を作ることを考えます。前 N 個から A をとり、中央 N 個から B をとり、後ろ N 個から C をとって作るなら、それぞれ min(a0,b1,c2) 個ずつ取り出した文字列を作ることができます。

他のパターンについても同じようにして文字列を作ってみます。全部で6パターンできますが、その中で最長のものを1つ選んで、実際にそれを作ることにしましょう。

もし、最長のものが「A, B, C の順の良い文字列」だったとして、さらに、min(a0,b1,c2)=a0 であったなら、まだ使っていない文字の個数は次のようになります。

A 0 a1 a2
B b0 b1a0 b2
C c0 c1 c2a0

ここでのポイントは、次の3つです。

  • どこかのマスが1つ以上 0 になる
  • どのマスも負になることはない
  • 各行の和・各列の和は、それぞれ同じだけ減る

どれも、操作の内容から明らかにわかることです。


さて、この操作、つまり、「各6パターンに対して、3つのグループから文字を取り出して最長のものを作っていく」という操作を、合計で4回やってみます。

このとき、9つのマスのうち、4つは 0 になっています。そのため、どれかの行には、0 が2つ含まれているはずです(鳩ノ巣原理)。ここでは、前・中のA0 になっていた場合を考えてみましょう(対称性から、他のケースも同様に考えられます)。

つまり、4回操作を行った後に、次のようになっていたとします。変化後の個数は、 xi というような記号で表すことにします。

A 0 0 a2
B b0 b1 b2
C c0 c1 c2

先ほどのポイントでも書いた通り、「各行の和・各列の和は、それぞれ同じ数だけ減る」ので、1行目の和が a2 なら、3列目の和も a2 です。また、個数がマイナスにはならないので、 b2=c2=0 だとわかります。

また、b0=x, b1=y とすると、どの列・行も、和は x+y となることから、実は次のような個数になっていることがわかります。

A 0 0 x+y
B x y 0
C y x 0

なので、xy が正なら、「B, C, A をそれぞれ x 個ずつ使う」「C, B, A をそれぞれ y 個ずつ使う」という操作を追加で行えば、ぜんぶの文字を使い切ることができます。

こうして、「各6パターンに対して、3つのグループから文字を取り出して最長のものを作っていく」という操作を行うと、6回以内で、問題文にあるような分解を行うことができることがわかりました。

あとはこれを書くだけです。提出 #26968203