Codeforces Round #514 (Div. 2) 参加記録＆解説（A～E）

Dashboard - Codeforces Round #514 (Div. 2) - Codeforces

結果は4完で88位。

f:id:betrue12:20181006175548p:plain

本番後に通したEも含めて5問振り返ります。

A. Cashier

問題概要

$0 \le t \le L$ の区間を考える。この中に、 $n$ 個の「選択不能区間」 $t_{i} \le t \le t_{i} + l_{i}$ が存在する。選択不能区間および他の選択区間と端点以外で重ならないように、 $0 \le t \le L$ の区間の中から長さ $a$ の区間をできるだけ多く選択する時、その個数を求めよ。

制約

$0 \le n \le 10^{5}$
$1 \le L \le 10^{9}$
$1 \le a \le L$
$0 \le t_{i} \le L-1, 1 \le l_{i} \le L, t_{i} + l_{i} \le t_{i+1}, t_{n} + l_{n} \le L$

解法

区間と区間の間から長さ $a$ の区間を取れるだけ取ります。両端を区間の1つとして扱うと実装が楽です。

ACコード

Submission #43832898 - Codeforces

B. Forgery

Problem - B - Codeforces

問題概要

# と . で構成された $n \times m$ のマス目が与えられる。# が黒、. が白を示す。

$n \times m$ の全てのマスが白い状態から、「以下のような中央に穴の空いた形をした $3\times 3$ のハンコを、この向きのままマス目の好きな位置に押す」ことを0回以上繰り返し、与えられたマス目を再現したい。これが可能かどうか判定せよ。

###
#.#
###

ハンコの黒い部分が押されたマスは黒になり、中央の穴に相当するマスは変化しない。マス目からはみ出すようにハンコを押すことはできない。

※問題文がちょっと曖昧なので、問題文に明記されていないことも含めて補足をしています…

制約

$3 \le n, m \le 1000$
与えられるマス目は $n$ 行 $m$ 文字の文字列で、# と . からなる

解法

まず、全部白のマス目を用意します。盤面から切り取れる全ての $3 \times 3$ のマス目について、「与えられたマス目において、その $3 \times 3$ の位置のうちハンコの形状通りの8マスが全て黒であれば、用意したマス目において同位置の8マスを黒く塗る」という操作をします。真ん中の色がどちらか、は気にしません。

これで、ハンコを押して良い位置が全て押されたことになります。この操作によって与えられたマス目を全て再現できている場合答えは YES となり、そうでない場合は NO となります。

盤面から切り取れる $3 \times 3$ のマス目は全部で $(n-2)(m-2)$ 個あり、計算量が $O(nm)$ となりますが、この制約では十分間に合います。

ACコード

Submission #43839595 - Codeforces

C. Sequence Transformation

Problem - C - Codeforces

問題概要

正整数 $n$ が与えられる。「操作」の数列を $1, 2, ..., n$ 、「結果」の数列を空として、以下の操作を $n$ 回繰り返す。

「操作」の数列全ての要素の最大公約数（GCD）を、「結果」の数列の末尾に追加する。
「操作」の数列から、好きな要素を1つ取り除く。

この操作の結果となる「結果」の数列を、辞書順最大にしたい。そのときの「結果」の数列を出力せよ。

制約

$1 \le n \le 10^{6}$

解法

最初の状態では、GCDは1です。辞書順最大を求めたいので、「なるべく早くGCDを1より大きい値にしたい」と考えます。つまり、1以外でなるべく多くの要素のGCDとなっているものを探して、それ以外の要素を取り除きたいです。ただし、要素数が同数の場合は大きいほうのGCDを採用します。

最初の $1, 2, ..., n$ の状態では、ほとんどの場合そのようなGCDは2です。GCDを2にするため、まずは奇数を取り除きます。

