yamake's blog

主に競プロ、たまに自転車

Codeforces Round #494 A ~ Eまで

こどふぉ

Codeforces Round #494 のバチャをしました、Bで50分かかってしまい、4完でした。

翌日にEまで解いたので、自分の方針を説明します。

A. Polycarp's Pockets

一番種類数の多いコインの数だけポケットがあれば必ず重複なしに振り分けられます。

C++のstd::mapを使うと $O(Nlog(N))$ でできます。

std::unordered_mapを使うと $O(N)$ でできます。

B. Binary String Constructing

ここはつまづいたので詳しめにいきます。

問題概要

$a$ 個の0と $b$ 個の1を並べて、 $s[i]!=s[i+1]$ となる $i$ の数が $x$ となる文字列 $s$ を構成しなさい。入力のもとで、答えが必ず存在することは保証される。

解説

$x \equiv \ 0\ (mod\ 2)\ \land \ a\gt b$ のときだけ取り上げます。

1. $"01"$ を $\frac{x}{2}$ こ並べる

2. $1$ を $b-\frac{x}{2}$ 個並べる

3. $0$ を $a-\frac{x}{2}$ 個並べる

証明

1. で並べた文字のうち、最後の一つを除いた $x-1$ 文字は $s[i]!=s[i+1]$ を満たす。

$x \equiv \ 0\ (mod\ 2)\ \land \ a\gt b$ のとき

$a-\frac{x}{2} \gt 0$ が言えるので必ず3. で $0$ を配置でき、

3. で $0$ を並べる前の数列の最後の数字は必ず $1$ であり、

一つ後ろに $0$ が来ることで $s[i]!=s[i+1]$ を満たすようになる。

以上より、 $s[i]!=s[i+1]$ を満たす $i$ の数がx個になる。

$a\leq b$ の時は $1$ と $0$ を入れ替えて同じことをしてください。

$x$ が奇数の時は2. と3. を入れ替えて操作を行ってください。（このとき $\frac{x}{2}$ は切り捨ててください。）

C. Intense Heat

あらかじめ $a[i]$ の累積和を取っておくと、任意の区間での $\Sigma a[i]$ が $O(1)$ で取得できます。

$k \leq x \leq n$ となる長さxの区間それぞれの平均値の最大値を求めれば良いです（読解が一番時間がかかりました）。

D. Coins and Querys

全ての $a[i]$ について、 $log_2(a[i])$ を計算し、その数を配列などに保持します。

与えられる $b[j]$ について、 $b[j]$ にたっているフラグを上から見ていき、取れるコインから取っていきます。

取りきれなかったフラグの分は変数 $rem$ などに入れて管理します。

$j$ が $0$ まで進んだ時に $rem=0$ であれば取ったコインの数を出力し、そうでなければ-1を出力します。

E. Tree Constructing

$n \leq d$ のとき、明らかに構築できません。

また、 $k=1$ のとき、 $n=2 \land d=1$ 以外の場合構築できません。

これら以外の場合について考えます。

f:id:yamakeeee:20200922151514p:plain — n=11の3分木

まず、与えられた頂点数 $n$ でのk分木を考えます。

このときの直径が与えられた条件下で実現できる最小の直径になるので、この木の直径が $d$ より大きかったら答えは"NO"です。

次に、直径となるパス上の頂点に印をつけます。

f:id:yamakeeee:20200922151922p:plain

直径の端点を根とする木を再構築します。

f:id:yamakeeee:20200922152126p:plain

ここまでで"NO"を出力していないのなら、木の直径を増やしていけばいつかは条件を満たします。

この木の直径が $d$ と一致するまで、色の付いていない頂点を色の付いている葉に接続することを繰り返したら終わりです。

editorial解は最初に直径 $d$ 、頂点数 $d+1$ の木を作り、条件を満たしつつ残りの頂点を木に接続していくという方針でした。

たぶんeditorial解の方が実装が楽です。