CEOI 2018 Day1 Lottery

CSA

5時間3問ratedコンテストのうちの1問。5時間がっつり粘った結果、この問題に関しては45点→80点と伸び、コンテスト直後にAC。他の2つは歯が立たず、解説の登場待ち。

45点解法 O(N³)

80点解法 O(N²)

例えば、1つ目の区間と2つ目の区間で比較すべき文字の組み合わせ((a_1, a_2), (a_2, a_3), ... ,(a_l, a_l+1))と、2つ目の区間と3つ目の区間で比較すべき文字の組み合わせ((a_2, a_3), (a_3, a_4), ... , (a_l+1, a_l+2))がほぼ全て重複していることに着目する
ずらしながらカウントしていくことで、O(N²)で45点解法と同様の ans[i][j] が求まる
ans[i][k]が答え
追加で subtask 4 と subtask 5 が解けて、80点
subtask 3 はMLE

満点解法 O(N² log q)

45点解法や80点解法だと ans[i][j] で (n-l+1 * l+1) のサイズの配列を確保するため、shortで持たせても最悪 2×5000×5000 = 50MB 程度のメモリが必要となる
今回の問題では32MBのメモリ制限のため、nが大きく、lがnの半分に近い値だとMLEする
- なぜか subtask 3 (q=1, k_1=0) だけが落ちる
クエリ数 q が最大でも100しかないことに着目すると、ans[i][j]のうち、j=k_i 以外の部分は不要なので、メモリを節約できる
k_iをソートしたものをksとして、ans[i][distance(ks.begin(), lower_bound(ks.begin(), ks.end(), (異なる文字数)))] をインクリメントする
45点解法や80点解法と同様累積和
ans[i][distance(ks.begin(), lower_bound(ks.begin(), ks.end(), k_i))] が答え
メモリサイズは最悪でも 2×10000×100 = 2MB 程度