GCJ 2018 round2

A 問題 i 番目と i+1 番目の間をいくつのボールが通過するかを計算できると、それをそのまま。 B 問題 丁度にする必要はなくて、適当に辻褄をあわせることができる、というのが重要な考察。 (i,j) を使う、というのを n×n グリッドの (i,j) の位置に駒を置く…

FFT (2)

Wikipedia には Hadamard Transform について次のように書かれている。Hadamard transform - Wikipedia。 The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multi…

April Challenge 2018

Chef 側の解説がまだ出てないので、それ読んで思うものがあったら更新します。CHEFAT: この制約なら SIMD O(n^2) 通る。そうは言っても 2 ケースほど TLE になってしまったので、平方分割+遅延評価で平均的に速くなるようにした。 多くの提出は $\log(1-x)=…

FFT

(追記:rots の配置変えたら SIMD でやったのとそうでないのとで速度が全く同じになった…。切ない) 追記 環境 多項式乗算を行うだけのコード。サイズ n の 2基底FFT を n/4, n/4, n/4, n/4 の FFT に分割し、n/4 の FFT を SIMD で4並列で行う。実装が簡単…

Visualization Floyd's Cycle Detection

Floyd's Cycle Detection

CSAcademy Strange Substring

SA+LCP の解法もあるけどここでは触れない。https://csacademy.com/contest/archive/task/strange-substring/文字列 A+$+B の DAWG を使うことが基本方針。状態 q に対応する文字列の最終出現(文字列末尾の)位置を fin(q) とする。DAWG の性質から fin は …

コンパクトにmod逆元を求める(続き)

コンパクトにmod逆元を求める - pekempeyのブログ で一部解析していなかった部分がうまくいったので書いておきます。具体的には 2-log4 の部分です。a.hs · GitHub再帰の深さの最大値、再帰の深さの総和、最大値を与える最小の x、最大値を与える最大の x、…

CodeChef March Challenge 2018

PSHTRG Q=1 で考えてみよう。これは,数列をソートして最大 3 つを見る,それで駄目なら次の 3 つを見るというのを繰り返すことで求められる。この繰り返しが O(log max a) 回しか起きないことに気がつくと,50th max 程度まで保持するセグメント木があれば…

ARC091 F Strange Nim

https://arc091.contest.atcoder.jp/tasks/arc091_dK を固定して Grundy 数 g(n) を考える。実験すると g(Kn)=n であることに気づける。g(Kn)=n ということは,その直前 n 個を見ると 0..n-1 の順列になっている。これに気がつくと漸化式が見える。 実験から…

yukicoder 661, 662, 663, 664, 665

最近いろんな作業を Rust で書いてるんですが、Rust やってると Haskell が書きたくなってくる。664はまだです。 661 ハローキティはりんご3個分 import Control.Monad main = getLine >> getContents >>= mapM_ (putStrLn . solve . read) . lines solve n …

SRM 729 Med. FrogSquare

問題概要 n × n のグリッドが与えられる。スタート地点は (sx,sy) でゴール地点は (gx,gy) である。ユークリッド距離が d 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は -1 を出力せよ。 誤解法 四隅だけ使えばよく,到達でき…

ランダムに生成した行列は高確率で正則

