http://arc085.contest.atcoder.jp/tasks/arc085_d愚直な DP 解を示す。DP の値には一致した文字数を格納してあり、状態は(位置、最後に使った区間番号)としている。0 番目に番兵として区間 [-1,-1] を入れている。 int dp[100][101]; void to(int &x, int y…

http://arc084.contest.atcoder.jp/tasks/arc084_d多項式への言い換えが気持ちがいい問題だった。多項式は気持ちがいい。 #include <iostream> #include <algorithm> #include <vector> using namespace std; const long long mod = 998244353; string gcd(string a, string b) { while (t</vector></algorithm></iostream>…

実装が結構大変。https://yukicoder.me/problems/no/590 解法 順列なので辺 $ i \to A_i$ のグラフを考えよう。このようなグラフはサイクルの集まりになることに注意したい。\( (x,y) \to (i,i) \) と考えるのではなく、逆向きの操作を考えて、\( (i,i) \to …

A 問題 尺取法をベースに解法を設計した。等差側とそうでない側、それぞれ p, q を尺取ポインタとして、うまく２つを動かしていく。もし \( ap+d 実装の工夫としては、m 側に番兵を設置し条件を緩やかにした。 #include <iostream> #include <algorithm> #include <string> #include <vector> #inc</vector></string></algorithm></iostream>…

https://www.codechef.com/problems/KOK100euler-tour tree。O(n log n) ではあるけど、定数倍が重くて通らなかった。euler-tour を考えるとき辺で見るか、頂点で見るかどちらかだと思うけど、辺で考えると対称性が良い気がするので辺で実装している。今回の…

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

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

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>…

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

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

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

計算量 \(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)で計算できる。複数文…

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

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の倍数になる部分列…

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

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 …

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

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

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

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

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]; }…

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

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

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

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

https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximum-disjoint-subtree-product 解法 全方位木 DP の知名度も高まってきたので説明は省略する。以前に作成した全方位木 DP のライブラリを使用した。 #include <iostream> #include <cstdio> #include <vector></vector></cstdio></iostream>…

https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness 解法 DP。1～n の順列に n+1 を挿入するイメージで更新していく。山の頂上（極大点）の個数を状態として持つと良い。dp[i: 順列のサイズ][j: 頂上の個数] とする…

A 問題 +- の列があって、連続する K マスを反転するのを繰り返して全部 + にする問題。まったく同じ問題が蟻本にある。 B 問題 10 進表記で数字が昇順になるような N 以下の最大の整数を求める問題。なるべく上位桁は動かさない方がいいということ、ある桁…

http://agc012.contest.atcoder.jp/tasks/agc012_c 解法 空の列も良い文字列だとみなす。順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。 A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。 A←A+[foo], B←[…

http://agc012.contest.atcoder.jp/tasks/agc012_b 解法 di が小さいのが鍵に見える。dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。 補足 ある頂点から距離 d …