AtCoder Regular Contest 101
Updated:
Source codes
Solutions
C - Candles
正の方向に歩いていく、負の方向に歩いていく、正の方向に歩いていった後負の方向に戻って負の方向に歩いていく、負の方向に歩いていった後正の方向に戻って正の方向に歩いていく、のいずれかが答えになる。これらを全探索する。
vector<ll> V[2]; とし、 $x_i > 0$ ならば $V[0]$ に入れる。 $x_i < 0$ ならば $V[1]$ に入れる。 $x_i = 0$ ならば K--; とする。 sort する。 $K = 0$ ならば答えは $0$ である。他は $V[0][K - 1]$, $V[1][K - 1]$, または $i = 1, \dots, K - 1$ に対し $V[0][i - 1] + 2 V[1][K - i - 1]$ または $2 V[0][i - 1] + V[1][K - i - 1]$ のうち一番小さいのが答え。
ポイント
実装が遅いので素早くはできなかった。
D - Median of Medians
コンテスト中に考えたこと
- 座標圧縮して良い。
- 各数字に対して、その値を中央値にするようなペアリングの数を高速に計算できればクリア。
あとわからん。