Codeforces Round #567 (Div. 2)
we did a pretty good job so far^^
nanikore
A. Chunga-Changa
問題：ｘ円とｙ円持っている人がいる。ｚ円のものを2人で協力してできるだけ多く買いたい。最大化したとき、一人がもう一人に譲渡しなければいけないお金を最小化せよ。
考察：
x%=z、y%=zにして、足してz以上なら譲渡します。そうでなければ譲渡はおきないです。
２ペナ出したのアですね…
丁寧に確実な方法を探しましょう
B. Split a Number
問題：l桁のとても大きい数nが与えられる。先頭が０にならないように、文字列とみて2つに分割する。この分けてできた整数2つの和を最小化せよ
考察：
真ん中らへんで分けることが最適なので、その付近で先頭が0にならないindexを上手く見つけます。
pythonなど多倍超整数でない場合は、頑張って筆算して和を求めます
l/2.0未満、超え、等しいの３パターンで求めて比べました。
比べるのも結構めんどくさくてヤバかったです。通らなかったです。
ミス：
if (idx<l/2.0){}
else {}
→else if (idx>l/2.0){}
こうでした。実装重くなるとこういうケアレスミスにどうしても気付きにくくなるので、1回目の実装で丁寧にこなしてくべきですね。
C. Flag
問題：n*mグリッドの全てのマスが0~25の色のいずれかで塗られている。以下の条件を満たす範囲はいくつあるか求めよ
条件：k*l、k*l、k*lの長方形が縦にならんだもの。1番目と2番目。2番目と3番目は色が違くなければならない。
考察：
まず1列のみで考えます。真ん中の色は必ず連続する全てを使わなければならないです。
したがって色xがk個連続しているのを見つけたら、その上に別の色がk個、下に別の色がk個あるかを調べます。
この列で条件を満たす長方形が構築できたとしましょう。
次に3k行を右に見ていきます。全て等しければ範囲を伸ばします。
最後にl列が等しいとわかったとします。そのとき題意を満たす長方形はl*(l+1)/2個です
このままでは計算量が大きそうに見えます。
一度真ん中に選ばれた範囲、列ごとの一番上か一番下になる範囲をチェック済みかboolを持っておきます。
3k*lの長方形を調べ終わったら、k*lが調査済みになります。
以上で最大でも3*n*m程度になり間に合います
ミス：
一番右まで調べたとき、lの更新ができてなかった。
そもそも上下k個調べるところが雑すぎた
全体的に惜しかった
D. Irrigation
問題：m個の都市のうちどれかで毎年大会が開かれる。はじめのｎ年は開催都市が決まっている。n+1年目以降は以下のルールで開催都市を決める。q個のクエリki年目で開催される都市はどこか求めよ
ルール：累計開催回数が最も少ない年の中で、一番indexが小さい都市で開催する
考察：
まず十分に年月が経てば全ての都市で開催回数が同じになります。
そこからは1~mで順番に行うので%mで簡単に求まります。
この「開催回数が同じ都市」を1つの集合として、はじめのn年の開催回数昇順でマージしていきます。
c個がp回開催していて、次に小さい都市がq回だとすると
揃うまでにc
c*(q-p)回かかります
このマージにかかった回数の累計をリストにしておき、クエリkに対して二分探索します。
bcとbc+1の間にkがあるとします。
「開催回数が同じ都市」がc個あり、その中で(k-bc)%c番目にindexが小さい都市が選ばれます。
以上から次の問題が解ければこの問題を解くことができます。
n個の整数列a0,a1...an-1がある。
q個のクエリ：i番目までを昇順に並べてk番目の整数を求めよ
クエリを先読みし、multisetを使えばO(N(logN)^2)で、遅延伝播セグ木を使えばO(NlogN)で解くことができます。
クエリの先読み：
クエリではiとkがあります。iごとに分類しておきましょう。
iを増やすごとに、現れたkだけ求めていきます。
１：multisetを使った解法
既に現れたaiをmultisetに入れておきます。
クエリに存在したkに対して二分探索を行います。
得られたイテレータとbeginを比べることで何番目かがわかりますので、二分探索の二分探索のような形で解くことができます
この問題は5*10^5*19*19くらいでギリギリ間に合いました。
ただ10＾6になってくると間に合わないと思うので、以下の高速な解法があります。
２：遅延伝播セグ木を使った解法
セグ木：ある整数ｘ未満で、既に現れた個数がnode[x]個
このセグ木でnodeがk-1以上になる最小のindexを、nodeを下りながら求めることができます。
遅延伝播セグ木の原理としては、nodeのほかにlazyなど、伝播用の値を持ちます。
あるnodeにアクセスしたときにlazyから子node、lazyに計算を行います。
区間に対して足し算を行いたいときなどで有効です。
ミス：
クエリのkを必ず超えると思ってたｉｎｆｌくんが超えなくてindexoutしてた。
セグ木の中を探索するのはよく使いそうなので慣れておきたいです。でも今日はこりごりだおって感じだからそのうちやります。
感想
1完して、一巻の終わり～ｗｗｗｗｗｗ
まあ考察はだいぶ当たってたし実装もある程度できてたので良しとします。
細部を詰める地力が欲しい。じゃあね