奇数を取り除くと、数列は $2, 4, ..., \lfloor\frac{n}{2}\rfloor$ となります。次は何が一番多いでしょうか？　既に最大公約数となっている2を無視すると、この数列はやはり $1, 2, ..., n^{\prime}$ のような形をしています。同じように考えると、やはり一番多いのは2、すなわち元の数列で言う4です。

このように、 $1, 2, ..., n^{\prime}$ の $2^{k}$ 倍の形状をした数列から奇数番目の要素を取り除き、そうするとその結果はやはり $1, 2, ..., n^{\prime\prime}$ の $2^{k+1}$ 倍になっていて…という操作を繰り返すことで、多くの場合解を求めることができます。

ただし問題ページ中のサンプルにもあるように例外があります。それは数列が $1, 2, 3$ であるとき、もしくは操作の途中でその $2^{k}$ 倍になったときです。このとき、2も3も含まれる要素の個数は同じ1個なので、大きい方である3を残さないといけません。

ACコード

Submission #43843969 - Codeforces

D. Nature Reserve

Problem - D - Codeforces

問題概要

$xy$ 平面上に $n$ 個の点 $(x_{i}, y_{i})$ が配置されている。以下のような条件を満たす円が存在する時、その半径の最小値を求めよ。または存在しないことを判定せよ。

その周上または内部に $n$ 個の点を全て含む。
$x$ 軸（直線 $y=0$ ）に1点で接する。

制約

$1 \le n \le 10^{5}$
$-10^{7} \le x_{i}, y_{i} \le 10^{7}$ , $y_{i} \ne 0$

解法

まず条件を満たすためには、 $y_{i}$ が正または負に全て固まっていることが必要です。 $x$ 軸に接する円は、 $y$ が正負どちらか片方の領域にしか存在できないからです。逆に正または負に固まっている場合、半径をものすごく大きくとればいつかは全ての点が収まるので、解は存在します。

以降、 $y$ 座標が全て負の時は反転し、全て正としておきます。

半径を $r$ とします。条件を満たす $r$ の範囲は単調（求めたい最小値を $r_{\min}$ とすると、 $r \ge r_{\min}$ の範囲の $r$ は全て条件を満たす）なので、二分探索をします。つまり半径 $r$ を固定して、条件を満たすかどうかのYes/No問題を解きたいです。

$x$ 軸に接するということは中心の $y$ 座標は $r$ であり、円内部の方程式は中心の $x$ 座標を $a$ として

$(x-a)^{2} + (y-r)^{2} \le r^{2}$

です。与えられた座標点 $(x_{i}, y_{i})$ が円内部に存在する条件は、この座標を代入して $a$ についての方程式を解くと求められます。

$n$ 個の点全てについて $a$ が存在すべき範囲を求めて、それらが共通点を持てば、条件を満たす円が存在するので判定はYesです。このようにYes/No問題を解いて、二分探索をすることができます。

最後に、二分探索の初期範囲を考えます。半径が小さすぎると、 $y$ 座標が大きな点にそもそも届きません。先程の方程式でいうと「実数解が存在しない」ということに相当します。全ての $y_{i}$ に届くよう、下界は $\frac{\max y_{i}}{2}$ とします。

そして上界ですが、これが意外と大きくなります。点群に、 $(-10^{7}, 1)$ と $(10^{7}, 1)$ のように $y$ 座標がとても小さくて $x$ 座標がとても離れた点が存在すると、必要な半径は大きいです。実際に求めてみます。

f:id:betrue12:20181006192949j:plain

このケースにおいて三平方の定理を使うと $r = \frac{10^{14}+1}{2}$ となります。おそらくこれが最大です。大きく取りすぎても反復回数が数回増えるだけなので、どんぶり勘定で大きめに取っておいてもいいとは思います。

計算量は1回のYes/No問題が $O(n)$ 、反復回数は初期範囲と終了範囲の長さの比を取ったものの $\log$ オーダーで、ほとんどの場合100回以内に収まるんじゃないかと思います。（私は100回指定でループしています）

