競プロ解説

yukicoder Advent Calendar Contest 2020 の 12/02 出題問題です。
今気付いたんですが、これ yukicoder の記念すべき第 300 回目のコンテストらしいですね。

問題リンク

https://yukicoder.me/problems/no/1305

問題概要

太郎君を呼ぶためにあなたは以下のうちのどちらかの行動をします。

• 噂をする。$1$ 分後に太郎君は $1/p$ の確率で来る。そうでない確率 $(p-1)/p$ のときは再度どちらかの行動をする。
• 電話をして呼び出す。太郎君は $q$ 分後に必ず来る。

太郎君が来るまでの時間の期待値の最小値を求めてください。

制約

$1\le p,\ q\le 10^{9}$
入力は整数

大爆死。反省を込めて解説ブログを書きます。

問題リンク

https://codeforces.com/contest/1455/problem/D

問題概要

非負整数からなる数列 ${a_i}$ および非負整数 $x$ が与えられます。
$a_{i}>x$ である $a_{i},\ x$ を swap することを任意の回数できます。$a$ を広義単調増加にするためには最小で何回の操作を行えばいいでしょうか。

制約

$1\le t\le 500$ (テストケース数)
$1\le n\le 500$
$0\le x,\ a_i\le 500$

これ E よりも簡単じゃないですか？

問題リンク

https://codeforces.com/contest/1454/problem/F

問題概要

$n$ 要素からなる数列 $a$ があります。$a$ を $1$ 以上の要素からなる $3$ つの部分列に分けます。
最初の部分列の最大値、真ん中の部分列の最小値、最後の部分列の最大値が全て等しくなるような分け方は存在しますか。存在するときはその分け方も出力してください。

制約

$1\le t\le 2\times 10^{4}$ (テストケース数)
$3\le n\le 2\times 10^{5}$
$1\le a_{i} \le 10^{9}$
$\sum{n}\le 2\times 10^{5}$

Div. 3 全完しようと思ったらこの問題に阻まれてしまいました。どう考えても不可能だと思ってたけど、よくよく見たらなもりグラフという制約を見逃していました。恥ずかしい。

問題リンク

https://codeforces.com/contest/1454/problem/E

問題概要

自己ループや多重辺のない $n$ 頂点 $n$ 辺の連結グラフ(つまり、なもりグラフ¹)が与えられます。このグラフに含まれる長さが $1$ 以上の単純パスの数を求めてください。ただし、逆順にたどっただけのパスは同じものとみなします。

制約

$1\le t\le 2\times 10^{4}$ (テストケース数)
$3\le n\le 2\times 10^{5}$
$\sum{n}\le 2\times 10^{5}$

ABC184-F Programming Contest を題材に、典型アルゴリズムである半分全列挙について詳しく解説します。実装の細かい部分まで解説します。

また、半分全列挙の高速化 (今回は主に $\log$ を取る部分について) についても掘り下げていきます。

問題リンク

https://atcoder.jp/contests/abc184/tasks/abc184_f

問題概要

$N$ 問の問題があります。$i$ 番目の問題は解くのに $A_i$ 分かかります。

この中からいくつかの問題を選んで解くのにかかる時間の総和のうち、$T$ 分以下での最大値を求めてください。

制約

• $1\le N\le 40$
• $1\le T\le 10^{9}$
• $1\le A_i\le 10^{9}$

この問題だけどうして問題名の最初が英小文字なのか気になってしまい夜も眠れません。

問題リンク

https://atcoder.jp/contests/abc184/tasks/abc184_d

問題概要

袋の中に金貨が $A$ 枚、銀貨が $B$ 枚、銅貨が $C$ 枚入っています。
袋の中から硬貨をランダムに選び、それと同じ種類の硬貨をもう $1$ 枚入れるのをいずれかの種類の硬貨が $100$ 枚になるまで繰り返します。
操作回数の期待値を求めてください。

制約

$0\le A,\ B,\ C\le 99$
$A+B+C\ge 1$

この問題がこのセットで最難……。

問題リンク

https://atcoder.jp/contests/abc184/tasks/abc184_c

問題概要

斜めにどこまででも進め、また マンハッタン距離 が $3$ 以下である場所に進める駒「超竜馬」があります。
$(r_{1},\ c_{1})$ から $(r_{2},\ c_{2})$ へ動くのに必要な最小手数を求めてください。

制約

$1\le r_{1},\ c_{1},\ r_{2},\ c_{2}\le 10^{9}$

数列を当てる系のインタラクティブとても好きだし得意。この前の JOI の数当てもそうだったけど、こういう問題を考えるのがとても楽しいと思えます。

問題リンク

E1 (Easy Version): https://codeforces.com/contest/1451/problem/E1
E2 (Hard Version): https://codeforces.com/contest/1451/problem/E2

問題概要

$n$ 要素からなる数列 $a$ を当てるインタラクティブ問題。解答者はプログラムの中で以下の質問をすることができます。

• AND i j: $a_{i}$ と $a_{j}$ の AND を質問する。
• OR i j: $a_{i}$ と $a_{j}$ の OR を質問する。
• XOR i j: $a_{i}$ と $a_{j}$ の XOR を質問する。

規定の回数以内の質問で元の数列を当ててください。

制約

$4\le n\le 2^{16}$
$n$ は $2$ の冪である
Easy: 質問の回数は $n+2$ 回以内
Hard: 質問の回数は $n+1$ 回以内

同じ日の ARC で -55 もレート溶かしたのに同じ日のこどふぉでレート超盛りました。Codeforces は調子いいのに、AtCoder の下振れが酷いです。助けて。

問題リンク

https://codeforces.com/contest/1451/problem/D

問題概要

$x-y$ 座標上の円 $x^{2}+y^{2}=d^{2}$ があります。この円の中でマスを動かすゲームをします。
マスは最初 $(0,\ 0)$ にあり、ふたりはお互いのターンで $x,\ y$ 座標どちらかの正の向きにちょうど $k$ だけ進めます。円の外に出たら負けです。勝者は先手か後手か求めてください。

制約

$1\le d \le 10^{5}$
$1\le k \le 10^{5}$

yukicoder contest 275 より。
個人差が強い問題。発想出来るかが分かれ目？yukicoder problems では黄 diff とのことですが¹、人によっては黄相応だと思う人も青程度と思う人もいると思います。

問題リンク

https://yukicoder.me/problems/no/1293

問題概要

$N$ 個の都市には $D$ 本の自動車専用道路と $W$ 本の歩行者専用があります。
$0$ 本以上の自動車専用道路を通った後に $0$ 本以上の歩行者専用道路を通ることで移動できる都市のペアの個数(自身どうしのペアを含まない)を求めてください。

制約

$2\le N\le 10^{5}$
$1\le D,\ W\le \min\left(10^{5},\ \frac{N(N-1)}{2}\right)$