SRM 729 Med. FrogSquare

問題概要 n × n のグリッドが与えられる。スタート地点は (sx, sy) でゴール地点は (tx, ty) である。ユークリッド距離が 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 …

ブログの分岐について

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 より小さいサイズが渡されたときには愚直を…