2017-08-18から1日間の記事一覧

August Long Challenge 2017: Flower Pots

CHTのO(BN^2)解を最初投げたんだけど通らなかった。解法は難しくないにも関わらず通している人が少ないのは集団心理か何かだろうか。 計算量 \(O(BN^2)\) キーワード DP 解説 まずDPで解くことを考える。状態は着火区間と経過秒数とする。\( [L,R] \rightarr…

August Long Challenge 2017: Walks on the binary tree

計算量 \(O(Q \log^2 N)\) キーワード persistent segment tree | zobrist hash | binary counter | binary search on segment tree | lcp 考察 これはそもそもbinary stringの問題である。 文字列数が2であればlen(s)+len(t)-lcp(s,t)で計算できる。複数文…

August Long Challenge 2017: Hill Jumping

正答数を見る限りだと正攻法ではないんだろなとは思う。 計算量 \(O(100 Q \log N)\) キーワード link-cut tree | envelope 考察 各点におけるジャンプ先をsucc[i]とする。変更クエリにより書き換わるsuccの要素数はたかだか200である。 succ[i]で繋いでいく…