CodeForces Contest #94

差不多一個月沒打CF (因為和 training 的時間相撞)
感覺題目的整體難度又提高了

A - 沒看到是 8-dir 寫了 4-dir 所以錯了 2 棍..

D - 感覺有些像 shy tortoise, 建立 freq[] 後由左到右處理, 不斷進行 freq[i+1] -= freq[i]

B - 比以往的 B 難, 做法有點像 suffix array 的思想, 先比較第 1 個位, 然後比較第 2 個位.. 但是 TLE 了, 因為用了 v[] 去表示可能開始的位置, 但其實應該用一條 list[] 去保留便可以, 前者的時間複雜度最差情況會是 O(N²)

C - 花了很多時間才想到可以 x, y 分開做, 得出 cnt[i] = sum{cnt[j] * (j - 1 - i), j > i}, 但仍然是 O(N³), 把式重寫成 cnt[i] = sum{cnt[j] * (j - 1)} - sum{cnt[j]} * i 可降至 O(N²)

今次的題目難度和次序很奇怪, 對我來說, 難度應該是 A -> D -> C -> B..