【「『JOI 2011年春合宿 Day1 の問題『Dragon』は強実装』はウソ」はウソ】はウソ

http://tozangezan.hatenablog.com/entry/2013/03/29/004026

upper_bound や lower_bound を使いまくったり， -1, -2 を乱発したりしない Dragon の実装が求められているそうなので書きました．

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

typedef long long Int;

int H, W, N;

struct dragon {
    int x, y;
} D[100050];
bool cmpx(const dragon& a, const dragon& b)
{
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}
bool cmpy(const dragon& a, const dragon& b)
{
    return a.y != b.y ? a.y < b.y : a.x < b.x;
}

struct event {
    int x, y;
    bool query;
    event(int x, int y, bool q) : x(x), y(y), query(q) { }
};
bool operator < (const event& e, const event& f)
{
    return e.y < f.y;
}

int solve()
{
    int res = 0;

    vector<int> xr, yd;
    for (int i = 0; i < N; ++i) {
        xr.push_back(D[i].x);
        yd.push_back(D[i].y);
    }
    sort(xr.begin(), xr.end());
    sort(yd.begin(), yd.end());
    xr.erase(unique(xr.begin(), xr.end()), xr.end());
    yd.erase(unique(yd.begin(), yd.end()), yd.end());

    vector<event> es;

    sort(D, D + N, cmpx);
    for (int i = 0, j; i < N; i = j) {
        for (j = i; j < N && D[i].x == D[j].x; ++j) ;
        es.push_back(event(D[j - 1].x, D[j - 1].y, false));
    }

    sort(D, D + N, cmpy);
    for (int i = 0, j; i < N; i = j) {
        for (j = i; j < N && D[i].y == D[j].y; ++j) ;
        es.push_back(event(D[j - 1].x, D[j - 1].y, true));
    }

    sort(es.begin(), es.end());
    set<int> xs;

    for (int i = 0; i < (int)es.size(); ++i) {
        if (es[i].query) {
            int rr, dd;
            dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y);

            set<int>::iterator it = xs.upper_bound(es[i].x);
            if (it != xs.end()) {
                rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it);
                res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd);
            }

            rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1);
            res = max(res, W - (es[i].x + 1) - 1 - rr);
        } else {
            xs.insert(es[i].x);
        }
    }

    return res;
}

int main()
{
    cin >> H >> W >> N;
    for (int i = 0; i < N; ++i) {
        cin >> D[i].y >> D[i].x;
        --D[i].x; --D[i].y;
    }

    set<int> xs, ys;
    for (int i = 0; i < N; ++i) {
        xs.insert(D[i].x);
        ys.insert(D[i].y);
    }

    Int sol = (Int)H * W - (Int)H * xs.size() - (Int)W * ys.size() + (Int)xs.size() * ys.size();
    int M = 0;

    for (int rot = 0; rot < 4; ++rot) {
        for (int flip = 0; flip < 2; ++flip) {
            M = max(M, solve());
            for (int i = 0; i < N; ++i) {
                D[i].y = H - D[i].y - 1;
            }
        }
        swap(H, W);
        for (int i = 0; i < N; ++i) {
            int x = D[i].x, y = D[i].y;
            D[i].x = y;
            D[i].y = H - x - 1;
        }
    }

    cout << sol + M << endl;

    return 0;
}

例によって main は回転などをしているだけ，solve も大半は座標圧縮などの造作も無い処理です．問題の箇所がこちら．

int rr, dd;
dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y);

set<int>::iterator it = xs.upper_bound(es[i].x);
if (it != xs.end()) {
    rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it);
    res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd);
}

rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1);
res = max(res, W - (es[i].x + 1) - 1 - rr);

upper_bound のみ 4 回使用，いずれも単純な呼び出しにとどまっていると思います．また +1, -1 などについては

res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd);

これは逆順に走査するときなどによく見る N - i - 1 の形です．また

rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1);

こちらはドラゴンのいる x 座標(es[i].x) の隣に M 理事長が居る場合を考えるので +1 をつけています．そして

res = max(res, W - (es[i].x + 1) - 1 - rr);

これは上ふたつの複合です．

少なくとも「人が死ぬレベル」「複雑すぎる」といった形容は必要ない程度にはシンプルにまとまったと思います．

「強実装は多実装ではありません。『手ごわい』実装なのです。」という理解は正しいと思います．「強実装」という概念には単に記述量が多いだけでなく，正しく書きづらい，複雑な記述になってしまう，デバッグ時に動作を追いづらいなどの要素が含まれているでしょう．

さて，ぼくはこの問題を解くのは 3 度目ですが，この問題はとても良い問題だと思います．そして，決して簡単な問題ではないとも思います．しかし，「強実装である」という点に関してだけはそうではないと思います．

この問題の良い点，そして同時に難しい点というのは「解法の詰め方」と「適切な実装方法の選択」であります．この問題の解法自体がそこまで難しいかといえば，少なくともJOI春合宿で出題された問題の中ではそうでもないでしょう．では実装が難しいのかといえば，それも難しいとは限らない(少なくとも今回載せた実装はそこまで難しいわけではない)のがポイントです．

「他の人のソースコードを見ても、このような1や2といった数字が多数混在しています。」とあることからも分かるように，多くの人は(そしてぼくも初めて解いたときには)複雑怪奇，とても人間のデバッグするようなものではないソースを書いてしまうようです．これはこの問題が決して簡単ではないことを示しているでしょう．

今回載せた実装を最初から書くことができれば，この問題は難しいものではありません．しかし，その実装方法を選択すること，あるいはその実装方法へ至るまで正しく解法を詰められるかということ，これはとても難しいと思います．事実，ぼくも 2 度目に解いたときに比べ，さらによい実装方法を選択することができました．

パッとでてきた解法ですぐに勝負すると大変になってしまうことこそ多いが，じっくり解法を詰め，できるだけシンプルで書きやすくてバグを埋め込みにくくて動作を追いやすい，という実装方法へ至ることでスッと解けてしまう．そんな問題がぼくはとても好きであり，その点を見事に体現しているこの Dragon という問題は解くたびに新たな発見のある，非常に楽しくて良い問題なのだと，またひとつ確信させて頂きました．