Codeforces Round 253

スポンサーリンク

A. Borya and Hanabi

ヒントとなる色・数の候補 $2^{10}$ 通りを全探索できます.

B. Andrey and Problem

「ソートして大きい方からいくつか」というパターンに限定できます.証明は少し難しかった.

$p_0$ を $0$ 問になる確率,$p_1$ を $1$ 問になる確率として,ここに成功率 $x$ の人をひとり追加することを考えると,$p_1$ は $p_1(1-x)+p_0x=p_1+(p_0-p_1)x$ に変化します.$p_0<p_1$ ならこのような追加はやらない方が得ですし,そうでなければ大きな $x$ を選ぶことが望ましいです.

このことから,大きい方から見て「選ばない・選ぶ」となっている $2$ 人が存在したとき,これらを入れ替えるか後者をキャンセルすることで利益を大きくできます.

C. Artem and Array

最小値から順に(端でなければ)削除していくパターンを計算すればよいです.大きいもの・小さいもの順に削除するパターンに対して,この順を入れ替えることを考えると証明できます.

D. Adam and Tree

根側から貪欲に色を決めていけばよいです.同じ色が $3$ 連続してはダメですが,複数の子に分岐する分には構わないので,根から各点のパスへ独立に貪欲で大丈夫です.

E. Gena and Second Distance

ボロノイ図を作って領域ごとに解くことを考えます.領域ではまず最小距離は確定しています.$2$ 番目の最小距離が誰の担当になるかというのは,点をひとつ削除したときのボロノイ図がどうなるかということです.

答の候補になるのは,そのようなボロノイ図における $3$ 点の外心や,垂直二等分線と長方形境界の交点などに限られて,候補を $O(N)$ 通りにすることができます.候補ごとに $O(N^2)$ 時間かけて解きましたが,ちゃんとやれば $O(N\log N)$ 時間になるはず.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました