Educational Codeforces Round 123のきろく

問題文和訳はこちら

A. Doors and Keys / Двери и ключи
B. Anti-Fibonacci Permutation / Антифибоначчиевы перестановки
C. Increase Subarray Sums / Увеличь суммы подотрезков
D. Cross Coloring / Раскраска крестиками
E. Expand the Path / Расширь маршрут: 未提出
F. Basis / Базис (実行時間制限: 6 sec): 未提出
結果、感想

A. Doors and Keys / Двери и ключи

R, G, Bの各文字について大文字よりも前に小文字があるかを調べます。find関数を用いたり、配列で既出かどうかを記憶するなどの方法があります。

B. Anti-Fibonacci Permutation / Антифибоначчиевы перестановки

降順順列 $(n,\,n-1,\,\dots,\,2,\,1)$ は条件を満たします。また、この順列の連続する2要素を入れ替えたものも条件を満たすので、これで $n$ 通りの順列を作ることができました。

C. Increase Subarray Sums / Увеличь суммы подотрезков

$1 \leq n \leq 5000$ であるので $O(n^2)$ であっても大丈夫なので、初期状態での全ての部分列の和を計算することができるので、長さ毎にその最大値を記憶します。長さ $i$ のものを $m_i$ とします。
この時 $f(k) = \displaystyle \max_{i} (m_i + x\min\{k,\,i\})$ となるのでそれぞれ計算することができます。

D. Cross Coloring / Раскраска крестиками

最終的な盤面において各セルのについて何番目の操作で着色されたのかが分かれば、最終的な彩色に関わる操作が $l$ 個存在するとき答えは $k^l \bmod 998244353$ となります。

$i$ 番目の操作は、それ以降に行 $x_i$ と列 $y_i$ の両方が塗り替えられる、もしくは全ての行か全ての列が塗り替えられる、のいずれかを満たした時、最終的な彩色に関わず、そうでないとき、関わります。そのため、最後の操作から逆順にどの行や列が操作されたかを記憶しておくことで答えを出せます。しかし、「全てのテストケースでの $q$ の和は $2 \cdot 10^5$ を超えない」という制約はありますが、 $n$ についてはそうでないため、その和は $4 \times 10^{10}$ にまでなる可能性があるので、配列で管理するとTLEとなります。そのため、出てきた行や列をstd::setやstd::unordered_setで管理して計算量を落とす必要があります。(これに気附かず、何度もペナルティを食らいました...)