ABCの勝ちパターンG問題の数え上げを拾う
result:ooooo-o-
rateing:1865->1931
■A - Edge Checker
１ペナ。
a=1とそれ以外で場合分け
■B - Count Distinct Integers
sort(all(a));
a.erase(unique(all(a)), a.end());
cout << a.size() << endl;
■C - Jumping Takahashi
dp[i][j]:=i回の移動後jにいれるならtrue無理ならfalse;
■D - Strange Balls
stackで丁寧に
■E - Ranges on Tree
葉っぱにたいしてdfsで訪れた順番に番号をふる
■F - Sum Sum Max
Cが同じ区間はBは等差数列になる
Aの差分(傾き)がBなので、
Bの符号がプラスからマイナスに変わる瞬間が最大値の候補点。
簡単にするため、各区間の最大値の候補として両端も調べるようにする。
あとはごちゃごちゃするとACできる。
■G - Teleporting Takahashi
２次元なら因数分解して形式的べき級数でできるという記憶があったので(maspyさんのサイトにあるはず)
一つ固定して２次元に落とせば
10^7の二項係数パートでTLEなりMLEしなければ通るでしょという感じ。
■Ex - Sequence of Substrings
考える文字列の長さはsqrt(n)で十分←わかる
全列挙してsortして←まにあわない。
セグ木に乗せればいい←わかる
長さsqrt(n)以下のnsqrt(n)個数程度の文字列をソートしたいという話。
文字列が01なのでtrie木に乗るというのはいいとして
trie木になんどもなんどもinsertするわけにはいかないし
なんどもなんどもidxを取得させるわけにもいかない。
今回の問題で使う文字列は文字列のprefixなのでまとめて上記の処理を行える。
まとめると少しだけ早くなる。
とはいえ2600msかかっているので不満。
追記
1262 msまで縮んだので許容範囲に。
