ARC119 - E Grid Repainting 3

ARC119-Eを解いた.

問題

H×Wの赤青二色のグリッドが与えられる.
赤マスに対してそのマスを含む行又は列を全て白く塗れる.
白マスの数を最大化する操作を一つ構築せよ.

解法

赤であるマス(i,j)について、頂点i と頂点j+H の間に辺を張った二部グラフを考えると、完全に独立とはいかないが分けて考えられそうだ.
まずは全体が連結な場合を解く.
その連結成分内の行・列すべてを白くするのは明らかに不可能な操作. しかし、その中から一つ行又は列を選んでそれに操作をしないことにすると、それ以外の行・列について操作が行える.
操作しないことにした行・列上にあった赤マスに注目すると(このようなマスは一つ以上存在しないとおかしい)、そのマスの用途は一つに絞られる(選んだ行・列に操作しなくてもよくなったため).
このように考えれば、連鎖的に後ろから操作が決められる.
ここで、全体の白マスの数は操作した行の数をr、操作した列の数をcとすると、rW+cH-rcと表され、どのような(r,c)を選択すればよいか簡単に求まり、各連結成分について行列どちらを選べばいいか定められる.

考察

どんな行・列の集合なら操作可能か考えるとうまくいく.
最初に一つ行・列を操作しないことにするとうまくいくように思えたが、連結成分ごとに考えるのがなかなか見えなかった.

提出コード

https://atcoder.jp/contests/arc119/submissions/51635695

AGC018 - D Tree and Hamilton Path

AGC018-Dを解いた.

問題

N頂点重み付き木が与えられる. 1...Nの順列Pを選び、そのスコアを \sum_{i=1}^{N-1}{dist(P _ i,P _ {i+1})}と定める(dist(i,j):=頂点iと頂点jの距離). スコアの最大値を出力せよ.

解説

まずスコアにdist(P _ N , P _ 1)を加えたものを考える.
主客転倒を考えればこの最大値は各辺について次の値を計算して足し合わせた値である(この値をSとでも置いておく).
- 2*辺の重み*その辺を切った時の小さいほうの連結成分のサイズ
P _ i \rightarrow P _ {i+1}の移動で重心をまたぐようにPを決めていけば達成できる.
このことを踏まえて、P _ 1とP _ Nをそれぞれu,vとして固定したときにスコアの最大値が何になるか考える.
(i) 重心が一つ
重心をcと置くと、スコアはS-dist(c,u)-dist(c,v)となる.
この最大値は簡単に求められる.
(ii) 重心が二つ 重心間の辺の重みをwと置くと、S-wが達成でき、これが最大値である.
(i)とほぼ同じこと.

考察

重心分解初めて使った. 上界達成可能なんじゃね? というのは大事だね.

提出コード

https://atcoder.jp/contests/agc018/submissions/51363220

Codeforces Div1 694-D Strange Housing

cf div1 694-Dを解いた.

問題

N頂点M辺の無向グラフが与えられる.最初、全ての頂点が白で、次の条件を満たすようにいくつかの頂点を黒く塗ることを考える.
1. 両端が黒い辺が存在しない.
2. 全ての頂点の組について、片端が黒い辺のみを通って移動できる.
このような塗り方が存在するか判定し、存在するならば塗り方を構築せよ.

解法

グラフが連結でなければこのような塗り方は存在しない.
頂点1からDFSを行い、その行きがけ順に貪欲に塗っていく.
隣接する頂点に一つでも黒い頂点があれば白、そうでなければ黒で塗れば必ず条件を満たす.

考察

連結なら可能そう
とりあえず全域木を取り、頂点1を根としたときの深さの偶奇をもとに色を塗っていくことを考えると、両端が苦をの辺が存在してしまっても後からどうにでも調節できてしまうことがわかる.

提出コード

https://codeforces.com/contest/1470/submission/247713682

Codeforces Div1 692-B

cf div1 692-B

問題

0,1,?からなる文字列Sが与えられる.S中の?を全て0,1に書き換えて得られる文字列に対して、(連続とは限らない)部分列01が現れたらコストx、10が現れたらコストyがかかる.コストの最小値を求めよ.

解法

x \leq yとして一般性を失わない(そうでない場合、x,yをswap,S中の0,1をそれぞれ1,0に置き換えればよい).
S中の全ての?を書き換えた後の文字列をTとすると、最適なTであって1 \leq i \lt j \leq N,T _ i = 1,T _ j = 0を満たす整数組(i,j)は存在しないようなものが存在する.これはこのような組が存在するとして、T _ iとT _ jをswapしてもコストが増加しないことが容易にわかるため.
この考察で?の置き換え方は高々N通りに絞られたため、差分を管理していけば最小値が求まる.

考察

