resulet:ooooo---
perf:2002
■A - On and Off
適当にやる。
1WA(は？)
■B - Takahashi's Secret
面倒なのでdfsをする
■C - Final Day
自分が100点みんな0点
■D - Linear Probing
問題の意味がわからん。
std::setのlower_boundで頑張る
■E - Integer Sequence Fair
m^(k^n)を求めればいい
フェルマーの小定理。
k^n部分をmod p - 1で考える
m = 0(mod p)に注意
■F - Stamp Game
2Dセグ木
昔パクったライブラリを使うも半分落ちる。なんで？
諦めて、他のライブラリをパクると通る
■G - Digits on Grid
同じ状態をどうまとめるか。
作った文字列は同じだが最終位置が違うものをひとまとめにして持つ必要がある
解説ACはしたが、旨く落とし込めてないのでうまく説明はできません。
■H - Histogram
Convex Hull TrickはEDPC-Zで解説ACして依頼始めてみた
CHTに落とすための考察もまあまあ大変な気がする。
まず、Aは昇順に並び替えて良い。
そらに操作後のAの値も昇順になり、操作前のAの値に一致するのが最適なのも明らか
簡単な式変形を行うと
dp[i] = min(-sumc[j]*a[i]+dp[j]) + sumc[i]*a[i] + x;
のような形になるので(0<=j < i)
min(-sumc[j]*a[i]+dp[j])のパートを眺めると
いくつかの一次式、f_i(x)=-sumc[i]x+dp[i]の
min(f_i(a[i]))がわかればいいのでこれはConvex Hull Trickそのもの。
■メモ
Fが通ればperf:2233
