AtCoder Beginner Contest 187参加記（～E問題）

100-200-300-400(2)-0-0で2ペナ4完1000点。茶パフォ。
ちなみに、コンテスト後15分くらいでE問題を通した。コンテスト中に通せよ！！！

A - Large Digits

$A$ も $B$ も $3$ 桁であるので、 $3$ 桁の数としてではなく $3$ つの数字として入力を受け取ると処理が楽に書ける。各桁の数字を足して、大小比較をすればよい。ちゃっかり出力制約に $S(A)=S(B)$ のときは $S(A)$ を出力せよと書かれているが、 $S(A)$ も $S(B)$ も同じ値なので特に注意しなくてもACできる。（解説書いてて今気づいた）

計算量は、 $A, B$ がともに $N$ 桁の整数だったとして、 $O(N)$ 。

とりあえず、 $1\le i\le j\le N$ を満たす整数の組 $(i, j)$ を列挙する。こういう条件が付いてるときの2重for文をスルスル書けるようになると楽。
それぞれの整数の組 $(i, j)$ に対して、「直線の傾き」の値を調べる。直線の傾きは $\dfrac{y_j - y_i}{x_j - x_i}$ で求められるので、この値が $-1$ 以上 $1$ 以下かどうか調べればよい。割り算するときは、

0除算していないか
演算結果は整数で持つのか小数で持つのか

あたりに気を付ければよい。今回は、0除算する可能性があるので、こういう例外は割り算する前に処理しておく。 $x_j - x_i=0$ ならば2点が縦に並んでいるということなので、傾きは無限大となる（条件を満たさない）。また、演算結果は小数で持つべきである。
以上のことに気を付けながら条件を満たす組をカウントする。

計算量は、 $O(N^2)$ 。

C - 1-SAT

不満な文字列 $T$ が存在するとしたら、与えられた $N$ 個の文字列のどれかに一致する。つまり、不満な文字列 $T$ の候補を一つずつ調べていき、実際にその文字列が不満な文字列の条件を満たすか調べればよい。ただし、候補は最大で $2\times 10^5$ 個あるため、判定は効率よく行う必要がある。
不満な文字列の候補 $T'$ に対し、 $T'$ の先頭に!を付けた文字列が、与えられた $N$ 個の文字列の中に含まれていれば、 $T'$ は不満な文字列である。ここで、文字列を辞書順でソートしておくことにより、文字列の集合に対しても二分探索が使えるので、この文字列の検索は一回あたり $O(|S_i|\log N)$ で判定できる。
あとは不満な文字列が見つかるまでループを回せばよい。

計算量は、 $O(|S_i|N\log N)$ 。

D - Choose Me

まず当然の話として、高橋氏が全く演説を行わなかった場合は必ず青木氏に負け、高橋氏がすべての町で演説を行った場合は必ず青木氏に勝つ。さらに、 $P$ 個の町を適切に選んで演説を行ったとき青木氏に勝てるなら、 $P+1$ 個の町で演説を行っても青木氏に勝てる。このことより、解の二分探索で解けそうだと目星を付ける。
問題は $P$ 個の町をどのように選ぶかであるが、これは「演説を行ったときの効率が良い」町から順に貪欲に選んでいけばよい。この、「効率の良さ」をどのように算出するかが重要である。
仮に町 $i$ で演説を行ったとすると、青木氏の得票数は $-A_i$ され、高橋氏の得票数は $+A_i+B_i$ されるので、両者の得票数の差は $2A_i+B_i$ 開くことになる。よって、各町を $2A_i+B_i$ で降順ソートして、先頭から順に演説すれば最善である。
$P$ 個の町で演説したときの実際の得票数を計算するのに、「 $1$ 番目から $P$ 番目までの青木派・高橋派のそれぞれの有権者数」を使うが、これは累積和を使うことで高速に求められる。よって一回の判定は $O(1)$ でできる。

計算量について、ソートに $O(N\log N)$ 、累積和を求めるための前計算に $O(N)$ 、解の二分探索に $O(\log N)$ かかる。よって、全体では $O(N\log N)$ の計算量となる。

ソートするための基準を適当に決めて2WA。罠にまんまと引っかかった。

E - Through Path

初めに少しだけ愚痴。問題文に書かれているクエリの説明が簡素すぎだと思う。せめて $e_i$ が辺番号を示しているということは明記してほしかった。
愚直に毎クエリごとに木を走査して頂点を更新していくと間に合わないので、最後に木の根から走査して動的計画法で更新することを考える。
クエリを読み解くと、スタート地点となる頂点と通ってはいけない頂点は必ず1本の辺で繋がっていることがわかる。よって、木の根を適当に決めたとき、スタート地点から到達できる部分木に根が含まれているパターンと含まれていないパターンの2つに分類できる。
木の根が部分木に含まれるとき、木の根に $+x_i$ する。ただし、走査しているときに辺 $i$ を通過したら $-x_i$ して打ち消す。
木の根が部分木に含まれないとき、はじめは木の根に何も足さない。操作しているときに辺 $i$ を通過したら、そこからスタート地点となる頂点を含む部分木なので、 $+x_i$ する。
こうすることで、1回の走査だけですべての頂点の値を更新することができる。