Kyoto University Programming Contest 2019

オンラインでの参加でした　ABC3完
レポート終わってからやり始めたら開始時点で終了まで1時間前切ってました
atcoder.jp

A - November Festival

atcoder.jp
「可能性がある」ことが判定できればいいので「残り $X$ 票が全部 $i$ 番目に突っ込まれたら？」を考えるといいです
よって $a_i+X\ge \max\{a_i\}$ となるような $i$ の個数を出力すれば計算量 $O(N)$ でAC

拙解 (C++14): Submission #7960118 - Kyoto University Programming Contest 2019

B - ナップサック問題

atcoder.jp
$a_j$ と $b_j$ を必ず一緒に入れないといけないということは $a_j$ と $b_j$ はつながった一つの荷物とみなせます
UnionFind貼るなりなんなりして連結成分を求めたらそれらの $w$ と $v$ をそれぞれ足して一つの荷物にすれば普通のナップサック問題に帰着できます
この記事を参考にするなどして $O(nW)$ のDPで解けます

拙解 (C++14): Submission #7960391 - Kyoto University Programming Contest 2019

C - てんびんばかり

atcoder.jp
問題文の式を変形すると、右の皿に $x$ g乗せるのは左の皿に $-x$ g乗せるのと変わりません
また、 $1, 2, \cdots, N$ gすべて乗せなければいけないので $1$ g刻みの調節をするのにまず $1$ gの分銅が必要になります
そこから網羅する範囲を広げるためには $2K+1$ gの分銅があればもっとも広い範囲をカバーできます
そこから帰納的に考えれば
$\displaystyle M \le K\sum_{i=1}^{N}(2K+1)^i = \frac{1}{2} \left( (2K+1)^N - 1 \right)$
を満たす最小の $N$ が答えになることが分かります
計算量は $\Theta((2M+1)^\frac{1}{2K+1})$ となって $M=10^9, K=1$ でも十分間に合います

D - Maximin Game

atcoder.jp
二人の手札のうち、小さい方から大きい方へと有向辺を伸ばすと
f:id:aprilganmo:20191013223302p:plain
このようになります
ここから、どこからもアークが刺さっていないノードから順に $1, 2, \cdots$ と整数を入れていくことで手札が構築できます
つまりこのグラフをトポロジカルソートする方法は何通りあるか？がこの問題の答えです
Sの0→1または1→0で切り替わっている部分はΠorЦの字型のパスがあるのでその順番にしか入れられません
Sの0か1が連続している部分では複数の方法がありそうなので、上下に分割してみます
f:id:aprilganmo:20191013224311p:plain
これを下の部分の個数が上の部分より大きくならないように左側から消していく方法が何通りあるか、を考えます
「下の部分を1つ消す」を「格子上を下に1つ進む」
「上の部分を1つ消す」を「格子上を右に1つ進む」
にそれぞれ言い換えると、
f:id:aprilganmo:20191013224833p:plain
対角線を跨がずに格子点上を通って移動する経路の数え上げに帰着できました！
これはカタラン数を使って解ける典型問題なので、ランレングス圧縮してそれぞれのランの長さに対応するカタラン数を掛けていけば $O(|S|)$ で解けます。