Codeforces Round #545 (Div. 2) - 鴨井遼競技プログラミング

今日から10日ほど予定があって競プロのコンテストに参加できなさそうだったので、朝4時5分開始だが頑張って参加した。

A問題は見返したら17分もかかっていた。寝起きなので許してほしい。

B問題はどちらもできる人を1番目のグループに何人配属して、clownしかできない人を1番目のグループに何人配属するか、というのを全て試して等式が成り立つ場合が存在したら出力した。これがなぜか40分かかっている。考察に少し時間がかかったが、それ以上に実装が冗長になっている。

C問題は行と列のそれぞれについて同じ値は同じランクになるランキングを作成して、各交差点について下から何位か、上から何位かという値を保持しておく。これは $O(n^2 \log n)$ で構成できるので通る。各交差点について、行・列におけるランキングの下からの順位の最大値と上からの順位の最大値を足した値が答えになる。これも40分くらいかかった。

D問題は最初に読んだときに完全に勘違いをしていて異常に簡単な問題だと思ったが、部分列が重なる場合がある（1WAしてから気づいたので頭が悪い）。 $s [ 0:i ]$ と $s[ n-i:n ]$ が一致する最大の $i$ を求めれば良いのだが、これが愚直に判定して間に合うという幻想が見えていてTLEを食らって時間切れになった。