mayoko’s diary

プロコンとかいろいろ。

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

AtCoder Regular Contest 050 D - Suffix Concat(その 2)

問題 arc050.contest.atcoder.jp 解法 これを参考に RollingHash でも解いてみました。 topcoder.g.hatena.ne.jp考え方(ソートの仕方)はさっきと同じです。問題なのは, RollingHash を使ってどうやってソートをするか, ということなんですが, s.substr(lhs),…

AtCoder Regular Contest 050 D - Suffix Concat

問題 arc050.contest.atcoder.jp 解法 問題設定が以前解いた問題に似ています。 mayokoex.hatenablog.comこれから, 文字列のソートの仕方は, p suffix array の lcp を使うと上手く行きそうな気がするのでそれを考えましょう。 suffix array 求める -> lcp[i…

AtCoder Regular Contest 050 C - LCM 111

問題 arc050.contest.atcoder.jp 解法 「1 を A 個並べた数」を one(A) と書くことにします。この問題では one(A) と one(B) の最小公倍数を求めたいですが, そのためにとりあえず最大公約数を求めることを考えます(A one(B) を one(A) で割った余りを考える…