pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 国内予選

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

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] となっていたら下図のように領域を分…

World Codesprint 10: Maximum Disjoint Subtree Product

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

World Codesprint 10: Permutation Happiness

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

GCJ 2017 Qual

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

Splay Tree の可視化

Chrome と Firefox では少なくとも見れます。重くて見れない方はごめんなさい。https://pekempey.github.io/splay_tree/splay_tree.html

Link-Cut Treeの可視化(失敗作)

Link-Cut Treeをうまく可視化できないか考えてました。exposeの可視化を目標としていましたが、うまい可視化が思いつかなかったので、あまり役に立たない可視化だけ公開します。察しのいい人なら実装まで想像がつくと思いますが、二分木のmerge/splitに慣れ…

Mo's Algorithmの可視化

SVG で描いてみた。処理落ちしたらごめんなさい(結構重い気がする)。https://pekempey.github.io/mo_algorithm/mo.htmlInternet Explorer では見れないのでご了承ください。

AtCoder Grand Contest 012 C: Tautonym Puzzle

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

AtCoder Grand Contest 012 B: Splatter Painting

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

AtCoder Grand Contest 012 A: AtCoder Group Contest

http://agc012.contest.atcoder.jp/tasks/agc012_a 解法 入力を昇順にソートして考える。適当な戦略を取ってみる。先頭から3つずつペアにしていくのはどうだろう。 _o__o__o__o_ 000111222333oになっているのが中央値。これは改善ができる。 _o__o___o_o_ 00…

CSAcademy Special MVC

editorial読んで概要はすぐに理解できたけど、cactus上のDPを整理するのに手間取った。この回難しすぎる。https://csacademy.com/contest/archive/#task/special-mvc/

Educational Codeforces #18: C. Divide by Three

http://codeforces.com/contest/792/problem/C

Educational Codeforces #18: E. Colored Balls

http://codeforces.com/contest/792/problem/E

Codeforces #405 Div.1 ABC

赤コーダーになりました。

Codeforces #404 E. Anton and Permutation

http://codeforces.com/contest/785/problem/E

Codeforces #404 D. Anton and School - 2

http://codeforces.com/contest/785/problem/D

CSAcademy #20 Palindromic Concatenation

https://csacademy.com/contest/round-20/#task/palindromic-concatenation

「みんなのプロコン」D - 工場

C: 検索 - 「みんなのプロコン」 | AtCoder

Query Sums on Strings O(K^2Q)

https://www.hackerrank.com/contests/university-codesprint-2/challenges/querying-sums-on-strings

Codeforces #399 ABCDE

A. Oath of the Night's Watch B. Code For 1 C. Jon Snow and his Favrourite Number D. Jon and Orbs E. Game of Stones

右方向の和を求めるBIT

本当にどうでもいい内容です。

Codeforces Round #397 F. Sourvenirs

高速化できたので追記しました。http://codeforces.com/contest/765/problem/F

Codeforces Round #397 ABCDE

A. Neverending competitions 問題概要 解法 B. Code obfuscation 問題概要 解法 C. Table Tennis Game 2 D. Artsem and Saunders E. Tree Folding

Codeforces Round #396 (Div. 2) A,B,D,E

C 問題は読めなかったので省略します。http://codeforces.com/contest/766 A. Mahmoud and Longest Uncommon Subsequence B. Mahmoud and a Triangle D. Mahmoud and a Dictionary E. Mahmoud and a xor trip

ポテンシャル解析

ならし計算量を解析するテクニックとしてポテンシャル解析というものがある。 ポテンシャル解析とは何かを簡単に説明し、いくつかの簡単な解析例を示す。

経路圧縮のみを用いた union-find の計算量解析

スプレー木がうまくいくのだから、union-find も似たような理由でうまいくのではと思い解析に挑戦してみました。スプレー木と同じポテンシャルの設定で解析できたのでメモしておきます。特に何かを参考にしたわけではないので間違っていたらごめんなさい。ポ…

Codeforces Round #395 (Div. 1) D. Timofey and a flat tree

http://codeforces.com/contest/763/problem/D 問題概要 木が与えられる。ある頂点を根としてみたとき n 個の部分木がある。もっとも部分木の形状の種類が多くなるような根の選び方を求めよ。部分木の形状が等しい、というのは根付き木として同型であるとい…