くで

AtCoder:橙

[くで @kude_coder]

答えは、最終更新のWがs側のWかt側のWかで2通り考慮。丁寧に考えると、前者のものがかなり広い範囲をカバーでき、後者がその範囲をちょっとだけ伸ばす感じになる。
F:全方位木DP

[くで @kude_coder]

Codeforces Round 1130
A:愚直
B:fの個数%2
C:二分探索。何も追加せず塗れるものは無いものとして扱って損しない。1個追加するごとに1 or 2個の条件を満たせる。端から貪欲。
D:各木それぞれで最大独立集合を作る場合が上界で、木が全部頂点数1でなければ上界が達成可能。
E:s[i]='R'であるiについての

[くで @kude_coder]

定数関数と間違えて恒等関数と書いていたけどACだった
ありがとう

[くで @kude_coder]

4年ぶりに入橙した

[くで @kude_coder]

4年ぶりに色変した

[くで @kude_coder]

ルはボトムアップに一意に決まっていく。kのラベルを持つ辺を作るには、最低でも2^k頂点が必要なので、ある程度適当に最大ラベルが小さい順にbit DPでやっても間に合いそうなので書いたら間に合った。

[くで @kude_coder]

ARC233
A:nが偶数かつn/2がAに含まれていなければ、n/2-1個のペア(1,n-1),(2,n-2),...,(n/2-1,n/2+1)のうちどれか1つは共にAに含まれているので答えは2。そうでないとき、まず1,...,n/2-1を聞いていき、ペアを2種類に分ける。次に少ない種類の方のもう片側を聞いていく。同じ結果になれば、答えは2。

[くで @kude_coder]

よく、C[[1],[1]]はStern-Brocot木の頂点そのものなので、[m+n,n][[i],[j]]<=Nなる互いに素な(i,j)の数え上げに落ちる。
C:ある頂点vに注目して、使う辺の順に、deg(v)-1,deg(v)-2,...,0の順にラベルを決める。各辺両端の頂点から与えられたラベルが一致するときに操作可能。木が与えられたときのラベ

[くで @kude_coder]

Σ_{v>=1}[v以上の値がk個以上]と表せる。vごとに答えへの寄与の母関数f_vを考えると、f_v=(x+x)^a_v (1+x)^b_v (1+1)^c_v みたいになる。f_vの変化はO(n)回なので、f_vをまとめることでO(n)個の母関数の和が分かればよい。分割統治。指数は1個ずつ変わっていくのでgcdが同じ部分の計算を遅らせればよい

[くで @kude_coder]

ABC481
A:はい
B:Kの倍数と誤読
C:はい
D:01bfs
E:片方の領域の星の数を管理しながら、直線の傾きを1周分走査。星ごとにそこを直線が跨いだら±1のイベントが発生すると見なす。
F:game-24 Hみたいにスコアを座圧した値も管理しながら、距離ごとに処理
G:下からk番目に積まれるパンケーキのサイズは

[くで @kude_coder]

そうでなければYes。+,-の位置のインデックスの偶奇に注目して判定。

[くで @kude_coder]

Repovive starter round 10
A:はい
B:a[i]>a[i+1]ならばswapするとa[i+1]操作後の時点で+xした回数は減らず、たとえ後で+xできなくなったとしても高々1回分なので損しない→a昇順でよい
C:入室順は(ai,-bi)の辞書順、退室順は(-bi,ai)の辞書順としてよく、退室済みの人数を管理しながらシミュ

[くで @kude_coder]

D:ai=qi*x+riと分解して、qiを分け合うと見なす
E:[ai,bi]が重なっていたら辺を張るととして連結成分を考えたとき、サイズ>=2ならば連結成分内で他人の椅子に座るよう構築可能
F:aのn/2番目の値をcとして、<cか=cか>cかで各要素-,0,+に置き換える。+同士または-同士で操作ができればNoで、

[くで @kude_coder]

beatsの人マジか

[くで @kude_coder]

gp_hash_table<ull, null_type>を使ったら間に合った。
E:先頭からの(の個数を最大化する場合と、それ以外で場合分け。後者はどこまで伸ばせるかを求め、prefix sumのmaxの計算に落としてセグ木で処理。

[くで @kude_coder]

Codeforces Round 1128
A:先手の手札が1枚ならば0, 2枚ならば1, そうでなければ初期スコアを維持できる。
B:「bit k以上は全ての値で一致している」ような最大のkを考えると、bit k以上は変えられず、bit k未満は全部1にできる
C:偶数が存在しないときの負け状態は、DPを考えると0,3のみ。これに偶数を

[くで @kude_coder]

加えたらどうなるかを考えて場合分け。
D:二分探索。新たに追加する区間を(L1,R1),...,(Lc,Rc)とすると、L1<...<Lc<R1<...,Rcとしてよい。現在覆われている区間集合をハッシュで管理し、必要なときに新たに追加する区間を弄ることで衝突回避。unordered_setを使ったらTLEしたので

[くで @kude_coder]

bit DP。
G:(dp, dp+(最大値), dp+(最小値), dp+(最大値)-(最小値))を遅延セグ木に乗せてDP。最大値、最小値更新は、スタックをうまく管理して、区間代入として扱う。

[くで @kude_coder]

ABC480
A,B:はい　いつもより面倒
C:お湯が途切れる時刻を管理しながらA昇順に見ていく
D:[L,R)での総和は、[0,R)での総和-[0,L)での総和に分解。(A1,...,Ai)を1グループと見なし、丸ごと含むグループ数を二分探索。
E:長さlは高々60なのでlは全探索。等差数列をa,a+d,a+2d,...,a+(l-1)dとして、各aに

[くで @kude_coder]

対してdの最大値を二分探索。
F:同じ分割されたケーキを持っている人同士をグルーピングし、最終的にあるグループがc人グループになった場合は、そのグループの総回数はc-1回以上であり、c-1回でも達成可能。グループを1つずつ作っていく。現在のグループサイズ mod S/Mは使用済みの人数から計算可能。