AtCoder Grand Contest 033 D,E問題メモ

AtCoder Grand Contest 033

• AtCoder Grand Contest 033 解説放送 - YouTube

D - Complexity

• $H \times W$ の長方形
• 上から $i$ 行目、左から $j$ 列目は、色 $A_{ij}$ （白または黒）で塗られている
• 長方形の「複雑さ」を、以下のように定義する
  • 全て白、または全て黒なら、複雑さは 0
  • そうでない場合、縦または横に平行に分割して2つの長方形の複雑さを $c_1,c_2$ とする。分割の方法は複数あり得るが、$m=\max(c_1,c_2)$ が最も小さくなるような辺で分割した時、$m+1$ を元の長方形の複雑さとする
• 与えられた長方形の複雑さを求めよ
• $1 \le H,W \le 185$
• メモリ制限: 512MB（AtCoderでの他の多くの問題は1024MB）
• 実行時間制限: 5s（AtCoderでの他の多くの問題は2s）

制約といい実行時間制限といい、かなりループが深そうな予感。また、メモリ制限という珍しい制約があり、上手くデータ構造を持ちなさいよ、という意図を感じる。

まず思いつく方法として、

$DP[a][b][c][d]=$ 左上を$(a,b)$、右下が$(c,d)$ の長方形の複雑さ

として、小さい方から埋めていくのが考えられる。

ただ、2つの点で問題がある。

• メモリ制限
  • $185^4 = 1,171,350,625$ であり、この時点で整数1個1byteとしても、メモリ制限を超えてしまう
• 計算量
  • ある長方形の複雑さを求めるには、全ての分割を試して最小値を求める必要があり、1つの長方形につき $O(H+W)$、全体で $O(H^2W^2(H+W))$ くらいかかる（もっと効率的な方法があるのかも知れないが）

複雑さは、言い換えると、長方形を紙に見立てて「全ての紙片が単色の長方形になるまで、はさみで一直線に切る必要のある最小回数、ただし切った紙片は何枚でも重ねてOK」みたいな解釈かなと思う。

1×1の長方形の複雑さは0なので、色とか気にせず真ん中で全て1×1になるまで分割しても、$2^8=256$ 以内の長方形なら、縦と横で最大8回、合計16回程度しかかからない。

複雑さの上限が16なので、素直な方法のDPでは、連続するかなりの領域で同じ複雑さが並ぶことが想定される。

ここで、複雑さを逆に添字に組み入れることで、$H,W$の指数を1つ落とせる。

• $DP1[k][a][b][c]=$ 左上を$(a,b)$、左下を$(c,b)$ とした複雑さ $k$ の長方形の内、最も広いものの右限が何列目か
• $DP2[k][a][b][d]=$ 左上を$(a,b)$、右上を$(a,d)$ とした複雑さ $k$ の長方形の内、最も広いものの下限が何行目か

さらに、$DP[k]$ の更新には、$DP[k-1]$ の値があればよく、更新順序を適切にすると上書き更新が可能なので、実装の上では $k$ も無くしてしまえる。ただ、説明の上では残して説明する。

$(a,b,c)$ によっては複雑度 $k$ では長方形が作れないかも知れないので、その場合はそれと分かる値、たとえば-1で埋めておく。

まず、$k=0$ の時を埋める。

$DP1[0][a][b][a]$ は、$(a,b)$ から数えて $a$ 行で同色が続く右限。これは各 $a$ に対して $b$ の大きい方から埋められる。

$DP1[0][a][b][c]$ は、まず $(a,b)～(c,b)$ が全て同色でなければ -1。同色なら $DP1[0][a][b][c]～DP1[0][c][b][c]$ の最小値で、各 $a,b$ に対して $c$ の小さい方から埋められる。

続いてDPの遷移を考える。2段階で更新する。まず、DP1を使ってDP1を、DP2を使ってDP2を暫定更新する。次に、双方の情報を合わせてDP1、DP2を修正更新する。

まず第1段階。a,b,cが決められたとき、「縦に分割すると決めて」複雑さkの長方形を最大限とることを考える。左右とも複雑さ $k-1$ になる出来るだけ広い長方形に分割するのがよい。

  複雑さk-1 r   複雑さk-1
(a,b)------>|(a,r+1)------->|
|           |               |
|           |               |
(c,b)       |               |
         ↓↓↓↓↓
          複雑さk
(a,b)---------------------->|
|                           |
|                           |
(c,b)                       |

よって、DP1[k-1][a][b][c] でまず左の長方形の右端を求めて（rとする）、次にDP1[k-1][a][r+1][c] で右の長方形の右端を求めると、それがDP1[k][a][b][c]の暫定値となる。

