6完。好きな問題が多かった。Bはゴミ。
A - 3.14
コピペできるいい問題。先頭からN+2文字出力する。
B - Roulette
ビットで管理する。popcountも持っておく。指定ビットが立っているものから最小値を求め、もっかいループしてvectorに条件を満たすものを入れていく。
コンテスト中にやる問題ではない。つまらない（ちゃんと考察して楽な方針を見つけるのは楽しいかもしれないがそれをしたら確実に10分以上かかるのでコンテスト中にはできない）。
（追記）pairでC_iも持ってたけどstd::popcountを使えば必要なかった。符号なししか受け付けてくれないので、llではなくullを使う。
C - Rotate Colored Subsequence
高速化で悩むのではなく、「どう実装するんだ？」ってなる。簡単そうなのに手が止まって面白い。空のstringをM個用意してN文字を振り分け実際に色毎の文字列を構成しrotateして書き戻す（どこまでやったか色毎に持っておけばいい）。
D - LOWER
タイプ2か3の操作をすると情報が潰れるので、最後にそういう操作をしたところから愚直にやればいい。と思ったらそれ以前のタイプ1の操作で文字が変わること普通にあるやん（調子は良かったけどなんか頭がゆるかった）。潰れるのは大文字か小文字かの情報だけね。最後のタイプ2,3の場所を求めたら、その前のタイプ1をやって、変換して、残りのタイプ1をやる。
tolowerとかを使いたかったけど軽くググってわからなかったので自分で書いた。
眠くなったのでここでブログ書くのを中断して寝た（Gを解くのにめちゃくちゃ時間使ったせい）。
（追記）islowerとかで判定する必要もなく、tolowerで小文字は小文字のまま、大文字は小文字になってくれる。
E - Roulettes
普通に後ろからやるだけだけど、なんか時間かかった。データの持ち方で迷う。P_iと0の個数と0以外の個数。結局、0でないものだけvectorに入れて、0以外の個数はs[i]のサイズで得ることに。感覚でわからなかったので一次方程式を解く。コストは全体にかかるからC_i*P_iで、それを0以外の個数（これは制約から0でない）で割る。まあs[i].size()/P_iの逆数みたいなイメージか。
「いっせーのー」の指を上げた数を当てるやつを2人でやったときの先手の勝率の計算をやっていたので、こういうのはなじみがある。
F - A Certain Game
これはけっこう難しい。手で例を作って試すと、木構造が見えてくる。UnionFind木か？しかし、マージする前に連結成分内全部に足す操作ができそうにない。普通に木を作ればいいかとも思って実装までしたが、よく考えると完成した木で部分木全体に足したら足しすぎになる。そこで、UnionFindを併用する。もっと簡単な方法がありそうでしばらく留まっていたが、思いつかないので実装を始める。有向辺でつないで根からDFSして累積和が答えという木を構築する。入力のp,qはまずleaderに置き換える。sizeを得てからmerge。計算量は多少悪くなるが実装を楽にするためにmerge後のleaderはpで固定とする。pの部分木にはp側の期待値を足すが、q側にもそれが足されてしまうのでqの部分木に入れる値はそのぶんを引いておく。これでサンプルが合わずにかなりの時間を使った。最終的にサンプル1で木の構築を手で試し、pの値には過去に足されたものも含まれるからq側でそれも引く必要があると気づいた。残り2分を切ってギリギリAC。今回は具体例を試すことで気づいたけど、別の方法で気づくことも多いし、全部やっていたら時間がかかるし、難しい。
G - Amulets
終了後に考えた。いつの間にかタイプの存在を忘れていて、前からセグ木やるだけかと思った。モンスターをi体倒すのに何個のお守りが必要かという問題を解いてそこから答えを求める方針。タイプがあると（ていうかタイプが全員バラバラでないなら）、モンスターをi体倒すのに使ったお守りを、モンスターをi+1体倒すときに使うと決めつけてはいけないことになる。しかし、減らせる攻撃力が大きい順にお守りを使えばいいというのは同じなので、平衡二分探索木のような雰囲気になってきて、ということはトライ木で解けそう。前から見ていって、タイプ毎の攻撃力の和をトライ木に入れる。部分木に含まれる個数は元々わかるが、総和もわかるようにしておく。どれだけ攻撃力を軽減すればいいかの値（総攻撃力が100で体力が10なら91）から、木の右側から見る二分探索をしてO(log(ΣA))で必要なお守りの個数を求める。二分探索を書くのにかなりてこずった。最後に割り算して現在の値を何個使うか求める。子ノードが2個未満のときの処理を忘れていて長時間ハマった。値の更新は、0は入れないので元の和が0のときは削除せず、そうでないときは削除して、そして新しい値を入れる。何個のお守りが必要かという情報からモンスターを何体倒せるかを得るのも地味に難しい。処理自体は1行だけど。
実行時間制限の1/5くらいかかったし、メモリ制限の2/5くらいかかった。そもそもトライ木は重いというところへ今回は50bitを使ううえ総和も持っていた。
