2024-05-29

ARC148 - E ≥ K

ARC148-Eを解いた.

問題

長さ $N$ の数列 $A$ が与えられる.
$A$ の並べ替えであって、全ての隣接和が $K$ 以上であるものを数え上げよ.

解法

全ての $i$ $(1 \leq i \leq N)$ について $A _ i \leftarrow A _ i - \frac{K}{2}$ とすることで $K=0$ の場合に帰着できる.
以下 $K=0$ の場合に帰着して考える.
$|A _ {i}|$ の降順に数列に挿入していくことを考えると、負の要素を追加した場合は挿入可能な位置が一つ減少し、正の要素を追加した場合は挿入可能な位置が一つ増加するため、あとは挿入するごとに挿入可能位置の数をかけていく.
また、 $A$ の要素に重複がある場合は最後にそれぞれの数の個数の階乗で割る必要がある.

感想

降順 / 昇順に挿入の典型.

提出

https://atcoder.jp/contests/arc148/submissions/53994118 簡単のため、 $A$ を倍にしている.

2024-03-24

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

2024-03-17

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

2024-02-22

Codeforces Div1 694-D Strange Housing

cf div1 694-Dを解いた.

問題

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

解法

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

考察

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

提出コード

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

2024-02-22

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

2024-02-07

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

2024-02-02

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)$ で解が求まる。