AtCoder Beginner Contest 004 D - マーブル

問題

abc004.contest.atcoder.jp

解法

よく考えたら最小費用流解が何も考えず出来て頭良いですが, 普通に解きました。

まず考察ですが, 赤, 緑, 青のマーブルはそれぞれ連続に置くのが明らかに得です。
「緑のマーブルの左端をどこにするか」というのを決めると, 緑色のマーブルは左端 g から, 区間 [g, g+G) に置かれることになります。これで緑色のマーブルを動かす回数は確定します。

赤, 青のマーブルについては, 同じようなアルゴリズムで回数がわかります。赤についてだけ書きます。

赤のマーブルは, g <= -100 の時, すべて左側に移動させなければなりません。この場合は, 単純に [g-G-R+1, g-G] にマーブルを並べていけば良いです。
そうでない場合は, なるべく左右に広げながら並べるのが最適です。lp = (現在の左端), rp = (現在の右端)というのを交互に動かしながら置く範囲を広げていけば良いです。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int R, G, B;
    cin >> R >> G >> B;
    ll ans = 1ll<<55;
    for (int g = -300; g <= 300; g++) {
        ll tmp = 0;
        for (int i = g; i < g+G; i++) tmp += abs(i);
        // R
        if (g <= -100) {
            for (int i = g-1; i >= g-R; i--) tmp += abs(i+100);
        } else {
            int lp = -100, rp = -99;
            for (int i = 0; i < R; i++) {
                if (i%2 && rp < g) tmp += abs(rp+100), rp++;
                else tmp += abs(lp+100), lp--;
            }
        }
        // B
        if (g+G >= 100) {
            for (int i = g+G; i < g+G+B; i++) tmp += abs(i-100);
        } else {
            int lp = 99, rp = 100;
            for (int i = 0; i < B; i++) {
                if (i%2 && lp >= g+G) tmp += abs(lp-100), lp--;
                else tmp += abs(rp-100), rp++;
            }
        }
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}