Easy Queries [wavelet matrix 3d]

https://www.codechef.com/problems/DISTNUM2参考にしました。http://min-25.hatenablog.com/entry/2017/09/13/073449改善点はない。 2 段目の wavelet matrix は、サイズが小さい方を採用するようにしてある count に 64 より小さいサイズが渡されたときに…

ACPC2017Day1 F: Steps

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day1&pid=Fdyck 列(正しい括弧列)の数え上げ問題に、深さ上限を与えた問題。dyck 列の総数はカタラン数として知られる。解法の本質はカタラン数の二項係数表現の導出と同じで、エラー…

yukicoder No.569 3 x N グリッドのパスの数

https://yukicoder.me/problems/no/569解法そのものは自明だが、真面目にやるべきものではない。行列による解法の存在に気づければ、解は線形漸化式に従うことが分かるので、その性質を使って楽をする。解の列に対する母関数 a(x) を考える。ここである多項…

RSQ and RAQ, mo's algorithm with update

http://ei1333.hateblo.jp/entry/2017/09/11/211011触発された。n^1/3個に分割しておけば、(l,r)の組がO(n^2/3)通り、時間方向への移動でO(n)、なるほど計算量が落ちている。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_Gこのような単…

ARC 082 E: ConvexScore

Keywords convex hull DP Time Complexity \(O(N^3)\) 汎用的な処理が多数含まれているのでメモ。 #include <iostream> #include <algorithm> #include <vector> #include <complex> #include <cmath> #include <cassert> #include <tuple> using namespace std; constexpr long long mod = 998244353; using P = complex<long long>; </long></tuple></cassert></cmath></complex></vector></algorithm></iostream>…

AIM Tech Round 4 (Div. 1) D. Dynamic Shortest Path

http://codeforces.com/contest/843/problem/D Keywords SSSP | reweighting technique Time Complexity \( O(Q(N+M)) \) Explanation 最小費用流や、負辺を含む全点対最短経路[1]などで用いられるポテンシャルを用いたreweightテクニックを使う。 Reweight …

Goldman Sachs CodeSprint: Transaction Certificates

keywords rolling hash | birthday attack 解法 ハッシュ値が重複するまでひたすら生成し続けるだけで高速に発見できることが知られている。これは誕生日攻撃と呼ばれている。nが小さい場合は重複値が存在しない可能性があるので、100以上になるまで大きくし…

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]で繋いでいく…

Codeforces Round #428 (Div. 2): D. Winter is here

http://codeforces.com/problemset/problem/839/Ddp[i]:=gcdがiになるような部分列の総数とすると以下の関係式が成り立つ。\begin{equation} dp[i]=\text{gcdがiの倍数の部分列の総数}-dp[2i]-dp[3i]-dp[4i]-\cdots \end{equation}gcdがiの倍数になる部分列…

Educational Codeforces Round 26: G. Functions On The Segments

http://codeforces.com/contest/837/problem/G 解法 二次元の総和クエリに落とし込む。高次元クエリを扱うテクニックとして永続的データ構造を用いるという方法がある。永続 segtree により解くことができるが、wavelet matrix を用いて解くこともできる。計…

Educational Codeforces Round 26: E. Vasya's Function

http://codeforces.com/contest/837/problem/E 解法 b-gcd(a,b) は gcd(a,b) の倍数である。つまり次の操作でも gcd は gcd(a,b) の倍数になるはずである。何だかんだでf(a,b)=f(a/g,b/g)が成り立つ。よってf(a,b)の計算は a,bをgcd(a,b)で割る gcd(a,b)≠1 …

コンパクトに一般modの逆元を求める

ユークリッドの互除法は (a,b)->(b,a-floor(a/b)*b) という変換を繰り返すアルゴリズムである。この変換は行列 A={{0,1},{1,-floor(a/b)}}を用いて (a',b')=A(a,b)と書ける。これを繰り返し行うため、互除法の過程は(1,0)=...DCBA(a,b)のような行列積で表せ…

重心分解?

