logo - ロゴマーク (Logo) Editorial
by 
maspy
公式解説が見当たらなかったので、書いておきます。
考察は軽く、実装メインな問題だと思います。
とはいえ私には、厳密な計算量解析はできませんでした。 とりあえず AC した方法と、計算量について行った考察を書いておきます。
基本方針として、対称軸のとり方を全探索します。
- 対称軸の選択肢：\(4(H+W-1) \leq 320\) 本以下
- 赤マスの対称軸・青マスの対称軸の選択の組：\(320^2\) 通り以下。
これを全部試すのが基本戦略です。
対称軸を固定したら、次のようにグラフを構築します。
- 赤い対称軸でマッチする \(2\) 点を赤い辺で結びます。
- 青い対称軸でマッチする \(2\) 点を青い辺で結びます。
いくつかの「マッチ」は、自己ループに対応します。適宜、「自己ループを無視したグラフ」「自己ループを含めたグラフ」を適宜使い分けます。
各色だけで見ると、任意の頂点の次数は \(1\) 以下であることに注意します（自己ループは \(1\) 回だけ数えた場合）。
特に、自己ループを無視して赤辺と青辺を合わせると、任意の頂点の次数が \(2\) 以下なので、連結成分はパスまたはサイクルです。色の差異や自己ループも含めて考えると、連結成分は次のような形になります。
- 交互サイクル。赤辺・青辺が交互に並んだ偶数長のサイクル。自己ループはない。
- 自己ループのない交互パス
- 「赤青赤青赤」のように赤が多いもの
- 「青赤青赤青」のように青が多いもの
- 「赤青赤青赤青」のように、同数ずつの赤青辺が使われているもの
- 自己ループのひとつついた交互パス
- 「赤青赤青赤」のように赤が多いパスに、青い自己ループがついている
- 「青赤青赤青」のように青が多いパスに、赤い自己ループがついている
- 「赤青赤青赤青」のように、同数ずつの赤青辺が使われているパスに、赤い自己ループがついている
- 「赤青赤青赤青」のように、同数ずつの赤青辺が使われているパスに、青い自己ループがついている
- 自己ループがふたつついた交互パス
- 「赤青赤青赤」のように赤が多いパスに、青い自己ループが 2 つついている
- 「青赤青赤青」のように青が多いパスに、赤い自己ループが 2 つついている
- 「赤青赤青赤青」のように、同数ずつの赤青辺が使われているパスに、赤・青の自己ループがついている
各頂点がどのタイプの連結成分に属するかは、頂点数、各色の辺と自己ループの個数を数えることで判定できます。例えば、Disjoint set union データ構造を使いながらこれらを計算すればよいです。
これらの連結成分に対して、頂点を赤 or 青に塗り分けて、どの頂点も同色の辺でマッチされているようにすることを考えます。この際、上述の連結成分の分類に対して、以下のような結果が得られます。
- どちらかの色の単色で塗ることになる：[1] [4.1] [4.2] [4.3]
- 赤の単色で塗ることになる：[2.1] [3.1] [3.3]
- 青の単色で塗ることになる：[2.2] [3.2] [3.4]
- 塗り分けることは不可能：[2.3]
塗る色が決まらない成分に対して、部分和問題を dp で解くことによって、赤い頂点数をぴったり \(K\) にできるかを判定できます。
計算量解析について。\(H=W=40\) として雑に上から見積もると、
- 対称軸 \(2\) つの選び方：\(320^2 = 10^5\) 通り程度
- 色が決まらない成分の個数：\(4\) 頂点のサイクルがたくさんできる場合があって、\(400\) 個程度。
- \(400\) 個の整数、\(K=1600\) に対する部分和問題を解く。
ということで、\(10^5\cdot 400\cdot 1600 = 6.4\times 10^{11}\) くらいのループ回数が回れば十分だということは分かります。
このループ回数はふつう TLE する大きさですが、実際にはそのようなワーストケースは作れないということでしょうか。ちゃんとは解析できませんでした。
対称軸の選び方 \(320^2\) 通り（\(10^5\) 程度）程度についてですが、どちらの対称軸についても invalid なセルが存在しない場合に限定すれば、\(10^4\) 通りを超えるケースすら（少なくとも採点データには）存在しないようです。
適切な対称軸の組がたくさんできる場合は、主に \(2\) つの対称軸が平行な場合だと思うのですが、この場合には（長さ \(2\) の交互パスが平行移動に相当するため）部分和問題 dp が必要となる形の連結成分はひとつも出来ません。
posted:
last update: