2016-01-01から1日間の記事一覧

Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

kenkoooo.hatenablog.comrng_58 さんのコードを参考にした。 よく考えたら、ハッシュなんか使わなくても解けるんだよなあ #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #incl</stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>…

Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

問題 codeforces.com 解法 Rolling-Hashing で文字列の大小関係をO(log N)で求めようのコーナー kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #inc…</queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>

技術室奥プログラミングコンテスト G: おおきなかずを作った

問題 tkppc.contest.atcoder.jp 解法 動的計画法で後ろから数字の桁数を決めていく。この時、s[i, k] と s[j, k] の文字列の大小関係を比較したいが、普通にやるとO(N)かかってしまう。そこでSA-ISを使うのが想定解法っぽい。 mayokoex.hatenablog.comが、SA…