2017/08/02(修正) HL分解と重心分解の定義を誤解してた?HL分解:size[v]<size[c]*2の辺を選択 重心分解:argmax size[c]の辺を選択いままで重心分解で書いてたけど、HL分解の方が実装が楽?(重心分解はmaxの更新が面倒だと思う)。 struct HLD { vector<int> parent, head, vid; HLD(const vector<vector<int>> &g) : parent(g.size()), head(g.size()), vid(g.size()) { int k = 0; vector<int> s(g.size(),…</int></vector<int></size[c]*2の辺を選択>

コンパクトにmod逆元を求める

mod逆元を求めたいだけなのに繰り返し二乗法を書くのは面倒。そういうときに使える手法。素数mod限定。 long long modinv(long long n) { return n == 1 ? n : modinv(MOD % n) * (MOD - MOD / n) % MOD; } 上の計算式は M%n+⌊M/n⌋n=M≡0 (mod M) に基づいて…

yukicoder 550: 夏休みの思い出(1)

https://yukicoder.me/problems/no/550 解法 x3+ax2+bx+c=0 を解く前に x3+ax2+bx+c≡0 (mod 33331) で解く。これは全探索で解くことができ、解の個数が 3 個以下であることが保証されている。得られた解を α,β,γ とすると、元の方程式の解は α+33331k,β+3333…

Codeforces #425 (Div.2) E. Vasya and Shifts

http://codeforces.com/contest/832/problem/E 問題概要 文字列 s1,s2,...,sn がそれぞれ 4 つずつ――全部で4n個――与えられる 使われている文字はabcdeの5種類で、文字列長はすべて m 4n個の文字列の中からいくつか選び、その総和が b になるようなパターン数…

Educational Codeforces Round 25: F. String Compression

http://codeforces.com/contest/825/problem/F 解法 文字列の最小周期はKMP法のテーブルを用いて計算できる。kmp[i]は文字列 S の先頭 i 文字を切り出した文字列の prefix と suffix の最大共通部分である。たとえば aabaabaab という文字列ならば 6 である…

Educational Codeforces Round 25: G. Tree Queries

http://codeforces.com/contest/825/problem/G 解法 一番最初の黒頂点を根 r として考える。黒頂点に囲まれている部分を black-tree と呼ぶことにする。タイプ1 u-r パスを black-tree に併合すればいい。事前に r-u パス上の最小頂点を求めておくことで O(1…

prime counting function

以下の問題を解く際に「n 以下の素数の個数」を高速に求める必要が出てくる。http://codeforces.com/contest/665/problem/F素数列を\(p_0,p_1,\ldots\)とする。\(\phi(x,p_i)\)を\(x\)以下の正整数のうち\(p_0,p_1,\ldots,p_i\)を約数に持たないものの個数と…

yukicoder 546: オンリー・ワン

https://yukicoder.me/problems/no/546 解法 高速メビウス変換というものを紹介する。高速メビウス変換というのは以下のような処理である。 for (int i = 0; i < n; i++) { for (int j = 0; j < 1 << n; j++) { if (~j >> i & 1) { a[j | 1 << i] -= a[j]; }…

ICPC 2017 国内予選D: 弁当作り

問題の解説はせずに、グレイコードの紹介をする。iに対してi^i>>1を計算して列挙すると、隣接する値のハミング距離が 1 になる。これをグレイコードと呼ぶ。 0000 => 0000 0001 => 0001 0010 => 0011 0011 => 0010 0100 => 0110 0101 => 0111 0110 => 0101 0…

ICPC 2017 国内予選F: リボンたたみ

解法 LRどちらを行っても下から何番目にあるのかは変わらない。そのため、各レベルにおいて下から何番目であるのかを求めることは容易である。広げきった状態から一手前の状態を考える。一手前の状態で下半分にあった場合、Lをすれば当然右半分に移動し、Rを…

ICPC 2017 国内予選

うろ覚えだけどメモ。 参加まで チームメンバーに誘われたので参加することにした。ところで、いまいち参加方法がわからない。自分の大学が最後に出場したのは大分昔で、あまり参考にならない。具体的には、コーチとか監督とかどうすればいいのかということ…

ICPC 2017 国内予選E: 論理式圧縮機

解法 DP。dp[i]=出力が i となるような論理式の最小の長さとする。DPのインデックスはf(0000),f(0001),f(0010),...,f(1111)の出力結果を16ビットにまとめたものである。遷移にループが生じるため、最短経路的なDPを行う必要がある。bellman-ford的な手法によ…

Codeforces #419 (Div.1) C. Karen and Supermarket

http://codeforces.com/contest/815/problem/C 解法 最適解は以下のような形である(入力が木になっていることに注意)。ここまで分かると dp[頂点][使用した頂点数][根と繋がっているかどうか] という DP ができることが分かる。しかしこれは O(n^3) ではな…

Codeforces #419 (Div.1) B. Karen and Test

http://codeforces.com/contest/815/problem/B 解法 和の線形性(重ね合わせの原理)を用いて計算するとうまくいく。i 番目の要素以外を 0 として、i 番目の要素が与える影響を調べてみることにする。動的計画法により結果を得ることができるが、それでは O(…

HourRank 20: Birjik and Nicole's Tree Game

https://www.hackerrank.com/contests/hourrank-20/challenges/birjik-and-nicoles-tree-game 解法 黒頂点を post-order でソートする。この列を左から順に見ていき、隣接する 2 点の LCA を列に挿入することを繰り返す。これだけで LCA の閉包(?)が作れ…

World Codesprint 10: Node-Point Mappings

https://www.hackerrank.com/contests/world-codesprint-10/challenges/node-point-mappings 解法 一番左の点(複数あるなら下にある方)を根に対応させる。根を中心に偏角ソートし、たとえば部分木のサイズが [4, 5, 3] となっていたら下図のように領域を分…