Codeforces Round #576 (Div. 2)
寝坊した。。。まぢムリ…
バチャしたから書くお
A - City Day
問題：N日の降水量が与えられる。そんなに雨が降ってない日かつ最も早い日を求めよ。そんなに雨が降ってない日：d-x<=j<d,d<j<=d+yを満たすjについてad<ajを満たすd
感想、考察：
数式で条件を与えてくれたのでわかりやすいですね。
ただ、d-xが0以下になったり、index outのときどうするのかがわかりづらかったです
と思ったらサンプルの下に書いてあったので楽でした
解法としては、全てのdでindex outをしないように-x~+yまで(dと一致しないところ)を、全探索すればよいです。
B - Water Lily
問題：Lilyの花が水面高さHに浮いている。中心からLだけ動かしたら丁度水面に接した。茎の長さを一定としたとき、生えている深さ求めよ。
Lilyって何だろうと思ったけどユリらしいです。百合ですね。Lily Whiteですね。
感想、考察：
図が書いてあるのでかなりわかりやすかったです。
なんだか中学校あたりでよく見たような図が
茎の長さをr、深さをxとします。
・H+x=r
・L^2+x^2=r^2（三平方の定理)
この連立方程式を解くとうまい具合に一次になります
L^2 = H^2 + 2Hx
これを解いて出力すればよいです
C -MP3
問題：N個の非負整数Aiが与えられる。K種類としたとき、使用するメモリは、(log2(K)の切り上げ)*N bitsである。ある整数l、r(l<=r)を決めて、全てのAiを、ｌ未満ならｌに、ｒより大きければｒにする操作が行える。使用メモリ量をＩbytes以下にせよ
ただし1bytes＝8bitsである。
考察：
要するにｌ未満、ｒより大きい範囲の整数を消して、全体の種類数（最小1種類以上）を減らすという問題です。
ここで、ｌ、ｒの指定は1回で十分です。2回目で範囲を狭くするなら元から狭くしておけば良いし、広くしても対象の整数はありません。
次にＩの制約を考えましょう。
log2(K)の切り上げを取っているので、2^(x-1)+1~2^xは同じ値になります。
したがってK＝2^xとして
nx<=８Ｉを満たすｘを考えればよいです。単位変換してます。
これは当然ｘ=８Ｉ//ｎです。
あとはl、rに対する種類数を求められれば良いです
単純に考えるとai<=10^9よりその二乗の時間がかかってしまいそうです
あらかじめ整数を種類ごとに数えて昇順にしておきましょう。(mapなどを使います)
こうすることで高々N種類になりました。
そしてK種類取れればよいのでK種類ずつスライドして見ていけばよいです。尺取り法などを使いO(N)で解くことができます
D -Welfare State
問題：N人の市民の資産aiが与えられる。Q個のクエリが与えられる
クエリ１：ｐさんの資産をｘとする
クエリ２：資産がｘ未満の人全員を、ｘにする
全てのクエリを終えたときの全員の資産を求めよ
考察：
まずクエリ１がｘ以下のときは変化しないとか、ｘ減らすとかじゃないことに感謝します。
クエリ１があったとき、その前のクエリに全く関係なくｐさんの資産をｘにすることが可能です。
つまりクエリ１だけ考えれば、各人の最後のクエリ1だけ見ればよいです。
次にあるｉさんは、最後のクエリ1のあとどのように資産を変化させるでしょうか。
これは最後のクエリ１以降のクエリ２の最大値、または最後のクエリ１の値になります。
これは簡単に示すことができて、まず最後のクエリ１の値をx0、それ以降のクエリ2の値をx1、x2…xkとします
x1～xkで資産が減ることはないので大きいときだけ更新されます。
はいセグ木ペタンコー＾＾
区間の最大値を取得は雑にセグ木でいいと思います。
クエリ２の値だけ格納していきます。
それとは別に各人をクエリ1の値で更新し、最後の更新のindexを持っておきます
O((N+Q)logQ)です
別解？：
実装してないので不確かです。
セグ木を使わなくても、クエリを読み終わった後、後ろからクエリを読めばO(N+Q)解ける気がしました。
後ろから見て
クエリ2：いま保証されているxmを更新
クエリ1：pさんの値をそのクエリのxiとxmのmaxで確定。もしその前に確定していれば処理しない。
最後に初期値をクエリ1としてN人分見て出力すれば良さそう
たぶんこっちが想定解ですね。早いし。
E -Matching vs Independent Set
問題：頂点3N個、辺M個の単純グラフが与えられる。
１：端点を共有しないN個の辺
２：どの2点も連結でないN個の頂点
このどちらかは存在するか。存在すれば求めよ
クエリ問題でありT個のグラフが与えられる
考察：
１だけだったら二部マッチング問題にできそう
ただ計算量的にキツイ
２はよくわからん。グラフの色塗りっぽくするのか。
答え見て勉強しよう。
解説ACしたので以下追記
E -Matching vs Independent Set
直感的に1が2N個の頂点、2がN個の頂点を必要とするとわかります
解説によると、順序関係なく貪欲に追加していけばよいそうです
端点が未使用なら枝を追加。最後に枝がN本以上あるなら枝を出力。ないなら未使用の頂点をN個出力でOKです
高速化：
上の貪欲ではTLで弾かれてしまいました。
調べたところcin高速化というテクニックがあるそうです
そもそも標準入出力に時間がかかっているということで
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
これを書いておくとcinが早くなるらしいです
また、endlの代わりに'\n'を使っても早くなるそうです。
両方使用で296ms、cinだけで623msでした。結構変わりますね。
インタラクティブ問題ではまた注意する必要があるそうです。あんまり使わないほうが良いかも
printf、scanfについて。こっちのほうが速いらしいですけど、vscode上では動かない？コンパイラの関係？かなんかで怪しいのでしばらくは使わないと思います
F - Rectangle Painting 1
問題：白黒の正方形グリッドが与えられる。あるh*wの任意の範囲を白に塗るコストはmax(h,w)である。すべて白にする最小コストを求めよ
考察：
再帰DPっぽい。Nが小さいし。
正方形で塗るのが最適だから正方形分割かと思ったけど無理そう
解説：
DP[x1][x2][y1][y2]：長方形(x1,x2](y1,y2]の区間を塗るための最小コスト
これを再帰DPで調べる
解説と区間の取り方がちょっと違います。なんか適当に二次元累積和書いてたらそうなっちゃったからで、特に理由はないです
まず、考える範囲に黒のマスがない場合、コストは0です。
これは二次元累積和をあらかじめ計算しておくことで、O(1)でわかります
次に再帰を考えます。ここで苦労しました
誤答：縦横、x3、y3で分割する
正答：縦x3で分割。横y3で分割。
一見同じようなことをしてるように見えますが（僕には見えます）、上ではO(N^2)、下ではO(N)です
上の分割は、下の分割を2回繰り返したものと同じになります。
あまり直感的でなく腹落ちしていないんですけど、できるだけシンプルな分割、遷移を考えるという感じでしょうか。
DPは苦手なので、二次元区間DPの1つとして頭に入れておこうと思います。
