ARC 085 F

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

ARC 084 F XorShift

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

yukicoder No.590 Replacement

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

ブログの分岐について

Haskell 用のブログを作ったので、Haskellはそっちに書きます。http://pekeskell.hatenadiary.jp/

Haskell: codefes 2017 qualC

D 問題が解けなかったのはまずい。何故か AtCoder だと DP じゃない気がしてくるんだよね…。 A 問題 point-free style、関数の本質を捉えてる感があって良い。 import Data.List main :: IO () main = getLine >>= putStrLn . yesno . isInfixOf "AC" yesno …

2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest

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

Haskell: ABC075

A 問題 -- Exec time: 2 ms -- Memory usage: 508 KB {-# LANGUAGE ScopedTypeVariables #-} import Data.Bits main = getLine >>= print . foldl1 xor . map (read :: String -> Int) . words B 問題 あまり面白くない書き方。 -- Exec time: 6 ms -- Memor…

Haskell: codefes 2017 qualB

A 問題 後ろを drop みたいな関数は見つからなかったので reverse で誤魔化した。大半の haskell の提出もこうやっていた。 main = getLine >>= putStrLn . reverse . drop 8 . reverse iterate init でいい感じの無限リストを作って 8 番目の要素を取る、と…

Sandy the foodie

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

Haskell: DDCC2017 qual

流石に競技中は C++ を使ったけど Haskell で解き直した。 A 問題 main = getLine >>= putStrLn . yesno . solve yesno :: Bool -> String yesno True = "Yes" yesno False = "No" solve :: String -> Bool solve [a, b, c, d] = a == b && b /= c && c == d…

Haskell: コード祭り予選突破練習会コンテスト

普段と違う頭を使う感じで楽しい。https://not-522.appspot.com/contest/6671465998974976 ダブル文字列/Double String main = getLine >>= putStrLn . concat . replicate 2 B - とても長い数列 main = getLine >> getLine >>= print . sum . zipWith (*) (…

拡張ユークリッド互除法を使って特性多項式を求める

定数係数線形漸化式を持つような数列の先頭 n 項が与えられるので漸化式を求めよ、という問題を解く話。特性多項式を求める方針で攻められる。線形漸化式を持つタイプの数列は母関数が有理式になるので、mod x^2m 上で有理式近似を掛けるときれいに求まると…

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 になるようなパターン数…