AtCoder Beginner Contest 187 - suisen のブログ

f:id:suisen_kyopro:20210102214942p:plain

A - Large Digits

文字列として受け取って和をとったけど, 普通にやった方が良かったかも.

B - Gentle Pairs

浮動小数点数 (double など) を使うと誤差が怖いので, 整数型演算だけで判定したい. 二点 $( x _ i , y _ i )$ , $( x _ j, y _ j )$ を結ぶ直線の傾きは, $\dfrac{y _ j - y _ i}{x _ j - x _ i}$ なので, $-1\leq \dfrac{y _ j - y _ i}{x _ j - x _ i} \leq 1$ かどうかが判定できれば OK. 分母を払えば整数演算のみで判定できるが, 符号に注意する必要がある. 方法としては, 次の二つが考えられる.

$x$ の昇順に点をソートしておくことで, 常に $x _ j - x _ i$ の符号が一定になるようにする
$-|x _ j - x _ i|\leq y _ j - y _ i\leq |x _ j - x _ i|$

C - 1-SAT

HashSet<String> を用意して, $S _ i$ を全て入れておく. その後, 各 $S _ i$ に対して, $S _ i$ の先頭に ! を付加した文字列が Set に入っているかを確認し, 見つかればその $S _ i$ を出力. 最後まで見つからなければ, satisfiable を出力.

D - Choose Me

$d=\mbox{(高橋氏の票数) - (青木氏の票数)}$ を管理する. 初め, $\displaystyle d=-\sum_{i=1}^N A _ i$ である. $d\gt 0$ となるように街で演説をしたい.

高橋氏が街 $i$ で演説したとき, 青木氏の票は $A _ i$ だけ減り, 高橋氏の票は $A _ i + B _ i$ だけ増える. つまり, $d$ の値は $2A _ i + B _ i$ だけ増える.

従って, $2A _ i + B _ i$ の値が大きい順に貪欲に $i$ を選んでいくことを $d\gt 0$ となるまで繰り返し, $d\gt 0$ となった時点でそれまでに演説をした回数を出力すれば良い. $\displaystyle \sum_{i=1}^N A _ i + B _ i\gt 0$ なので, この操作は必ず終了する.

E - Through Path

部分木加算クエリが処理できれば良い. 適当に根を決めて深さ優先探索をする. このとき訪問順に頂点を記録していくと, 部分木は区間に対応する. 従って, この区間を各 $i$ に対して前計算をしておくと, 各クエリは遅延伝播セグメント木を使えば $O(\log N)$ , imos 法を使えば $O(1)$ で処理できる. imos 法を使うことにすると, 全体 $O(N+Q)$ でこの問題を解くことが出来る.

F - Close Group

グラフを複数のクリークに分割する問題. まず, $V=\{1,\dots,N\}$ の各部分集合 $S\subset V$ に対して, 以下のテーブルを埋めておく.

$\mathrm{ok}[S]=\mbox{$S$ から誘導される部分グラフ $G_S$ は完全グラフ $K _ {|S|}$ である}$

このテーブルは愚直に計算して $O(2 ^ N N ^ 2)$ で埋められる.

続いて, 次の DP テーブルを埋める.

$\mathrm{dp}[S]=\mbox{$G_S$ に対して同じ問題を解いたときの答え}$

このテーブルは, 以下のように埋められ, 元の問題の答えは $\mathrm{dp}[\{1,\dots,N\}]$ である.

$\mathrm{dp}[S]=\begin{cases} 1 & \mbox{if $\mathrm{ok}[S]$} \\ \min \{\mathrm{dp}[T]+\mathrm{dp}[S\backslash T]\mid T\subset S,\;T\neq\emptyset,\;T\neq S\} & \mbox{otherwise} \end{cases}$

テーブルの更新では $S$ の部分集合を列挙する必要があるが, これは以下のようにすれば全体 $O(3 ^ N)$ で可能である.

for (int i = 0; i < 1 << n; i++) {
    // j ⊂ i, j != ∅, j != i なる j を無駄打ちなしで列挙する.
    for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
        
    }
}

外側の for 文が全体 $O(3 ^ N)$ で動作することは, 以下より従う.

$\displaystyle \sum_{i=0}^N 2 ^ i \cdot {}_NC_{i}=\sum_{i=0}^N 2 ^ i \cdot 1 ^ {N - i} \cdot {}_NC_{i} = (1+2) ^ N = 3^N$

以上より, 全体 $O(2 ^ N N ^ 2 + 3 ^ N)$ でこの問題を解くことが出来る.