Codeforces Round #677 (Div. 3) - 人間だけど競プロやる

A. Boring Apartments

1,11,111,1111,2,22, ... , 9,99..,9999
を作って、何個目まで使えるか試せばOK

B. Yet Another Bookshelf

右端からの0のエリアと左端からの0のエリアに移動するのは無駄。
右から最初の1と左から最初の1の間にある0を埋めるように移動すればよいから、その0の数が答え。

C. Dominant Piranha

全部が等しかったら不適。
そうでないなら、最大値のうちどれかの隣は最大値より小さいので、可能（最大値がとなりを食べれば最大値+1となり唯一の最大値となる）。

D. Districts Connection

全部が等しいと無理。
そうでないなら可能。
所属が違うグループを1つずつ直線で結び、残りを所属が違うグループに繋げば良い。

f:id:bqn2:20201022111117p:plain

E. Two Round Dances

N個からは半分（ $\frac {N}{2}$ ）を選ぶ方法aを $_N C _\frac{n}{2}$
右と左の2つにグループ分けする場合、左右で重複するので2で割る。
円環に並べる方法bを、先頭を固定して順列を数えればよいので、 $(\frac{N}{2}-1)!$
2つの円環は独立なので組み合わせは $b \times b$
よって求める答えは、 $\frac{a}{2} \times b \times b = \frac {_N C _\frac{n}{2}}{2} \times ((\frac{N}{2}-1)!)^2$

F. Zero Remainder Sum

行と列で2回DPをする
行については、 $\frac{M}{2}$ 個まで使ったときのKで割った余りでグループ分けした和の最大値をつくる。
列については、各行でどれを選ぶか（あるいは選ばないか）で、Kで割った余りでグループ分けした和の最大値をつくる。
結果の余りが0（Kで割り切れる）が答え。

解法。
行についてのDPは、
dp1[n][m][i][k] = n行目について、「m列目まで見て、i個選んだときの、和をKで割った余りkでの和の最大値」とする（行ごとに処理するのでdp[n]はたんにn行目についての処理という意味。 n+1への遷移みたいに考えない）。
また列について、dp2[i][k] = i行目までみて、和をKで割った余りがkのときの和の最大値、とする。
dp2の遷移にdp1を利用する。

for j in 0..M/2 {
    for r in dp1[i][M][j] {
        for k in 0..K{
            dp2[i+1][k] =  chmax(dp2[i][k])  //使わないとき  
            let s = dp2[i][k] + r  
            dp2[i+1][s%K] =  chmax(dp2[i][k]+s)  //使うとき  
        }
    }
}

$O(70^4) = O(10^7)$
で間に合う。

G. Reducing Delivery Cost

全点間最短距離を求める、ワーシャルフロイドでは間に合わない（ $O(N^3)$ ）。
各ルート(a to b）にたいして、削除する辺（(u,v)）をすべて試す。
始点をa、始点をbとして2つのダイクストラを行って、最短距離を、
min(dist(a,b) , dist(a,v)+dist(b,u) , dist(a,u)+dist(b,v))とする。
（aからuへの最短距離とuからaへの最短距離は等しいことを利用）
削除する辺にたいして、最小値が求める答え。

ダイクストラに $O( (n+m) \log n)$
各ルートにたいして、削除する辺を試すので $O(mk)$
よって $O(mk( (n+m) \log n))$
m,n,kがそれぞれ1000以下なので間に合う。