Codeforces Round 1024

スポンサーリンク

A. Mex in the Grid

適当に真ん中から渦巻を描けば AC になります.証明はかなり非自明な気がしました.AC と証明の難易度差がすごい.

なんらかの置き方 $X$
渦巻での置き方 $Y$

各 $k$ に対して,$0,\ldots,k-1$ を含む subgrid の個数を比べると,$X$ は $Y$ 以下であることを示せばよいです.$X$ の場合の bounding box の大きさを $(h,w)$ とします.$h<w$ として示せばよいです.

$h+t\leq w-t$ となる最大の $t$ をとって,$(h,w) \to (h+t,w-t)$ という操作を考えると,面積は増えて,最適な場所に置いたときの subgrid の個数も増えます.どちらも総和が一定であるようなものの総積の最大化をする話になって証明できます.

面積は増えているので,$(h+t,w-t)$ の長方形に $0,\ldots,k-1$ をおさめることが可能で,$Y$ における bounding box は $(h+t,w-t)$ の長方形に含まれることが分かります.$Y$ ではその長方形が最適な場所に置かれているので,$X$ のスコア以上であることが分かります.

B. Quartet Swapping

  • 奇数インデックスにあったものは奇数インデックスに行く
  • 偶数インデックスにあったものは偶数インデックスに行く
  • 偶置換

が必要十分です.十分性の証明は,手前 $n-3$ 項を正しく作れることと,そのとき上の条件下で列が一意に定まるからです.

C. 23 Kingdom

使う値(つまり 1 度以上登場する値)は $1,2,\ldots,k$ としてよいです.

beauty については各 $x=1,2,\ldots,k$ に対して

  • 左側として使うインデックスをひとつ選ぶ.そのインデックスを beauty から引く.
  • 右側として使うインデックスをひとつ選ぶ.そのインデックスを beauty に足す.
  • 左側として同じインデックスを 1 度までしか選べない.
  • 右側として同じインデックスを 1 度までしか選べない.

とした問題を解けばよいです.max – min を自由に選んだ項の加算・減算に置き換えてますが問題ないです.また左右インデックスの重複を許しても最適解が増えることはないです.これで,左右独立に解けます.

あとは $k$ をインクリメントしながら,インデックスと $1,2,\ldots,k$ の最大重みマッチングを作るという問題になります.最小費用流の動作を考えると,$k$ を追加したあと何らかのインデックスをひとつ選んで解を延長するという手順でよいです.

結局,完全マッチングが存在するようにインデックスをひとつ追加することになります.完全マッチングの存在条件は Hall の定理で書けて,追加のたびに「$A[i]\geq c$ であるような $i$ を追加する必要がある」という $c$ を計算できます.それを満たす最適な $i$ もセグメント木で取得できます.

D. Mani and Segments

RSK 対応による LIS, LDS の計算を考えると,条件は単調性があって尺取り法が使えることが分かります.あとは https://judge.yosupo.jp/problem/static_range_lis_query を使えばよいです.

LIS, LDS に共通に含まれる要素をとって考えることでもシンプルに解けるようです.

E. Kia Bakes a Cake

まず,path をとる問題ですが,距離が $2$ 倍以上増えていくことから単に walk をとればよいことが分かります.

dp[v][x] := 頂点 $v$ を距離 $x$ 以上で出発するときの最大の移動回数.という dp が考えられます.最大の移動回数は小さいので,

dp[v][k] := 頂点 $v$ を出発して $k$ 回移動するとき,初手の移動距離として可能な最小値は?

という dp の方が良いです.これで $O(N\log N)$ 個の値を計算すればよいという問題になりました.

1/3 重心分解で遷移するのが簡単だと思います.重心分解で登場する subtree ごとに線形時間で遷移できます.$k\to k+1$ の計算に $O(N\log N)$ 時間,全体で $O(N\log^2N)$ 時間で解けます.

F. Shoo Shatters the Sunshine

red の中心を固定して解きます.辺の長さを $2$ 倍にしておいた方が簡単でしょう.

スコアは,(red の最大深さ) + (blue の最大深さ) です.red の最大深さをとるときは,(深さ $0$ お場合を除き)中心から見て $2$ つの異なる subtree 方向からとらなければいけないという縛りになります.

前計算として,各頂点の深さと中心から見た方向を取得しておきます.あとはこの $2$ つの数列を使って答を計算するだけです.

各深さでは,「赤色を最大深さとして選ぶ / 選ばない」「青色を最大深さとして選ぶ / 選ばない」などの遷移を計算して dp していきます.ある深さでは,各方向ごとの個数をもとに,「赤をとった方向の個数」「青をとった方向の個数」(それぞれ 2, 1 以下)としてその深さでの配色の方法を計算します.

としたのですが,たぶんもっと簡単にできて,red の寄与と blud の寄与を独立に計算すればよかったです.各層での塗り方を分類したあとは,全体の dp は要らなかったですね.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました