String

AtCoder Regular Contest 077F: SS

http://arc077.contest.atcoder.jp/tasks/arc077_d実験的にやるのがたぶん正攻法だけど、もうちょっと文字列の周期のこととかに気を配れるとよかった。解説にも書いてありますが、g(n+2)=g(n+1)+g(n)になります。これは実験をすると比較的簡単に気づけます。…

POJ 3690: Constellations

http://poj.org/problem?id=3690蟻本に書いてあるように二次元hashをすればいいです。hashといえばこの記事 http://hos.ac/blog/#blog0003 が有名ですが、ここに書いてあるように3つのmodでhashをとるようにしてみました。注意:TLE解法です。 struct ll3 { …

SA-IS

https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf elementi-bioinformatica/Two Efficient Algorithms for Linear Time Suffix Array Construction.pdf at master · Al…

AtCoder Regular Contest 081E: Don't Be a Subsequence

https://beta.atcoder.jp/contests/arc081Typical DP Contest FGHIJ - omochan's diary これのGとほとんど同じで、dp復元がくっついただけ。 でも1-originで逆から見ていくのでかなりこんがらがった。普通に0-originのstringを参照するときに-1をつければい…

MP法

MP法を勉強したのでメモ。文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログこれを参考にしました。A[i]の定義はS[0:i-1]の接頭辞と接尾辞が最大何文字一致しているかである。 [0:i-1]が一致しているから…

AtCoder Regular Contest 078E: Awkward Response

http://arc078.contest.atcoder.jp/tasks/arc078_cまず桁数を特定する。これは1, 10, 100,...と比較するとわかる。 それからは上の位から数字を特定していく。 例えば(10^3,10^4)の区間において49990を投げると、(10^3,5*10^3)でyes,[5*10^3,10^4)でNoとなる…