2016-01-01から1ヶ月間の記事一覧
問題 discovery2016-qual.contest.atcoder.jp 解法 DDPC 2016 予選 解説 from AtCoder Inc. www.slideshare.net解説スライドの通り、出来るだけ前の方をaで埋めて、置換しきれない分は辞書順最小の接尾辞を探している。接尾辞を探すのは Suffix Array ではな…
問題 codeforces.com 解法 内側の円は中心の点と最も近い線分との距離になる。外側の円は中心から最も遠い頂点との距離になる。 点と線分の距離を求めるライブラリ double distanceVertex(pair<double, double> p1, pair<double, double> p2) { double dx = p1.first - p2.first; double dy =</double,></double,>…
解法 bitDP補集合のビットマスクを列挙する方法頭いい。 コード // #define _GLIBCXX_DEBUG #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #inclu…</set></stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>
15 Coding Contest Creation DP コード #define _GLIBCXX_DEBUG #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include …</set></stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>
Codeforces 皆勤賞 AtCoder 皆勤賞 yukicoder 皆勤賞 頑張るぞ〜〜!
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.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>
問題 tkppc.contest.atcoder.jp 解法 動的計画法で後ろから数字の桁数を決めていく。この時、s[i, k] と s[j, k] の文字列の大小関係を比較したいが、普通にやるとO(N)かかってしまう。そこでSA-ISを使うのが想定解法っぽい。 mayokoex.hatenablog.comが、SA…