$\mathbb{F}_p ^{2 \times 2}$ の行列をランダムに生成すると、高確率で正則になる。$\mathbb{F}_p ^{2 \times 2}$ のうち、正則なものは $(p^2-1)(p^2-p)$ 個ある(解析は付録に書いておく)。そのため、ランダムに生成した行列が正則になる確率は\begin{eq…

状態がループするゲームの解析(後退解析)

状態がループするゲームは、DAG ではないため動的計画法が使えない。代わりに 後退解析 というテクニックを用いる。次のゲームを考えよう。n 頂点 m 辺の有向グラフが与えられる。最初、頂点 s に駒が置かれている。プレイヤーは駒を隣接頂点に動かすことが…

ARC 089 D. Checker

https://beta.atcoder.jp/contests/arc089/tasks/arc089_bこの解説では、座標を(横,縦)で表している。$(x,y)$ が黒であることと $(x \bmod 2K, y \bmod 2K)$ が黒であることは同値である。 $(x,y)$ が白であることと $(x+K,y)$ が黒であることは同値である…

CF #458 E. Palindromes in a Tree

重心を求めるコードが間違っていたので修正しました(sz[v] >= x / 2ではなくsz[v] > x / 2が正しい)。計算量に影響はないです。2018-01-22 21:25http://codeforces.com/contest/914/problem/E重心分解による分割統治法で解く。重心を c としたとき、回文パ…

CF #458 G. Sum the Fibonacci

AND, OR, XOR 畳み込みを使う。ANDは分割統治、ORは高速ゼータ変換と高速メビウス変換、XORは高速アダマール変換を使うことで処理できる。n=2^17 としたとき、ANDがO(n log n)、ORがO(n log^2 n)、XORがO(n log n)になっている。OR も O(n log n) で行けるの…

根が頻繁に変わる木で親を求める

根が のとき頂点 の親を で求めるコード。以下の場合分けによるアルゴリズム。 $r$ が $u$ の子孫だった場合、$r$ を $u$ にぶつからない限界まで持ち上げる。 それ以外の場合、根が頂点 0 だった場合の親をそのまま返す。 // Verified at http://codeforces…

根が頻繁に変わる木でLCAを求める

根が $r$ のときの頂点 の LCA を とする。 のうち最も頂点 から遠い頂点が である。この機能を持ったHL分解のライブラリを書いておく。きちんとした証明はしてないけど多分問題ない。 // Verified at http://codeforces.com/problemset/problem/916/E struc…

CF #457 E. Jamie and Tree

http://codeforces.com/problemset/problem/916/ELC-tree は根を変更するクエリと lca を求めるクエリを捌ける。ET-tree は辺の追加・削除と連結成分全体に x を一様加算するというクエリが捌ける。これらを組み合わせることで容易に解くことができる。 #inc…

CF #457 D. Jamie and To-do List

http://codeforces.com/problemset/problem/916/D誤読さえしなければ解法は自明。永続multiset と永続配列があれば良い。永続multisetは使いまわせそうな形で再実装した。内部的には LLRBtree を用いている。 ポインタ型が64bitというのが厄介で、nodeにポイ…

AGC 020 A..C問題

A問題 端に追いやられたら負けである。よって相手に近寄るように移動するのが最適行動になる。この戦略を実際にシミュレートすることで答えが得られる。 main = do [n, a, b] <- map read . words <$> getLine putStrLn $ turnA n a b turnA :: Int -> Int -…

CF Good Bye 2017 G: New Year and Original Order

http://codeforces.com/contest/908/problem/G 解法 上の桁から決めていく桁 DP により解くことができる。ソート済み整数はレピュニット数*1 の和で表せるという性質が役に立つ。たとえば 1122244 という整数の場合 1122244 1111111 11111 11 11という表現が…

Zig-Zag Numbers

条件を満たすような○○以上△△以下の整数を求める問題は、上の桁から決めていくDPがよく使われる。DEGwer さんの記事いわく、下から決める方法も上手くいくらしいので、Zig-Zag Numbers と呼ばれる非常に面倒な問題を下からの桁DPで解いてみた。F - ジグザグ数…

ARC086 E問題 Smuggling Marbles

E: Smuggling Marbles - AtCoder Regular Contest 086 | AtCoder 解法 縮約解について説明する。よく考えるとマージテク解と本質的に同じ。深さが等しい頂点をまとめて計算できるのは自明だと思いたい。普通にやると$O(depth\times n)$ だが、各深さごとに木…

CSA #60 E問題

Rust で書き直したのだが Rust で提出できなかった。そういえばクロージャの再帰ってできるんだろうか。グラフを引数に渡すのくどい。パスを交差させる必要はなくて、互いに素なものだけ考慮すれば良い。これは適当な木DPで解ける――具体的には、状態を(dp0: …

Prufer sequence によるランダムツリー生成

Prüfer sequence - WikipediaPrufer sequence に関しては wikipedia を参照してください。python の networkx はランダム木生成に prufer sequence を使ってるらしい*1ので実装してみました。Wikipedia に書いてある擬似コードをそのまま実装すると O(n^2) …

非遅延塗りつぶしツリー

大分前に塗りつぶし操作は非遅延でも出きるみたいな事を言っておきながら実装してなかったので実装した。塗りつぶしと総和の木。N=500, Q=500000 でのランダムテストは通ったのでバグは無いと思う(多分)。これを非遅延と呼ぶかは怪しい。原理は意外とトリ…

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 …