ACPCVC20200203 復習メモ - tinumu's reminder

3日経つと、問題の解法を忘れてしまっています。
AtCoder Virtual Contest

A: Colorful Hats

上限と下限の差が2以上だと矛盾するので、"No"と出力する。
差が0の場合は、全体の色が異なっているのか、少なくとも2匹は同じ色になっているかのどちらか。
そのため、配列 $a$ の値を $A$ とすると $A = N - 1$ または $N \geq 2A$ である必要がある。　おわり
差が1の場合は、小さい値の猫は誰とも色が被ってない必要がある。大きい値の猫はそれらの中で少なくとも2匹は同じ色である必要がある。
小さい値の猫の数を $x$ とすると、大きい値の方で使える色の数は、 $A - x$ となる。
したがって $A - x > 0, N - x \geq 2(A - x)$ を満たしていれば"Yes". おわり

論理が割とわかりやすいので解けました。

B: Connected?

少なくても一つの点が端にない線の場合、他のやつをうまく曲げてあげればよく、解に関係しないことがわかる。
どっちの点も端にある線たちは、交差してる奴はうまく避けられないので、交差を判定->ある:"NO", ない:"YES"である。
交差判定に使える簡単な奴は、stackがある。
長方形を時計回りや半時計回りに走査しながら異なる値ならpush, 同じ値ならpopを繰り返す。走査後、emptyであれば "YES". ほかは "NO"。

交差判定はstackを使えるんだね。　これは、四角形を開けばいいのかな？

C: guruguru

0 indexedにすると解きやすい。
お気に入りボタンを0に固定する。逆に $a$ 自体を動かすことを考える。
0に設定しているので、

$a_i \leq a_{i+1}$ : 広義増加してる->お気に入りボタン押さない
$a_i > a_{i+1}$ : 減少してる->お気に入りボタン押す(はやい)

$a$ に1を足していくと、単調増加列の数だけボタンを押す回数が増える。
その代わり、 $a$ の中の値が $M-1$ -> $0$ になる場所 $k$ に関して、 $a_k-a_{k-1}$ だけ値が減ることが言える。
また、 $k=1$ の時、単調増加列は一つへり、 $k=N$ の時、単調増加列が一つ増える。

これに注意しながら降順ソートした配列を使用しながらシミュレーションを行うと、 $O(N log N)$ でこの問題は解ける。