Hatena::ブログ(Diary)

TopCoderとJ言語と時々F# このページをアンテナに追加 RSSフィード

2012-02-14

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

昨年の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の方々はよりよい実装が出来るよう向上を心がけましょう.

2009-03-11

[] TopCoder SRM 436 Div2

f:id:JAPLJ:20090311230439p:image

まあいいだろう。Hardは解法分かってたんだけど、BigIntegerゲーで時間足りなくなった。

Room内1位、Division内33位で 10941210

Div1復帰だよ!

250 FriendScore

ソーシャルネットワークで一番人気ある人を決めたい。そこで、互いに友達である人の数と、間接的に友達(AとCが友達で、BとCが友達のときの、AとB)である人の数を合計して一番多い人が人気があるものとする。一番多い人は何人その関係の人がいるか。

やるだけ。

500 BestView

高層ビルが連続で建ってて、i個目のビルを(i, 0)-(i, 高さ)の線分とみなす。あるビルAからあるビルBが見える条件は、AとBの屋根を結んだ線分がどのビルとも触れず、交わらないことである。一番多くのビルを見ることができる場合、いくつのビルを見ることができるか。

AとBの屋根を結んだ直線の傾きを計算して、交差してるかチェックするだけ。

1000 DigitsSwap

ある数x, yが文字列形式で与えられる。任意のiについてx[i]とy[i]を交換する作業をちょうどswaps回行って、結果のx, yの積が最大になるようにしたとき、その積を求めよ。

できるだけ積が最大になるように交換を繰り返す。swaps回行っても最大の積にたどり着けない場合は途中のまま、その積を返す。swaps回行う前に最大の積にたどり着いた場合は、残り回数が偶数ならば最大の積を返し、奇数ならば影響の少ない1の位を入れ替えてその積を返す。

解法はこれで合ってる(と思う)けど、積がでかいので多倍長演算が必要。C#になかったので焦って時間なくなった。