DP2も、同様にすれば、横に分割すると決めた場合の暫定値を求められる。

次に、先ほどの更新は縦に分割するという仮定をおいたが、実際は横に分割した方が複雑さが抑えられ、より右まで複雑度 $k$ のまま範囲を伸ばせるかも知れない。 横方向の分割での最適な下限は $DP2[k]$ にあるので、それを使ってDP1を更新する。

a,bを固定して、dを大きい方から見ていく。

(a,b)             <----(a,d)
|

もしある $d=d_2$ の時、$DP2$ によって、複雑度 $k$ の長方形の下限が $c_2$ であるとわかったとする。

(a,b)               (a,d2)
|                         |
|                         |
                   (c2,d2)v

$DP1[k][a][b][a]～DP1[k][a][b][c_2]$ と $d_2$ を各個比較し、もし $d_2$ の方がより右なのであれば、$d_2$ に更新する。

(a,b)            |  (a,d2)
|                |        |
|                |        |
       -->(c2,d1)| (c2,d2)v
 縦分割による右限  横分割による右限
 
 ⇒  DP1[a][b][c2] を d2 に更新

E - Go around a Circle

• $N$ 個の点で等分された円周
• 長さ $M$ の、'R', 'B' のみからなる文字列 $S$ がある
• 隣り合う点と点に挟まれた円弧を「1区間」とし、各区間を赤か青で塗る
• $2^N$ 通りの塗り方の内、以下の条件を満たすものの個数を求めよ
  • 円周上の $N$ 個の点を1つ選び、そこから出発する
  • 円周上で隣り合う点まで移動することを $M$ 回繰り返す。点では方向転換が可能
  • この時、どの点から出発しても、移動方向を上手く選ぶと $i$ 回目の移動で通る区間の色を $S_i$ が 'R' なら赤色、'B' なら青色にできる
• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$

解説を読んでの解答。

丹念な場合分けの考察、累積和を用いたDP更新の高速化、重複しないように回転のバリエーションを数え上げる方法など、 1つ1つは解説を見れば理解できても、コンテスト中に思いついて実装できるかというと、厳しいなあというところ。

'R'と'B'を全て逆転して考えても答えは変わらないので、$S$ が'B'から始まる場合は逆転させて、全て 'R' から始まるとして説明する。

条件を満たすにはどのような制約が必要か、考える。

どの点から出発しても最初に赤を通れる必要があるので、青が連続する箇所があってはいけない。

...赤赤青青赤...
        ↑ここから出発したケースでいきなり詰む

                  長さ   1    2    3    4    5    6
赤から始まり、末尾が赤   1 → 1 → 2 → 3 → 5 → 8
                           ×   ×   ×   ×   ×    ＼
赤から始まり、末尾が青   0    1    1    2    3    5  ー この3つの合計が答え
                                                     ／
青から始まり、末尾が赤   0 → 1 → 1 → 2 → 3 → 5
                           ×   ×   ×   ×   ×  
青から始まり、末尾が青   1    0    1    1    2    3

$S$ に'B'が含まれる場合、'R'から'B'に切り替わるタイミングで、円周上の移動でも赤と青の境界に存在できないといけない。両方が赤の点で'B'への切り替わりを迎えてしまうとアウト。

すると、連続する赤の個数にも制約が生じる。結論から言うと、奇数個でなければいけない。

赤が $K$ 区間連続すると、区間端点は $K+1$ 個ある。番号を付けてみる。

    1    2    3       K   K+1
-青-|-赤-|-赤-|- ... -|-赤-|-青-

$K$ が偶数だった場合、連続する赤の両端が、両方とも奇数番号になる。

    1    2    3
-青-|-赤-|-赤-|-青-

1回移動すると、今いる点の番号の偶奇は必ず変更される。 すると先頭で連続する'R'が

• 偶数個だった場合、偶数番号の点から出発するケース
• 奇数個だった場合、奇数番号の点から出発するケース

では、移動後に存在できるのが偶数番号の点となり、どうやっても奇数番号の赤と青の境界に存在できない。

$K$ が奇数個なら左右端で偶奇を選べるので、どの点から出発しても青に移行できる。

    1    2    3    4
-青-|-赤-|-赤-|-赤-|-青-

よって、連続する赤は、奇数個でないといけない。

偶奇で左右端を選べるとは言っても、あまりに連続する赤が長いと、到達できない。

S = RRB
...青赤赤赤赤赤青...
      ↑ここから出発したら、右端から青に移行することになるが、2回の移動ではたどり着けない

