Codechef - Starters 173
参加してみた。<2700 ratedらしいが、あんまり出てないからratedだった。
簡単枠はともかく、後半の問題はおおむね良質だった。サンプルの説明は不親切がち？
ラスト１分で全完出来た。
大体残り１分とかになると冷静にデバッグできなくて終わりがちなんだけど、レートも何も気にしてなかったからか冷静さを保てた。大事なコンテストでもこうありたいね。
ん？今気づいたけど賞金もらえるっぽい？やったー。
COOLCHECK
面白い。twitterでも好評っぽい。
Aが１種類：簡単
２種類以上
x != y を取ってくると、x,y mod 2～17 はどれかが異なる（LCM>=1e7なため）
18 個以上あれば、x,y以外とxまたはyでどっちかが平均が整数でなくなる
17 個以下なら全探索
（LCMちゃんと見積もらず適当に 16 にして 1 WA、雑見積もりで19にしてさらに雑実装により 1 TLE、え？）
1...x の LCM を最も速く調べる方法募集中
POSTLLM
問題文長い・・・
昇順に連続 M 個だけ考えれば良い
詰めることで期待値を減らせる
同じ値があるときの数え上げがやや面倒（この要素要る？）
期待値の式を整理
$ \sum (d_{i+1}-d_i)*i*(M-i) みたいな式になる（これの２倍かも）
展開すると $ 2(\sum d_i*i) - (M-1)(\sum d_i) みたいになって簡単にスライドできる
上の式のままやってる人twitterで複数観測した。はえー。
たしかに差分列と係数を畳み込めばいいね。そっちの方が手っ取り早いかも？
TERMIN
AC数逆転してた。たしかに最難はこっちだと思う。
累積和にしておくと見通しが良くなる。
頂点に 0,1,2 が書かれた N+1 頂点のグラフで l から r までのパスを作る、みたいに捉える。
辞書順最小化：
$ S_r = 0 なら r に直接飛んで "0" にするのが最小
そうでないなら前から貪欲
（$ S_r と同じ値の頂点に到着したら終わりとして良い）
今の頂点と同じ値が書いてある頂点のうち最も近い頂点に飛ぶ
ないなら、+1 のうち最も近いもの
ないなら、+2 のうち最も近いもの
適当にdpできる。
MNMXPRPAR
B をソートしておく。
S の min と T の max の index を si,ti とする。
数えるべきもの：
$ si \lt tiについての$ B_{si}B_{ti}2^{ti-si-1}
$ si = ti+1についての$ B_{si}B_{ti}
クエリ先読みして座圧しておいて、segtreeに乗せる。
以下、簡単枠
WAPEN
１問目ってこんな簡単なんだ。
COOLSUB
よくわからんギャグ、英文読解コンテスト
MINOVER
貪欲に前から。末尾だけ置き換えるかどうかを両方試した。
INTROVERTS
問題の内容に対して問題文が複雑。最初の人以外はSecondary Goal関係ない。
なんとなく全問題について書いてしまった。まあいいか。