ECR001~020の紫・橙をほとんど埋めたので、簡単な解説・感想を書きます。
ECR001-C Nearest Vectors
偏角ソートやるだけ、long double使ったら落ちなかったけど有理数のもの使った方が安全なのかな？
ECR001-E Chocolate Bar
制約がかなり小さいのでそこに着目。切った後も長方形になるので、
dp[h][w][k] = 縦h, 横wからkつくるための最小手数
というdpをたててメモ化再帰で更新する
ECR002-D Area of Two Circles' Intersection
幾何とみせかけて、公式当てはめるだけ...なんだけど誤差にめちゃめちゃ厳しい
嫌すぎてACするの諦めた
ECR002-E Lomsat gelral
部分木の情報がほしいので、mapに持たせてマージテクを使う
マージテク使ったのはじめてかも
ECR003-D Gadgets for dollars and pounds
k日以内で買えるなら、k+1日以内で買えるので二分探索が使える
日数を決め打ったら、貪欲に安いときに買うのが最適
ECR003-E Minumum spanning tree for each edge
普通に最小全域木をとって、それに使われているものは自明
そうでないときは、a-bの辺を使いたいなら、最小全域木におけるa-bのパス中で最もコストの大きい辺を消せばよい
「パス中の辺の最大コスト」はLCAのようにダブリングを使うと、O(logN)で求められるのでOK
ECR004-E Square Root of Permutation
構築パズル。与えられる順列から必要なサイクルをつくってうまいこと構築する(説明するの難しい)
サイクルの長さが奇数・偶数でつくり方が変わるので注意
ECR005-E Sum of Remainders
√Nで分類するいつもの。mが大きくなるとn mod mがパターン化してくるのでそこをまとめて計算する
ECR006-D Professor GukiZ and Two Arrays
N≦2000でswap回数が2回までなので、swap箇所を決め打ちしてしまってよい
そのときの最善がどうなるか丁寧に場合わけする、めんどくさいよね
ECR006-E New Year Tree
部分木クエリなので、Euler Tour + セグ木が効果的
ci≦60なので、各クエリで60種類全部あるかないか見ても余裕はある
メモリが謎に厳しいので、bitで管理しないと詰む(やめて)
ECR007-D Optimal Number of Permutation
わけわからないものの最小化なので、これが0か1のものが常に構築できたらいいなという気持ちになる。実際に0になるものが常に構築できる
うまく対称的に配置するとできるので、パズルを頑張る
ECR007-E Ants in Leaves
言われてみればそうなんだけど難しかった
部分木でかかる時間を計算して、木DPをする
DPの更新をするときに、子の時間でソートする
ECR008-D Magic Numbers
すごく大きい数字が与えられて、a以上b以下で条件を満たすものを求める
どうみても桁DPなので頑張る
i桁目までみた、mで割ったあまりがj, 奇数桁かどうか(k), 桁dpのいつもの未満フラグ(l)の4つをもって桁DPする、かなりめんどくさい
ECR008-E Zbazi in Zeydabad
O(nm)かO(nm log(nm))くらいが限界なので、各マスについてすぐ答えが出るようにすることを目指す
あるマスから左に / 左下に / 右に何マス連続するか？を前計算しておくと、区間sumのセグ木を使うことでそれぞれのマスの答えがわかる、こういうのすき
ECR009-D Longest Subsequence
GCD, LCMで調和級数になるいつもの
LCMを決め打った時に使える個数を求めて、あとは復元するだけ
ECR010-E Pursuit for Artifacts
解けなかった...
a->bに一筆書きできるか？という問題には「二重辺連結成分分解」が有効なことがある
a->bにいたる途中にある二重辺連結成分にzi = 1となる辺が含まれるかどうかを確認すればよい
ECR011-D Number of Parallelograms
Parallelogramって単語はじめてしった
長さと向きが等しいベクトルがあれば、それらを辺として平行四辺形がつくれるので、mapで管理する
ECR011-E Different Subsets For All Tuples
もし数列が与えられた場合は部分列DPになるので、それをベースに考える
数字については対称性があるので、それを利用すると遷移をまとめることができる
ECR012-E Beautiful Subarrays
区間の個数を求める問題の典型で、累積和的に考えて、左側の値をmapか何かで保持しておくものがある
BinaryTrieを使って、左側の値を保持しておき、xorがk以上となるものの数を計算する
なんかしらんけどMLEでどうしても通らなかったのであきらめた
ECR013-E Another Sith Tournament
苦手で解けなかった...
N≦18なのでbitDPが頭に浮かぶ、期待値DPなんだけど確定しているところから攻めていくべきなので、
dp[i] = 戦い終わった人がi(bit)であるときに、勝利する期待値
とおいて、dp[1<<N -1] = 1としてメモ化再帰で計算していく
ECR014-E Xor-sequences
N≦100, K≦10^18という制約がいかにも行列累乗っぽい
あるaiに対して条件を満たすものの個数は愚直にやって求まるので、それを行列において累乗する
ECR014-F Couple Cover
勝つ方を数えても、負ける方を数えても一緒なので、取りうる値の範囲が狭い負ける方を数えることにする
A×B = Cとなる(A,B)の個数は調和級数を用いてO(maxAi log maxAi)で求められるので、これを全体の数からひけばよい
ECR015-D Road to Post Office
O(1)場合分け
車の方が速いので乗ったからには壊れるまで乗った方がよい、同じ長さを走るのに修理時間を含めて車が速いか徒歩が速いかで場合分け
ECR015-E Analysis of Pathes in Functional Graph
ダブリングやるだけ
和とmin両方あるけど、ダブリングのDPテーブル作れば演算を変えるだけ
ECR016-E Generate a String
ABC-Dで何回かみた最短路に落とし込むやつ
制約が厳しめなので01BFSとかを使う方がいいかな
ECR017-C Two strings
よくある左側からの最善+右側からの最善を計算するやつ(Yutori)
添え字でめっちゃ落とされた...丁寧にしましょうね
ECR017-D Maximum Path
状態をもつDP、場合分けはきちんと列挙して頑張る
最近ABCで出たのに似てる(Keep Conect)
ECR017-E Radio Station
まず絶対値は嫌なのでソートしておく
k ≦10が特徴的で、|fi - fj| ≦ kは(fi - fj) = -k ~ kで間に合うのであんまり深く考えなくてよくなる
あとはSegment Treeでがんばる
ECR018-C Divide by Three
3で割ったあまりで個数を分類しておく
取り除く数は少ない方がいいので、取り除くパターンは(1),(1,1),(2),(2,2)のいずれかになる
それぞれ条件を達成できるか調べてその最大値をとればよい
取り除くのであれば、S[i] < S[i+1]となっているところが優先(その桁が大きくなる)
ECR018-D Paths in a Complete Binary Tree
ABCで見た(Moves on Binary Tree)
上の問題とはちょっと移動の仕方が違うけど、それぞれの移動がbitの操作で表される
ECR019-D Broken MST
各頂点に「その頂点からの部分木を考えたときに、trueとなる数の集合」をsetでもつ
すると、マージテクをしながら木DPをすることができる
マージするときに条件を満たさないもの(Lからマージするならvより大きいもの)を取り除いていくとよい
ECR019-E Array Queries
kが小さいときに移動が多くなって困るので、ここだけメモ化しておく
あとは愚直にする
kは√Nくらいにするとよい
ECR020-C Maximal GCD
gcdを固定すると、長さの最大値が分かるのでそれを計算
復元は余ったものを最後に押し付ければよい
ECR020-D Magazine Ad
空白付きの入力しないのがめんどくさい...
ちゃんと入力出来たらにぶたんするだけ(Longest X)
ECR020-E Roma and Poker
O(n)で解いてた... n, k≦1000なのね
まず最後が勝ちor負けで決め打ちできる
決め打ちすると、後ろから考えることで「i番目まで考えて達成可能なscoreの範囲」を更新していける
これが初めまでみたときにscoreの範囲に0が入っていればよい
復元は、どっちでもいいときは適当にしてギリギリの時だけちゃんと見る
ECR020-F Coprime Subsequences
いつもの除原理(?)っていうやつ(Sum of gcd of Tuples hard)
余事象を考えて、「公約数がkとなる部分列の数」を数え上げることを考える
ECR020-G Periodic RMQ Problem
区間更新なので遅延Segment Treeをうまく使いたい
必要になる座標はたいして多くないので、それを座標圧縮して更新・クエリ応答を楽にする
座標圧縮した区間それぞれについてあらかじめ区間minを計算したSegment Treeを構築して、そこに区間更新を適用すればよい
おわり
今度はもうちょっと小分けにして出そう...つかれた...
