| 難易度 | 問題名 | 出典 | 解いた人数 |
|---|---|---|---|
| 600 | ほぼ周期文字列 (☆) | 夏合宿2015:day2F | 53 |
| 投票者 | 難易度/推薦 | 投票理由 |
|---|---|---|
| @Rubikun_pro | 600 | (2021-08-19 12:18:59) |
| @SSRS_cp | 600 | (2021-04-19 07:48:45) |
| @square1002001 | 1000 (☆) | 考察面・実装面ともに難しい。文字の種類数を Σ として計算量 O(N + Q log N) の解法を実装したが、非常に多くのステップを利用しなければ解くことができない。自分が (最初に) AOJ に提出した解法 (https://onlinejudge.u-aizu.ac.jp/solutions/problem/2711/review/3324790/square1001/C++11) は Suffix Array を使わずローリングハッシュを使ったが、後になって Suffix Array (SA-IS) を使うとこの問題を O(N log Σ + Q)、つまりほぼ線形時間で解けることが分かった。 (2019-01-05 19:01:01) |
| @HIR180 | 550 | (2017-06-15 01:38:47) |
| @asi1024 | 700 | (Imported) 650 (2016-08-15 07:03:28) |
| @sigma425 | 550 | (Imported) 550 (2016-08-15 07:03:28) |