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

hamayanhamayan's blog

ダンジョン [パソコン甲子園2017 予選 H]

https://onlinejudge.u-aizu.ac.jp/problems/0364

考察過程

1. 一掃できる敵は、移動後の最大列xmax、最大行ymaxとすると、x≦xmax,または,y≦ymaxを満たす座標(x,y)にいる敵
2. これを考えると上や左に移動するのは無駄なので考えない
3. 加えて、右に何回移動したか、下に何回移動したかだけが重要で順番は関係ないと分かる
4. なにか全探索できるものが無いか考える
5. 右への移動量を全探索すると、下への移動量は一意に定まりそう
6. 右へx座標まで移動したと考えると、下への移動量は[x+1,W)にいる敵のy座標の最大値であると言える
7. これは累積和のように事前計算できるので、解けた

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0364/review/3136635/hamayanhamayan/C++14

累積和のようにy座標の最大値を求めよう。
まずは、これを求める。
maxh[x] := x座標がxである敵のy座標の最大値
次に、これを累積和のようにして以下のように変形する。
maxh[x] := x座標が[x,W)である敵のy座標の最大値
 
答えを求めるために、右への移動量を全探索する。
x座標がxまで右に移動すると、下への移動量はmaxh[x+1]となる。
よって、x+maxh[x+1]が必要なコストとなる。
この最小値が答え。

int W, H, N;
int maxh[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> H >> N;

    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        chmax(maxh[x], y);
    }
    rrep(x, W - 2, 0) chmax(maxh[x], maxh[x + 1]);

    int ans = inf;
    rep(x, 0, W) chmin(ans, x + maxh[x + 1]);
    cout << ans << endl;
}