上限を考慮しなければならない条件は2種類あり、

• 先頭に連続する'R'
• 一度'B'を経由してからの「奇数個の」連続する'R'

1番目の条件「先頭に'R'が連続する個数」と「連続できる赤の上限」の関係は以下のようになる。

また、2番目の条件「…→青→奇数個の赤→青→…」の移動は、先ほどの偶奇を考えると、赤を端から端まで貫通する必要がある。

'R'が偶数個なら入った端点と出る端点が同じなので引き返せばいいのだが、奇数個なら入端点と出端点は異なり、貫通が必要になる。

R 偶数個          R 奇数個
青赤赤赤赤赤青    青赤赤赤赤赤青
→→,             →→→→→→→
←←'

じゃあ、そういう、赤が長く連続する箇所を避けるように選択して移動できないかというと、無理。

実はあんまり移動の自由度がなくて、'R','B'が連続する個数の偶奇と入端点によって、出られる端点は一意に決まるので、 出発点を決定した時点で、「$i$ 回目の移動後には、この連続する赤/青の区間のどこかに存在する」というのが決まってしまう。

S = RRRRR BB RRRR BBB RRR
      1    2   3   4   5    同色の連続につけた番号

...青赤赤赤赤赤青赤赤赤青...
        ↑スタート
     ----------             1ではこの上のどこかにいて、右端から出る
               --           2ではこの上のどこかにいて、左端から出る
     ----------             3ではこの上のどこかにいて、右端から出る
               --           4ではこの上のどこかにいて、右端から出る
                 ------     5ではこの上のどこかにいて、右端から出る

全ての赤が連続する区間は、どこかからの出発点で必ず通られる。

よって、円周上で赤が連続する箇所は全て、$S$ 上で'B'に挟まれた最も短い奇数個の'R'の個数を超えてはならない。

• 青は連続しない
• 連続する赤は奇数個で、$S$ の連続する'R'の個数から決まる上限がある

$N$ が奇数の場合、円周を周回する際に偶奇がズレるので、条件を満たす塗り方が出来ない。答えは0である。

以下、$N$ を偶数とする。

「赤赤赤…赤青」という塗り方を1括りにする。赤は奇数個なので、1括りは偶数個である。

円周を割り開いて直線化して、その塗り方を考える。この時、1括りで考えやすいように、左端が赤、右端が青のパターン数のみを考え、回転によるパターンの増加は後で考える。

    青|赤
  赤     赤  →  赤赤赤赤赤青赤青
  青     赤
    赤 赤

以下のパーツを使って、$N$ 区間の塗り方を埋めるパターン数を考える。

赤青
赤赤赤青
赤赤赤赤赤青
...
赤赤赤....赤赤赤赤青  (連続する赤の上限)

$dp[i]=i$ 個目までを塗るパターン数（$i$ 個目は青）

$i$ が奇数の時は0に決まっているので実装の上では半分に圧縮できるが、説明の上ではそのまま進める。

パーツの長さの上限を $L$ とすると、以下のように遷移できる。

dp[0] = 1
dp[i] = dp[i-L] + dp[i-L+2] + ... + dp[i-2]
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        iの前 L個の合計 (ただし添字が負になる場合は0)

連続する区間の和は、累積和が使える。 今回は、DP[i]の値を埋めるのにDP[i-1]までの累積和が必要になるため、DPと累積和を同時に更新しながら尺取のように進めていく。

$dp[N]$ まで埋めたら、回転のバリエーションを考える。本問題では、回転して同じになるものは区別する。

単純に直線を円周に当てはめる位置を $N$ 通りずらすので、$dp[N]$ を $N$ 倍すればよい…なんてことにはならず、 例えば「赤赤赤青赤赤赤青」などは半回転した結果が全く同じになるので、重複してしまう。

ここでは、以下の方法で求めると、重複を除いて計算できる。

• 円周上のある1区間を決め、その1区間を塗ることになるパーツの長さを固定
• 「そのパーツのずらし方」×「残りの部分の塗り方」を合計

例えば以下のような場合を考えると、

N=8
L=6
       0  2  4  6  8
DP[i]  1  1  2  4  7

• ある1区間を長さ2のパーツで塗る → ずらし方＝2、残り6個の塗り方＝DP[6]=4
• ある1区間を長さ4のパーツで塗る → ずらし方＝4、残り4個の塗り方＝DP[4]=2
• ある1区間を長さ6のパーツで塗る → ずらし方＝6、残り2個の塗り方＝DP[2]=1

で、2*4 + 4*2 + 6*1 = 22 が答えとなる。