差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/09] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/10] – [解法] ikatakos | ||
|---|---|---|---|
| 行 38: | 行 38: | ||
| * $185^4 = 1, | * $185^4 = 1, | ||
| * 計算量 | * 計算量 | ||
| - | * ある長方形の複雑さを求めるには、全ての分割を試して最適を求める必要があり、計算量が | + | * ある長方形の複雑さを求めるには、全ての分割を試して最小値を求める必要があり、1つの長方形につき $O(H+W)$、全体で |
| ===解説の方法=== | ===解説の方法=== | ||
| 行 57: | 行 57: | ||
| $(a,b,c)$ によっては複雑度 $k$ では長方形が作れないかも知れないので、その場合はそれと分かる値、たとえば'' | $(a,b,c)$ によっては複雑度 $k$ では長方形が作れないかも知れないので、その場合はそれと分かる値、たとえば'' | ||
| - | DPは2段階で更新する。まず、DP1を使ってDP1を、DP2を使ってDP2を暫定更新する。次に、双方の情報を合わせてDP1、DP2を修正更新する。 | + | まず、$k=0$ の時を埋める。 |
| - | まず第1段階。a,b,cが決められたとき、「縦に分割するとして」複雑さkの長方形を最大限とることを考える。左右とも複雑さ | + | $DP1[0][a][b][a]$ は、$(a,b)$ から数えて $a$ 行で同色が続く右限。これは各 |
| - | | + | $DP1[0][a][b][c]$ は、まず $(a, |
| + | |||
| + | 続いてDPの遷移を考える。2段階で更新する。まず、DP1を使ってDP1を、DP2を使ってDP2を暫定更新する。次に、双方の情報を合わせてDP1、DP2を修正更新する。 | ||
| + | |||
| + | まず第1段階。a, | ||
| + | |||
| + | | ||
| (a, | (a, | ||
| | | | | ||
| 行 75: | 行 81: | ||
| よって、DP1[k-1][a][b][c] でまず左の長方形の右端を求めて（rとする）、次にDP1[k-1][a][r+1][c] で右の長方形の右端を求めると、それがDP1[k][a][b][c]の暫定値となる。 | よって、DP1[k-1][a][b][c] でまず左の長方形の右端を求めて（rとする）、次にDP1[k-1][a][r+1][c] で右の長方形の右端を求めると、それがDP1[k][a][b][c]の暫定値となる。 | ||
| - | DP2も、縦方向に同様にすれば求められる。 | + | DP2も、同様にすれば、横に分割すると決めた場合の暫定値を求められる。 |
| 次に、先ほどの更新は縦に分割するという仮定をおいたが、実際は横に分割した方が複雑さが抑えられ、より右まで複雑度 $k$ のまま範囲を伸ばせるかも知れない。 | 次に、先ほどの更新は縦に分割するという仮定をおいたが、実際は横に分割した方が複雑さが抑えられ、より右まで複雑度 $k$ のまま範囲を伸ばせるかも知れない。 | ||
| - | 横方向の分割での最適な下限はDP2にあるので、それを使ってDP1を更新する。 | + | 横方向の分割での最適な下限は |
| a, | a, | ||
| 行 85: | 行 91: | ||
| | | | | ||
| - | もしある $d=d_2$ の時、DP2によって、複雑度 $k$ の長方形の下限が $c_2$ であるとわかったとする。 | + | もしある $d=d_2$ の時、$DP2$ によって、複雑度 $k$ の長方形の下限が $c_2$ であるとわかったとする。 |
| (a,b) | (a,b) | ||
| 行 92: | 行 98: | ||
| | | ||
| - | $DP1[a～c_2][b][c_2]$ と $d_2$ を各個比較し、もし $d_2$ の方がより右なのであれば、$d_2$ に更新する。 | + | $DP1[k][a][b][a]～DP1[k][a][b][c_2]$ と $d_2$ を各個比較し、もし $d_2$ の方がより右なのであれば、$d_2$ に更新する。 |
| (a,b) | (a,d2) | (a,b) | (a,d2) | ||
| 行 128: | 行 134: | ||
| ===説明のための特殊化=== | ===説明のための特殊化=== | ||
| - | ' | + | ' |
| ===制約=== | ===制約=== | ||
| 行 143: | 行 149: | ||
| <WRAP center round box> | <WRAP center round box> | ||
| ここで、$S$ が全て' | ここで、$S$ が全て' | ||
| - | この場合の数え上げは、フィボナッチ数列のようにしてできる。 | + | この場合の数え上げは、フィボナッチ数列のようにしてできる。直線上で考え、先頭と末尾がともに青にならないように注意する。 |
| + | |||
| + | 長さ | ||
| + | 赤から始まり、末尾が赤 | ||
| + | | ||
| + | 赤から始まり、末尾が青 | ||
| + | ／ | ||
| + | 青から始まり、末尾が赤 | ||
| + | | ||
| + | 青から始まり、末尾が青 | ||
| </ | </ | ||
| 行 149: | 行 164: | ||
| $S$ に' | $S$ に' | ||
| - | （' | ||
| すると、連続する赤の個数にも制約が生じる。結論から言うと、奇数個でなければいけない。 | すると、連続する赤の個数にも制約が生じる。結論から言うと、奇数個でなければいけない。 | ||
| 行 169: | 行 183: | ||
| * 奇数個だった場合、奇数番号の点から出発するケース | * 奇数個だった場合、奇数番号の点から出発するケース | ||
| - | では、移動後に存在できるのが偶数番号の点であり、どうやっても1や3といった赤と青の境界に存在できない。 | + | では、移動後に存在できるのが偶数番号の点となり、どうやっても奇数番号の赤と青の境界に存在できない。 |
| $K$ が奇数個なら左右端で偶奇を選べるので、どの点から出発しても青に移行できる。 | $K$ が奇数個なら左右端で偶奇を選べるので、どの点から出発しても青に移行できる。 | ||
| 行 196: | 行 210: | ||
| ^連続できる赤|1|3|3|5|5|7|7|...|k/ | ^連続できる赤|1|3|3|5|5|7|7|...|k/ | ||
| - | また、2番目の条件「...→青→奇数個の赤→青→...」は、先ほどの偶奇を考えると、赤を端から端まで貫通する必要がある。 | + | また、2番目の条件「...→青→奇数個の赤→青→...」の移動は、先ほどの偶奇を考えると、赤を端から端まで貫通する必要がある。 |
| ' | ' | ||
| 行 204: | 行 218: | ||
| →→, | →→, | ||
| ←←' | ←←' | ||
| - | | + | |
| じゃあ、そういう、赤が長く連続する箇所を避けるように選択して移動できないかというと、無理。 | じゃあ、そういう、赤が長く連続する箇所を避けるように選択して移動できないかというと、無理。 | ||
| - | 実はあんまり移動の自由度がなくて、' | + | 実はあんまり移動の自由度がなくて、' |
| 出発点を決定した時点で、「$i$ 回目の移動後には、この連続する赤/ | 出発点を決定した時点で、「$i$ 回目の移動後には、この連続する赤/ | ||
| 行 221: | 行 235: | ||
| | | ||
| - | 赤が連続する区間は、どこかからの出発点で必ず通られる。 | + | 全ての赤が連続する区間は、どこかからの出発点で必ず通られる。 |
| よって、円周上で赤が連続する箇所は全て、$S$ 上で' | よって、円周上で赤が連続する箇所は全て、$S$ 上で' | ||
| 行 273: | 行 287: | ||
| $dp[N]$ まで埋めたら、回転のバリエーションを考える。本問題では、回転して同じになるものは区別する。 | $dp[N]$ まで埋めたら、回転のバリエーションを考える。本問題では、回転して同じになるものは区別する。 | ||
| - | 単純に直線を円周に当てはめる位置を $N$ 通りずらすので、$dp[N]$ を $N$ 倍すればよい、なんてことにはならず、 | + | 単純に直線を円周に当てはめる位置を $N$ 通りずらすので、$dp[N]$ を $N$ 倍すればよい...なんてことにはならず、 |
| 例えば「赤赤赤青赤赤赤青」などは半回転した結果が全く同じになるので、重複してしまう。 | 例えば「赤赤赤青赤赤赤青」などは半回転した結果が全く同じになるので、重複してしまう。 | ||
