はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree, Manacher, Suffix Tree]

競技プログラミング

文字列アルゴリズム

  • Suffix Array
    • 接尾辞配列
    • 全文探索、パターンマッチングに使える
  • LCP
    • ある2つの文字列について接頭語がどれだけ一致しているか
    • 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列のLCP」参考
  • Trie, Aho-Corasick
    • Trie : 複数文字列から作った木
    • Aho-Corasick法 : 複数文字列のマッチングアルゴリズム 資料
    • Aho-Corasick法で作った木に対してDPする典型がある
  • Z-algorithm
    • z[i] := S[0..]とS[i..]の文字列での共通文字数
    • O(N)で構築できる
    • 覚書
    • 動的に作れるみたい 問題 実装？
  • Palindromic Tree, eertree
    • 回文にまつわる色々なことができる木
    • 数え上げ問題に使える。（最大最小でも使える？）
    • 参考1 参考2 参考3
  • Suffix Automaton
  • Manacher
    • 参考
    • A[i] := i番目を中心としたときの最長回分の半径。半径とは(全長+1)/2のこと
    • O(|S|)

問題

SuffixArray,LCP

（未解決）
https://kimiyuki.net/categories/suffix-array/
http://kenkoooo.hatenablog.com/entry/2016/11/17/201707
http://www.prefield.com/algorithm/string/suffix_array.html
　
KMP,Aho-Corasick

KMP法で最短周期を取得する問題

Trie

Trie上でのdfs

Aho-Corasickで作った木上でのDP

Palindromic Tree

Manacher

Suffix Tree

z-algorithm

Codeforces Round #406 問題と解説

競技プログラミング

http://codeforces.com/contest/786
http://codeforces.com/contest/787

A. The Monster

http://codeforces.com/contest/787/problem/A
t回目にAさんはb+ta秒に叫び、Bさんはd+tc秒後に叫ぶ。
同時に叫ぶのは最短で何秒後か。

B. Not Afraid

http://codeforces.com/contest/787/problem/B
N宇宙からAさん,Bさんがそれぞれ来る。
それぞれ、どちらかが嘘つきでどちらかが正直者である。
Mグループあり、全員が嘘つきになりうるグループがあるなら"YES"、無いなら"NO"

C. Berzerk / A. Berzerk

http://codeforces.com/contest/787/problem/C
http://codeforces.com/contest/786/problem/A
2人でゲームをする。
それぞれ使えるカードが決まっており何回でも使える。
0～N-1個の数字が昇順に円状に並んでいる。
AさんBさんのどちらかが先攻で、初期位置が1～N-1の全てのパターンについて、先攻がWin, Lose, Loop（最適に動かすと勝敗がつかない）のどれかを答えよ。
ゲームは以下のように進行する

  • 位置がxであるとする
  • (自分の手持ちのカードのある数 + x) % Nへ移動可能
  • x==0へ移動させることが出来たプレイヤーが勝ち
D. Legacy / B. Legacy

http://codeforces.com/contest/787/problem/D
http://codeforces.com/contest/786/problem/B
1～Nの頂点があり、以下のクエリに従って有向辺を付けていく
1. 頂点vから頂点uへコストw
2. 頂点vから頂点[l,r]へコストw
3. 頂点[l,r]から頂点vへコストw
頂点Sを始点として各点の最短距離を求めよ

E. Till I Collapse / C. Till I Collapse

http://codeforces.com/contest/787/problem/E
http://codeforces.com/contest/786/problem/C
N要素の配列Aがある。
これを連続する要素毎にグループ分けすることを考える。
各グループ最大でもK種類の数を含むことができるようにして分けるとして、最小何グループに分割できるか。
K=1...N全ての場合について答えよ。

続きを読む

競技プログラミングにおける動的計画法更新最適化まとめ（CHT, MongeDP, AlianDP, インラインDP, きたまさ法, 行列累乗）

競技プログラミング

