結構好き！ソートすることが本質の問題としていい感じな気がする。

問題概要

下図のような「中央の通路とそこから横に伸びた乗り物に乗客がどこにいるかを表した地図」が与えられる。乗客は $p$ 人いる。各乗客は 1 秒かけて 1 マス移動できる。ただし、

中央の通路以外は横にしか移動できない
他の乗客のいるマスには移動できない

全員が外に出られるまでの最小回数を求めよ。

考えたこと

一見大変そう。同じマスに次ステップで複数の乗客が移動したい状況になったときに、どの乗客を優先したらいいのか。。。

とりあえず、「移動待機」はあまり考えたくないので、各乗客は最初に移動を始めるまでスタート地点で待機するものとして考えるものとする。そして一度移動を始めたら、もうゴールまで真っしぐらに移動するものとする。

そして重要な考察として

ゴールするタイミングが異なる乗客間で、同じタイミングで同じマスへ移動したくなるような状況は生じ得ない

というのがわかる。よって、各乗客につき

一度スタートしたら何ステップでゴールへ行けるか

を求めておいて、それが大きい人から優先的にゴールへ行ってもらい、

その次の人はその人のちょうど 1 秒後にゴールへ着くように待機して出発
さらにその次の人はそのちょうど 1 秒後にゴールへ着くように待機して出発
...

としていけばいい。計算時間はソートに要する $O(p \log{p})$ 。

他の考え方: 操作を逆順に見る

他のもっと考えやすい見方として、操作を逆順に見るのがしばしば有効な気がする。

今回も

外にいる乗客が順番に中へと入って行って、全員が配置につくまでにかかる時間を最小にする

という問題と読み替えても同じであることに気がつく。そうすると

各乗客が入場してから配置にかかる時間を求め
それが大きい人から順番に入っていく

というのがとても自然に導かれる。そしてそれは、上の解法とちゃんと一致する。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int r, s, p; cin >> r >> s >> p;
    vector<int> nums;
    for (int _ = 0; _ < p; ++_) {
        int i, j; cin >> i >> j; --i, --j;
        if (j >= s) ++j;
        nums.push_back(abs(i - r) + abs(j - s));
    }
    sort(nums.begin(), nums.end(), greater<int>());
    int res = 0;
    for (int i = 0; i < p; ++i) res = max(res, nums[i] + i);
    cout << res << endl;
}