2022-02-23

Codeforces Round #550 (Div. 3)E. Median String

問題概要

二種類の文字列 $s, t$ について, 辞書順でちょうど $s, t$ の真ん中な文字列を求めよ.

問題へのリンク

制約

$1 \le |s| = |t| \le 2\times 10^5$
$s$ と $t$ の間にある文字列は奇数個

解法

文字列を $26$ 進数の数とみれば, $(s+t)/2$ を出力するだけです. ただし, $2\times 10^5$ 桁の数を扱うのは無理があるので, 上手に計算する必要があります.

とはいっても, 普通に筆算のように計算するだけです. $(s+t)$ を表す数列をつくり, 上の桁から $2$ で割っていきます. $1$ 余ったとき, 下の桁に繰り下がるのは $10$ ではなく $26$ のことだけ気を付けましょう.

実装

Submission #146499260 - Codeforces

2022-02-23

Codeforces Round #531 (Div. 3)F. Elongated Matrix

問題概要

$n \times m$ の行列が与えられる. この行列について, 行を自由に入れ替える. この結果できた行列を $A$ としたとき, 数列 $s$ を $s = \{a_{11}, a_{21}, \cdots a_{n1}, a_{12}, \cdots, a_{nm}\}$ として定める.

このとき, ある $k$ に対して, 全ての $1 \le i \le nm-1$ について $|s_i - s_{i+1}| \ge k$ が成り立つとき, $s$ は良い数列であるという.

与えられた行列に対し, 良い数列が存在する最大の $k$ を求めよ.

問題へのリンク

制約

$1 \le n \le 16, 1 \le m \le 10^4, 2 \le nm$
$1 \le a_{ij} \le 10^9$

解法

見るからに二分探索です. 解となる $k$ を決め打ちして, 良い数列が構築できるか判定しましょう.

$i$ 番目の行の次に $j$ 番目の行が来れるかどうかは, $min_{1 \le p \le m}|a_{ip} - a_{jp}| \ge k$ ならば来れると判定できます. これは, 各行を頂点とし, 条件を満たすとき $i \rightarrow j$ の辺を張ることにすれば, 全ての頂点をめぐって最初の頂点に帰ってこれるか？という判定問題に帰着することができます.

そこで, 始点を全探索し, TSP のように bitDP をすれば, あらかじめグラフを構築しておけば $O(n^32^n)$ で良い数列を作れるかどうかを判定できます.

この上で二分探索の分の $\mathrm{log}$ が乗ってくるので計算時間的には怪しいですが, C++ を信じて投げましょう.

実装

Submission #147390915 - Codeforces

2022-02-23

Codeforces Round #529 (Div. 3)F. Make It Connected

問題概要

$n$ 頂点のグラフ $G$ が与えられる. $i$ 番目の頂点には数字 $a_i$ が割り当てられており, 最初は辺が張られていない. このとき, $G$ に対して辺を張ることによって, 全域木を作成したい. このとき, 頂点 $i$ と頂点 $j$ を結ぶのにはコスト $a_i + a_j$ がかかる.

ただし, $m$ 個の辺があたえられ, $i$ 番目の辺は $x_i$ と $y_i$ を指定する. この辺については, $a_i + a_j$ の代わりにコスト $w_i$ で結ぶこともできる( $a_i + a_j$ で結んでもよい).

全域木を作るのに必要な最小コストはいくらか？

問題へのリンク

制約

$1 \le n \le 2\times 10^5, 0 \le m \le 2\times 10^5$
$1 \le a_i \le 10^{12}$
$1 \le x_i, y_i \le n, 1 \le w_i \le 10^{12}$

解法

辺を張れる候補は $n(n-1)/2$ だけあるため, そのまま MST をすると当然 TLE します. どのようにすればよいでしょうか？

よくある発想として, 必要な辺だけ候補に入れることで辺の本数を減らすことを考えます. たとえば, $m = 0$ だとすれば, $a_i$ が最小の頂点を $v$ として, $v$ を中心としたウニグラフを構築するのが明らかに最小になります.

よって, $m$ この辺が追加されたとしても, MST を構築しうる辺は $m$ 個の辺たちと $v$ とつながっている辺のみです(これ以外の辺を用いることによってコストが下がることはありません). よって, これらの辺をまとめてソートしクラスカル法などで MST を構築すればいいです. このとき辺の本数は $O(n+m)$ 程度なので, 問題なく間に合います.

実装

Submission #146588618 - Codeforces

2022-02-23

Codeforces Round #506 (Div. 3)F. Multicolored Markers

問題概要

$1\times 1$ の赤い正方形が $a$ 個, 青い正方形が $b$ 個与えられる. $a+b$ 個の正方形を敷き詰めることにより長方形を作るが, このとき少なくとも赤か青の一方の正方形だけでも長方形が完成されているようにしたい. このような敷き詰め方のうち, 周の長さが最小値はいくらか？

問題へのリンク

制約

$1 \le a, b \le 10^{14}$

解法

まず, $a+b$ 個の正方形を敷き詰めてできる長方形を全探索しましょう. これは $a+b$ の約数を列挙すればよく, これは $O(\sqrt{a+b})$ で行えます.

