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個ずつとってくればいいじゃないか、という感じ。
これは数えるのは楽そうだけど、実際にこれでうまくいくかはちゃんと考えないといけない。けれど、うまく行きそうな気がする。
解説
長さ A
の個数を
場所と文字の個数は、次の表のようになっています。
前 | 中 | 後 | |
---|---|---|---|
A | |||
B | |||
C |
この状態では、各列、各行の和は
ここで、「A, B, C
の順の良い文字列」を作ることを考えます。前 A
をとり、中央 B
をとり、後ろ C
をとって作るなら、それぞれ
他のパターンについても同じようにして文字列を作ってみます。全部で6パターンできますが、その中で最長のものを1つ選んで、実際にそれを作ることにしましょう。
もし、最長のものが「A, B, C
の順の良い文字列」だったとして、さらに、
前 | 中 | 後 | |
---|---|---|---|
A | |||
B | |||
C |
ここでのポイントは、次の3つです。
- どこかのマスが1つ以上
になる - どのマスも負になることはない
- 各行の和・各列の和は、それぞれ同じだけ減る
どれも、操作の内容から明らかにわかることです。
さて、この操作、つまり、「各6パターンに対して、3つのグループから文字を取り出して最長のものを作っていく」という操作を、合計で4回やってみます。
このとき、9つのマスのうち、4つは A
が
つまり、4回操作を行った後に、次のようになっていたとします。変化後の個数は、
前 | 中 | 後 | |
---|---|---|---|
A | |||
B | |||
C |
先ほどのポイントでも書いた通り、「各行の和・各列の和は、それぞれ同じ数だけ減る」ので、1行目の和が
また、
前 | 中 | 後 | |
---|---|---|---|
A | |||
B | |||
C |
なので、B, C, A
をそれぞれ C, B, A
をそれぞれ
こうして、「各6パターンに対して、3つのグループから文字を取り出して最長のものを作っていく」という操作を行うと、6回以内で、問題文にあるような分解を行うことができることがわかりました。
あとはこれを書くだけです。提出 #26968203