https://codeforces.com/contest/1090/problem/J考察有りライブラリ使いまくりで楽しい。 まず文字数を固定します。するとTを少しずつずらした時何通り同じ文字列があるかみたいな問題になります。 こんな感じです。 Tを1文字shift S:aadaa | T: aaaaaba| 文…

https://codeforces.com/contest/1055A ちょっと場合分けがあって面倒ですね。 B 幅1の区間しかたさないので、両脇見ればいいだけです。 C GCD D 良問。違う部分は共通じゃないと行けなくて（なぜかここにきづけなかった)、伸ばすだけ伸ばしてマッチしてほし…

https://arc087.contest.atcoder.jp/C はい。 D XY独立にできます。 E 本質っぽいgrundyのところまではわかったけどtrie木で敗北しました。 まずstringを2分木に対応させます。そうするといろいろな高さの2分木から頂点を取るゲームになります。 高さがdの2…

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

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

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…

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

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

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となる…