この上で, 完成される長方形に対して赤もしくは青で内部に長方形を作れるかを判定します. これは $a$ 及び $b$ の約数列挙を行うことにより判定をすることができます.

たとえば, $a = i \times j~(i \lt j)$ のような形で表せるとき, 長方形の短辺, 長辺をそれぞれ $p, q$ とすれば $i \lt p$ かつ $j \lt q$ ならば条件を満たせると判断できます. この判定は実行時間制限に間に合うでしょうか？

じつは, 制約上限のような $10^{14}$ 程度の数に対しては, 約数は最大でもたかだか $2\times 10^4$ 程度しかありません. ですから, 全ての約数に対して条件を満たせるか判定しても $4\times 10^8$ 程度の計算回数で判定することができるので, 間に合わせることができます.

実装

Submission #147242517 - Codeforces

2022-02-22

Codeforces Round #490 (Div. 3)F. Cards and Joy

問題概要

長さ $n\times k$ の数列があり, $i$ 番目の要素は $c_i$ である.

この数字を $n$ 人に $k$ 個ずつ配る. $i$ 番目の人は数字 $f_i$ を好んでおり, 配られた数字の中の $f_i$ の個数が $t$ ならば幸福度 $h_t$ を得る.

自由に数列を配れるとき, 全体の幸福度の最大値はいくらか？

問題へのリンク

制約

$1 \le n \le 500, 1 \le k \le 10$
$1 \le f_i \le 10^5$
$1 \le h_i \le 10^5$

解法

数字 $f$ を好む人に, あるだけ $f$ を配るのが最適なのはすぐわかります. では, 数字 $f$ を好む人が $p$ 人いて, 数字 $f$ が $q$ 個あるとき, 得られる最大値はいくらでしょうか？

一人 $k$ 枚までしか配ることができないので, $p\times k \le q$ のとき明らかに幸福度の最大は $h_k \times p$ です( $p$ 人全員に $f$ を $k$ 個ずつ配ることができます). これを満たさない場合を考えましょう.

$dp[i][j] :=$ ( $i$ 人に $k$ 個の数字を配るときの幸福度の最大値) としましょう. 遷移を考えれば, $i+1$ 人目に数字を $0\sim k$ 個配る場合それぞれについて考えれば良いですから,

$dp[i+1][j] = max_{0 \le p \le k}(dp[i][j-p])$

となります. この dp テーブルは $O(n^2k^2)$ で埋められることがわかります.

これさえできれば, 各数字の個数とそれを欲している人数を std::map などで管理すれば, 答えを求めることができます.

実装

Submission #147254690 - Codeforces

2022-02-22

Codeforces Round #490 (Div. 3)E. Reachability from the Capital

問題概要

頂点数 $n$ の有効グラフが与えられる. 頂点 $s$ からすべての頂点に到達可能にするには最小であと何本有向辺を追加すればよいか？

問題へのリンク

制約

$1 \le n \le 5000, 1 \le m \le 5000$
$1 \le s \le s$

解法

強連結成分分解をしたうえでトポロジカルソートをすれば, どの頂点に優先して辺を張ればいいかがわかります(よりトポロジカルソートしたときに早い頂点に辺を張りたいはずです).

ただし, $s$ から到達さえできればいいので, 次のようにすればいいです.

到達可能かどうかを表す bool 配列 $d[n]$ を用意する. はじめ $false$ で初期化する.
$s$ から到達可能な頂点 $v$ について, bfs などで $d[v] = true$ としておく.
頂点集合をトポロジカルソートし, 頂点番号の早い順にみていく. もし $d[v] = true$ なら辺を張る必要がないのでスルーし, $d[v] = false$ なら辺を張ることにして答えに $1$ を加算し, また $v$ から到達可能な頂点 $e$ をすべて $d[e] = true$ に変更する.
答えを出力する.

このアルゴリズムではたかだか定数回しか各頂点を見ないので, 時間計算量 $O(n+m)$ で答えを得ることができます.

実装

ACL の scc を用いると非常に実装が簡便です.

Submission #147250113 - Codeforces

2022-02-17

Codeforces Round #527 (Div. 3)F. Tree with Maximum Cost

問題概要

$n$ 頂点の木が与えられる. 頂点 $i$ には値 $a_i$ が割り当てられている. 頂点 $v$ に対し関数 $f$ を

$f(v) = \sum_{i=1}^{n}dist(i, v)\times a_i$

と定義する. $v$ を自由に選べるとき, $f(v)$ の最大値はいくらか？

問題へのリンク

制約

$1 \le n \le 2\times 10^5$
$1 \le a_i \le 2\times 10^5$

解法

典型的な全方位木dpの問題です. 全方位木dpがわからない方はまずググってください.

最初に部分木についての問題を解きましょう. これは普通に木dpをすればいいです. $val_v :=$ (頂点 $v$ の部分木についての $f$ の値), $sum_v :=$ (頂点 $v$ の部分木にある頂点についての $a$ の総和) という風に定義すれば, 頂点 $p$ についてその $val_p$ の値は, 全ての $p$ の子頂点 $v$ について $val_v + sum_v$ を足しあげた値になります. これは, 子頂点の $f$ に加え, $p, v$ 間の辺を通ることによって加算される量が $sum_v$ に等しいことを利用しています(実験してみてください).