はまやんはまやんはまやん

hamayanhamayan's blog

Traveler [AtCoder Beginner Contest 197（Sponsored by Panasonic） E]

競技プログラミング

https://atcoder.jp/contests/abc197/tasks/abc197_e

解説

https://atcoder.jp/contests/abc197/submissions/21324848

貪欲法で解く。

回収順

ボールは色が広義単調増加となるように回収する必要があるので、
同じ色のボールについては回収順番はどうなるかは分からないが、違う色については順番は確定することになる。
つまり、考えるべきは

  • 同じ色のボールの回収順番をどう最適化していくか
  • どのように次の色への動作を準備するか

の2点となる。
よって、前処理として、色毎にボールの座標を集めておき、色が小さい順に評価していくことにする。

同じ色のボールの回収順番

例えば、1 2 3 4の場所に同じ色のボールがある場合を考えよう。
この時に、色んなパターンを考えてみる

  • -1にいる場合は、右端の4まで進んでいってその過程で全部取るのが最適になる
  • 5にいる場合は、左端の1まで進んでいってその過程で全部取るのが最適になる

これはいいとして、内部にいる場合はどうだろうか

  • 2にいる場合は、左端の1まで進んでいってその過程で取れるものを取って、次に右端の4まで進んでいってその過程で残りを取るのが最適になる

このような考察から抽出できることとしては、「回収時に折り返すのは1回にするのがいい」「回収完了時には左端か右端にいる」である。
特に後者が重要で、回収完了時には左端か右端にいるのが最適であり、どちらにいるのがいいかは、その直後の回収によって変化する。

どのように次の色への動作を準備するか

同色の場合の最適動作は何となくつかめたので、違う色でも考える。
同色の場合の終了位置は左端か右端の2択になるので、その2択の状態が前の色から与えられると考えて次の色の動作をシミュレートしていく。

…つまり？

同色毎に右端で終了する最適動作と左端で終了する最適動作を評価して、それを使って次の色の同様の評価を行っていく。
具体的には次のような情報を色間で伝搬させながら貪欲法を行っていく。

  • L: 左端の位置
  • Lcst: 左端にいるときの移動距離の最小値
  • R: 右端の位置
  • Rcst: 右端にいるときの移動距離の最小値

各色について次のL,Rについては確定するので、それをL2,R2とすると、最適動作は以下の4種類となる。
これを評価して、次のL, Lcst, R, Rcstを決める。

  • L -> R2 -> L2
  • L -> L2 -> R2
  • R -> R2 -> L2
  • R -> L2 -> R2

あとはこれが本当に最適な貪欲法であることを祈りながら実装して提出すると通る。

int N, X[201010], C[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i] >> C[i];

    map<int, vector<int>> ma;
    rep(i, 0, N) ma[C[i]].push_back(X[i]);

    int L = 0, R = 0;
    ll Lcst = 0, Rcst = 0;
    fore(p, ma) {
        int mi = inf, ma = -inf;
        fore(x, p.second) {
            chmin(mi, x);
            chmax(ma, x);
        }

        int L2 = mi, R2 = ma;
        ll Lcst2 = infl, Rcst2 = infl;

        // L -> L2 -> R2
        chmin(Rcst2, Lcst + abs(L - L2) + abs(L2 - R2));

        // L -> R2 -> L2
        chmin(Lcst2, Lcst + abs(L - R2) + abs(R2 - L2));

        // R -> L2 -> R2
        chmin(Rcst2, Rcst + abs(R - L2) + abs(L2 - R2));

        // R -> R2 -> L2
        chmin(Lcst2, Rcst + abs(R - R2) + abs(R2 - L2));

        L = L2, R = R2, Lcst = Lcst2, Rcst = Rcst2;
    }

    ll ans = min(Lcst + abs(L), Rcst + abs(R));
    cout << ans << endl;
}