01と10どっちを減らしたいかわからないので一つにそろえたくなる.
なんとなく1,0の順の置き換え方は良くなさそうとわかる.

提出コード

https://codeforces.com/contest/1464/submission/247589381

ARC105 - E Keep Graph Disconnected

ARC105-Eを解いた,

問題

与えられたN頂点M辺のグラフに対して先手と後手が辺を追加していく.しかし、頂点1と頂点Nを連結にするような辺は追加できない.操作できなくなったら敗北、敗北しなかった方の勝利.
両者が最適に行動したときに勝利するのはどちらか.

解法

グラフの連結成分が二つで、頂点1を含む連結成分とNを含む連結成分がそれぞれ完全グラフである状態で手番が回ってきた人は負ける. また、最終的なグラフが定まっていればその辺数とMが勝敗が容易に判断できる.
ここでNが奇数であれば、最終的に頂点1を含む連結成分のサイズをx(1 \leq x \leq N-1)とすると、x(N-x)辺が最終的に追加されないが、これは常に奇数であることから容易にどちらの勝利か判定できる.
Nが偶数の場合は、最終的なxの偶奇によって勝敗が定まる(片方は最終的にxを偶数にしたい、もう片方はxを奇数にしたいという状況になる). 最初に頂点1と連結である頂点の数をaとして、同様にbを頂点Nについて定める.
c:=(a \, mod \, 2) + (b \, mod \, 2)
と置き、この値によって場合分けする.
1. c=0の場合
最終的にxを偶数にしたい方の勝利(Nが偶数よりサイズが奇数の連結成分の個数は偶数個、よって相手の操作を打ち消すような操作が確実にできる).
2. c=2の場合
最終的にxを奇数にしたい方の勝利(証明は1の場合と同じ).
3. c=1の場合
先手の勝利(Nが偶数よりサイズが奇数の連結成分は奇数個、よって自分の有利な方に動かす方で1,2の場合に帰着できる).

よってUnionFindなどを用いてa,bを求めれば答えが求まる.

考察

最終状態と辺の偶奇に注目できれば自然に.

提出コード

https://atcoder.jp/contests/arc105/submissions/50079539

ABC201 - F Insertion Sort

ABC201-Fを解いた

問題

順列Pに対して、次の操作を繰り返しPを狭義単調増加にする。コストの最小値は?
- 1 \leq i \leq Nを満たすiを選択し、P _ iを好きな位置に移動させる。
- 1 \leq i \leq Nを満たすiを選択し、P _ iを左端に移動させる。
- 1 \leq i \leq Nを満たすiを選択し、P _ iを右端に移動させる。
かかるコストは上から順にA _ i,B _ i,C _ iである。

解法

一番上の操作は下二つの操作の上位互換であるため、B _ iにmin(A _ i,B _ i)を、C _ iにmin(A _ i,C _ i)を代入してよい。
一回も操作をしないindexの集合をSを決めると、そのほかのindexに対する操作が一意に定まる。(具体的には、i \lt min(S)を満たすiについては左端への、min(S) \lt iを満たすiについては右端への、そうでない場合は自由な挿入の操作を選択する)
ここで、
DP _ i = (max(S)=i の時の最小コスト/但し、右端に持っていく分は無視)
を考えると、P _ 1,P _ 2...P _ Nの順に
DP _ i = min( \sum _ {j=1} ^ {i-1} B _ {j} , min(DP _ j + \sum_{k=j+1}^{i-1} A _ {k}))
という遷移ができるが、このままでは間に合わない。これは最初に答えに\sum _ {i=1} ^ {N} A _ iを加算して置き(詳しくは実装を)、その差分を計算することを考え、区間min取得/一点更新ができるSegmentTreeを用いればO(N log N)で解が求まる。

考察

あんまり動かしたくない->動かさないものは単調増加->動かさないのに注目すればよさそう?

提出コード

https://atcoder.jp/contests/abc201/submissions/49860992

AGC037 - E Reversing and Concatenating

AGC037-Eを解いた。

問題

整数N,K、文字列Sが与えられる。
S ← (S + reverse(S))の長さNの連続部分列
という操作をK回行う。操作後のSとして考えられるもののうち、辞書順最小のものは?

解法

m=S 内の最小文字
と置く。前からできるだけmを連続させることを考えると
max(後ろから連続しているmの数 * 2,S中で連続しているmの数の最大値)*2^{K-1}
個だけ連続させることができる。また、これが上界であることもS中で連続しているmの数の最大値が一回の操作で高々二倍にしかならないことを踏まえれば明らか。
これを踏まえれば操作手順の候補が絞れ、全部試せばよい。(Kが十分に大きい場合にはmをN個連続させたものを出力すればよい)

考察

前から小さいのを連続させたいのを踏まえて実験

提出コード

https://atcoder.jp/contests/agc037/submissions/48996634