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

JOI Algorithm

昨年のJOI合宿のDay 1では3問の問題が出題されました．

http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf

一問目の Banner は易しいもので，三問目の Joitter は若干の思考ととコーナーケースに引っかからない注意深さが求められるものでした．

二問目として出題された Dragon という問題ですが，JOIerたちは口を揃えて「強実装」「ひたすら実装」と言います．

確かに参加した当時は，かなりひどいソースをぐだぐだと書いた記憶があります(さすがにバグを混入させてしまい90点でした)．

でも今思うと，JOIでひたすら強実装するだけの問題が出るのでしょうか？(過去の実装するだけの例として a+b がありますが，まああれもそこまで強実装というわけではないです)

というわけで，約1年越しで Dragon を再び解いてみました．

#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

typedef long long ll;

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

int H, W, N;

int solve()
{
  int res = 0;

  map<int, int> maxy, lessx, largex, largey;
  for(int i=0; i<N; ++i)
    maxy[D[i].x] = D[i].y;

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

  for(int i=0; i<(int)xs.size(); ++i)
    lessx[xs[i]] = i, largex[xs[i]] = (int)xs.size()-i-1;
  for(int i=0; i<(int)ys.size(); ++i)
    largey[ys[i]] = (int)ys.size()-i-1;

  set<int> done;
  for(int i=0, j; i<N; ) {
    for(j=i; j<N && D[i].y==D[j].y; ++j) ;

    set<int>::iterator left, right;
    left = done.lower_bound(D[i].x);
    right = done.upper_bound(D[j-1].x);
    if(left != done.begin()) {
      left--;
      res = max(res, *left + (H-D[i].y-1) - lessx[*left] - largey[D[i].y]);
    }
    if(right != done.end())
      res = max(res, (W-*right-1) + (H-D[i].y-1) - largex[*right] - largey[D[i].y]);
    res = max(res, max(D[i].x-1 - lessx[D[i].x], W-D[j-1].x-2 - largex[D[j-1].x]));

    for(; i<j; ++i)
      if(maxy[D[i].x] == D[i].y)
	done.insert(D[i].x);
  }

  return res;
}

int main()
{
  scanf("%d%d%d", &W, &H, &N);
  for(int i=0; i<N; ++i)
    scanf("%d%d", &D[i].x, &D[i].y), D[i].x--, D[i].y--;

  set<int> X, Y;
  for(int i=0; i<N; ++i)
    X.insert(D[i].x), Y.insert(D[i].y);

  ll S = (ll)H*W - (ll)H*X.size() - (ll)W*Y.size() + (ll)X.size()*Y.size();
  int M = 0;

  sort(D, D+N);
  M = max(M, solve());

  for(int i=0; i<N; ++i) D[i].y = H-D[i].y-1;
  sort(D, D+N);
  M = max(M, solve());

  swap(H, W);
  for(int i=0; i<N; ++i) swap(D[i].x, D[i].y);
  sort(D, D+N);
  M = max(M, solve());

  for(int i=0; i<N; ++i) D[i].y = H-D[i].y-1;
  sort(D, D+N);
  M = max(M, solve());

  printf("%lld\n", S+M);
  return 0;
}

94行あります．94行という時点で，とても強実装とは言えないと思います．

さらに見ればわかりますが，main 関数はドラゴンたちの位置を回転させて solve を呼んでいるだけです．

さらにさらにその solve の中でも，40行目(doneの宣言)から58行目(その後のforループが終わるまで)が本質であり，それ以外の部分は座標圧縮に近い作業をしているだけです．

したがって，「JOI 2011年春合宿 Day1 の問題『Dragon』は強実装」は真っ赤なウソです．

むしろ，「JOI 2011年春合宿 Day1 の問題『Dragon』は強実装」だと主張することは，実装力が足りていないことの証左です．JOIerの方々はよりよい実装が出来るよう向上を心がけましょう．