競プロがんばりたい

ABC186 (Panasonicコン)

コンテスト参加

結果

A $01:03$

B $03:33$

C $06:57$

D $15:30$

ノーペナ $4$ 完でパフォは $1250$ ，rating変動は $+59$ で $762 \to 821$ でした．

考察

A問題

$N$ という大きさに $W$ がいくつ入るかなので，シンプルに $N/W$ でOK

B問題

操作としては取り除くだけで追加はできないので，最小値に合わせて多いやつを取り除きます．

まず $A [ ] [ ]$ の最小値minを求め，各 $A[i][j]$ をminまで減らすのに何回取り除くかの合計を計算します．

計算量は $O(HW)$ でした．

C問題

$n$ を $1$ から $N$ まで動かして全探索です．

$n$ を $10$ で割った余りは $7$ か？ $\to n$ を $10$ で割る $\to n$ を $10$ で割った余りは $7$ か？ $\to n$ を $10$ で割る $\to ...$

というのを $n$ が正の間繰り返せばいいかんじに桁をずらせて， $10$ 進数のときは処理できます．

$8$ 進数でも同じで，上の処理で $10$ を $8$ にすればOK．

$O(N)$ で解けます．

D問題

サンプル $2$ で考えてみます．

まずは配列をソートしておくと

$A[] = \{ 26, 31, 41, 53, 59 \}$

で，答えを計算すると

$(59-53) + (59-41) + (59-31) + (59-26)$

$+ (53-41) + (53-31) + (53-26)$

$+ (41-31) + (41-26)$

$+ (31-26)$

です．

ここで，それぞれの行は

$A[i] \times i - (A[0]$ から $A[i-1])$ までの和

になっていることがわかります．

例えば $1$ 行目は，

$59 \times 4 - (26 + 31 + 41 + 53) = A[4] \times 4 - (A[0] + A[1] + A[2] + A[3] )$

よって，累積和などで $i$ 番目までの $A[ ]$ の和を事前に計算しておき， $1 \leq i \leq N-1$ の $i$ について上の式を加算していったものが答えで， $O(N)$ で計算できました．

感想

年内最後のABCでしたね．

今年の締めくくりに過去最高パフォで，さらに緑コーダーに戻れ，ratingもHighestでした．

良い終わり方ができました．

自分はコンテストおさめになりそうです．