動的計画法更新最適化？

  • セグメント木や累積和
    • dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]
    • dp[i][j] = min(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
    • dp[i][j] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
    • みたいに区間和や区間最大最小をもたせることで更新を行う。
  • 行列累乗
    • DPの更新式を見てみると、一回の更新操作が行列の形になるときがある
    • この場合は行列を繰り返し二乗法の要領でN乗しておくことで、N番目の要素を高速に取り出せる。
  • MongeDP
    • 別名,Knuth Optimization, Knuth-Yao speedup, 最適二分探索木問題, MongeDP
    • 一番短いMongeDPがいいんじゃないかなと思ってる
    • 「f(i,l) + f(j,k) >= f(i,k) + f(j,l), i <= j, k <= l」を満たす二変数関数はMonge性を持つ
  • インラインDP
    • skyさんによる素晴らしい記事
    • DPで2次元配列となるが、遷移が単純なので、普通なら空間O(NM),計算量O(NM)かかる所を、セグメントツリー全体をDPの配列として更新していくことで、空間O(N),計算量O(MlogN)で済むテク
    • 普通の配列でやるインラインDPもある。入門的。DPをするときのメモリ節約術を思い立たせる
    • 名前が無いのでここに追加するのに困っていたが、インラインDPという名前はとても良いと思う（なんとなくかっこいいので）

問題

CFにあったまとめ

セグメントツリーや累積和

行列累乗

分割統治

CHT

http://codeforces.com/blog/entry/8219
http://arc070.contest.atcoder.jp/tasks/arc070_c
http://pekempey.hatenablog.com/archive/category/Convex%20Hull%20Trick

MongeDP

インラインDP

きたまさ法

（あんまり関係ないけど）遷移が限られる関係で最適化できる動的計画法問題

Week of Code 30 問題と解説

競技プログラミング

問題

Candy Replenishing Robot

https://www.hackerrank.com/contests/w30/challenges/candy-replenishing-robot
カップ内のボールの数をb個とする。最初はb=N。
これについて以下の操作をT回する。

1. C[i]個のボールを取り除く。つまり、b=b-C[i]（各操作で取り除けることが保証される）
2. 残ったボール数が5個未満(b < 5)ならば、カップ内のボールの数をN個にするように(N-b)個を足す

操作2で足されたボールの総和は？

Find the Minimum Number

https://www.hackerrank.com/contests/w30/challenges/find-the-minimum-number
2つのint,intの最小値 -> min(int, int)
3つのint,int,intの最小値 -> min(int, min(int, int))
4つのint,int,int,intの最小値 -> min(int, min(int, min(int, int)))
となるとき、Nつのintの最小値の文字列は？

Melodious password

https://www.hackerrank.com/contests/w30/challenges/melodious-password
N文字の以下のルールを満たす文字列を全て出力せよ。

  • 小文字の英語だけ使う
  • 子音と母音を交互に置く
  • 'y'は使わない
Poles

https://www.hackerrank.com/contests/w30/challenges/poles
N本の電柱をK本にまとめる。
電柱には重さW[i]と高度X[i]がある。
ある電柱は低い高度へ動かすことしかできず、コストW[i]*dXだけかかる。
コストの総和の最小値は？

Range Modular Queries

https://www.hackerrank.com/contests/w30/challenges/range-modular-queries
N個の数列Aがある。
Q個の「[left, right]の範囲でxを法にした時にyとなる要素数を答える」クエリに答える。

A Graph Program

https://www.hackerrank.com/contests/w30/challenges/a-graph-problem
N頂点の無向グラフGがある。
この点誘導部分グラフG'のうち、(G'の三角数)÷(G'の頂点数)が最大となるグラフの点集合を出力せよ。
三角数とはグラフの点集合のうち、(a,b),(b,c),(c,a)に頂点がある三点(a,b,c)の組となる数のこと。

Substring Queries

https://www.hackerrank.com/contests/w30/challenges/substring-queries
N個の文字列がある。
この文字列に対してQ個のF(S[x], S[y])のクエリに答えよ。
F(s, ss) := 文字列sと文字列ssでそれぞれ連続する部分文字列を取った時の最大の長さ。

続きを読む

Codechef March Cook-Off 2017 問題と解説

競技プログラミング

https://www.codechef.com/COOK80

問題

Safe Robot

https://www.codechef.com/COOK80/problems/ROBOTG
縦N横Mのマスがある。
ロボットはLRUDから構成された命令に従って移動する。
全ての命令の過程でマス目からはみ出ないロボットの初期マスが存在するか。
すれば"safe"、さもなければ"unsafe"

Rainbow Graph

https://www.codechef.com/COOK80/problems/RAINBOW
N頂点の無向完全グラフがある。
各辺には色（自然数）がついている。
頂点の部分集合で全ての頂点から出ている辺のうち少なくとも色が異なる2辺があるものを"面白い"とする。
面白い頂点の部分集合のうち、頂点数が最大のものは？

Yet Another Card Game

https://www.codechef.com/COOK80/problems/CARDS777
R個の赤カードとB個の青カードがある。
P個の赤コインと(R+B-P)個の青コインがある。
R+B回、以下のクエリを行う
1. コインを1つ選ぶ
2. カードをランダムに1枚選ぶ
3. もし、同じ色ならば1ポイント得点
得点できる点の期待値は？

Increasing Xor Sequence

https://www.codechef.com/COOK80/problems/INCXOR
N個の数列Aがある。
以下のルールを満たすようなN個の数列Bは何通りあるか(mod 10^9+7)。

  • 0 <= B[1] <= B[2] <= ... <= B[N] < 2^31
  • A[1] xor B[1] <= ... <= A[N] xor B[N]
続きを読む