AtCoder Regular Contest 101

Updated:

AtCoder Regular Contest 101

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

コンテスト中に考えたこと

  • 座標圧縮して良い。
  • 各数字に対して、その値を中央値にするようなペアリングの数を高速に計算できればクリア。

あとわからん。

ポイント

E - Ribbons on Tree

ポイント

F - Robots and Exits

ポイント

Others