ACコード

Submission #43849835 - Codeforces

E. Split the Tree

Problem - E - Codeforces

問題概要

頂点 $n$ 個の根付き木が与えられ、各頂点には重み $w_{i}$ が設定されている。

これらの頂点を、互いに交わらない、以下の条件を満たす集合に「垂直分割」する。その集合の個数の最小値を求めよ。

集合に含まれる要素は、ある要素から親を辿ったもの、またその親を辿ったもの…というように、縦一列に並んでいる。
集合の要素数は $L$ 以下である。
集合に含まれる要素の重み合計は $S$ 以下である。

制約

$1 \le n \le 10^{5}$
$1 \le L \le 10^{5}$
$1 \le S \le 10^{18}$
与えられる木は頂点1を根とする根付き木である

解法

木DPを考えてみます。子のほうから順に処理をしていって、ある頂点に注目したとき、パスの取り方としてどのようなものがあるでしょうか。

子から伸びてきている「未完成の集合」のうち、高々1つに自分を加える。残りはその時点で完成した集合となる。
その後、自分（または自分を加えた集合）を、「未完成の集合」として親に伸ばす。

ここで難しいのが、「子から伸びてきている集合のうち、どれを採用して上に伸ばすか？」です。将来性があるものを上に伸ばしたいですが、長さと重み合計という2つの条件があるので、短いものがいいのか軽いものがいいのか単純には決められません。

ただこの問題の場合、親を順に辿っていくようにしか要素が追加されないため、将来的に追加されていく要素とその順番は決まっています。そのため「いまこの集合から、あと上にいくつの要素を足せるか？」というものを事前に計算してしまうことができます。これを計算し「上に足せる要素数が最も多いもの」を選べば、当然それが最適になるということです。

ということで、次は「いまこの集合から、あと上にいくつの要素を足せるか？」を効率的に求める方法を考えます。これを毎回1つずつやっていると間に合わないので、ダブリングという方法を使います。これは

ある点から、
- 上に1個足したときの増加重み合計はXXで、1つ上の親は○
- 上に2個足したときの増加重み合計はXXで、2つ上の親は○
- 上に4個足したときの増加重み合計はXXで、4つ上の親は○

というように、2の冪乗ごとに「 $2^{k}$ 進んだときの情報」を事前計算しておく方法です。これを計算しておけば、「いまこの集合から、あと上にいくつの要素を足せるか？」を計算する時は逆順に「8個要素を足せるか？」「4個要素を足せるか？」「2個要素を足せるか？」…　のように考えていくことで、効率的に計算をすることができます。

解法をまとめると、

まず事前計算として、各頂点について「親を $2^{k}$ 個辿ったときの重み合計」と「辿った先の親」を、 $2^{k} \le n$ である $k$ それぞれについて計算する。
葉から木DPをする。を「頂点を含んでいる集合から、上にいくつ要素を足せるか」とする。
1. 子の中で、「上にいくつの要素を足せるか」が正のものが存在する場合、その値が最も大きいものを採用し、その集合に自分を含める。つまり子 $j$ のうち $dp\lbrack j \rbrack \gt 0$ であるものが存在する場合、その中で最大のものを選んで $dp\lbrack i \rbrack = dp\lbrack j \rbrack - 1$ とし、残りの集合は完成させる（答えの個数に加算する）。
2. 1で自分を含めた集合がなかった場合は、自分自身を始点とする新しい集合を作る。このとき「上にいくつの要素を足せるか」を事前計算の結果を使って効率的に計算し、 $dp\lbrack i \rbrack$ とする。
3. 1, 2いずれの場合においても、これ以上上に伸ばせない場合、つまり $dp\lbrack i \rbrack = 0$ であるときは、集合を完成させる。また見ている頂点が根である場合も、もう上はないので集合を完成させる。
完成させた集合の個数が答えである。