AGC030-C(Coloring Torus) 解説

問題概要

以下の整数が与えられるので以下の整数を自由に選び、以下の条件を満たす色を使った縦横マスの塗り方を構築せよ。

同じ色のマスを選んだ時、選び方によらず、そのマスそれぞれに隣接するマスの色の種類と回数は等しい(ただし、列目のマスにとって左に隣接するマスは列目のマスとする。他の方向も同様。)

ステップ1 に対応するとは

まず、は以下ですが、の上限はです。つまり、に対して、色での良い塗り方があるのではないでしょうか。がで割り切れない時は切り上げてよいでしょう。制約から察せる気がしますが、これは正解です。

ステップ2 を場合分けしてみる その1:が偶数

がで割り切れる場合を考えてみましょう。ステップ1に従ってとすると、行あたり色があるとよさそうです。つまり、左から奇数列目にはからの数を入れ、偶数列目にはからの数を入れるようにすればよさそうです。

この時、の場合は成り立っているのが分かりますが、の場合は成り立っていません。(列目のはにつ隣接していますが、列目のはに隣接していません。)

同様に考えると、がで割り切れる場合は成り立ちますが、がで割り切れない場合は成り立ちません。

そこで、が奇数の場合、マス目の右に列目をつけても、縦に行余ってしまいます。しかし、とする場合の構築はの場合を真似るならば難しそうです。

なので、が奇数の場合はとする方針がよさそうです。これはの時でも、[n=500]となり、制約的には問題ありません。

ここで、が奇数の場合を考えましょう。色の塗り方を元にする場合、今回の解法では同じ色が複数回登場し、その一部を別の色にするという形なので難しそうです。それに対して、色の塗り方を元にする場合、色をつ選び、その色のマスを全て塗り替えるという手法ができそうです。今回はこちらを採用しましょう。

現状としてはがで割り切れる場合の構築は完了しています。

 

ステップ3 を場合分けしてみる その2:をで割った余りが

がで割り切れる場合の構築を元にして考えたいですが、現状ではどの数字を変えてもうまくいきません。ここで、斜め線を列挙することで列状になるような塗り方を考えてみましょう。

左上から右下への斜め線の色に周期性がある塗り方

どこかで見たことがある感じの模様ですね。この塗り方での色に数字を対応しても成り立つのが分かります。また、それぞれの斜め線を交互に違う色にしても成り立つことが分かります。また、斜め線の色は上図の場合種類で、全ての斜め線を交互に違う色にすると色を使えることができます。これを利用するとがで割り切れるとき、で構築することが可能となります。

では、どのようにこれを作るかというと、対角線に種類の色が現れるように各列をスライドすればよいです。この後、対角線を全て同じ色にすることで、で割って余る場合の構築が可能です。

これはがで割り切れるもしくはで割って余るときには、がどんな数であろうとこの方法を使用できることが分かります。

はがないです。

現状としてはがで割り切れる場合、で割って余る場合の構築は完了しています。

がで割って余る場合も同様に考え、そこからで割って余る場合を作ることができれば解けそうです。

ステップ3 を場合分けしてみる その3:をで割った余りが

まず、がで割って余る場合の構築を考えましょう。の構築で斜め線を利用するものを考えてもうまくいきません。

でのマス目(成り立っていません)

端にあると内側にあるでは隣接しているマスの色が違います。また、違うところを別の色にしてもうまくいきません。(うまくいったとしても、がで割って余る場合しか構築できない)

なので、としましょう。ここでは具体的にとします。の場合のマス目から色減らすことが目標となります。ステップ3での最初の図において、このような事実が分かっています。『また、それぞれの斜め線を交互に違う色にしても成り立つことが分かります。』

これを言い換えると、斜め線に色が含まれている場合、それを全て同じ色にしても成り立ちます。これによって、色の種類を減らすことができます。これを回すればよく、これは十分余裕です。

はがないです。

これによってがで割って余る場合の構築はできました。で割って余る場合の構築はもう回色の斜め線を同じ色にすればよいです。先ほどと同様、をで割った余りがかなら、どんなでもこの手法が使用できることが分かります。

はがないです。

ここまでの議論より、をで割った余りがなんであろうと構築が可能であることが分かり、この問題を解くことができました。

感想

をで割った余りがの場合はすぐわかりましたが、の場合が難しかったです。

数学が好きなのでこういう問題は楽しかったです。