2012-03-14

受験記

Diary

東京大学理科一類を受験しました

時系列

2011/7

IOI楽しいナ〜

2011/8上

堕落

2011/8下

しょうがないので倫理をやる

2011/9

センター模試で化学6割とか物理7割とかとる

2011/10

まだ n ヶ月あるしどうとでもなるでしょ……

2011/11

倫理すっかり忘れてしまった

2011/12上

あれ，これ実はやばいのでは？

2011/12下

学校が企画した冬季勉強合宿みたいなのへ行く

センター形式の問題で化学6割とかとる

2012/1上

家でゆっくり理科のセンター過去問をやる

化学7割とかとる

センター試験

神が降りてきて848/900点とる

2012/1下

まだ1ヶ月ぐらいあるしどうとでもなるでしょ……

2012/2上

堕落

GCJJオフ会楽しかったナ〜

2012/2中(2次試験2週間前ぐらい)

あれ，これ実はやばいのでは？

2012/2中(2次試験1週間前ぐらい)

過去問をやる

数学何回やっても4完できないし理科は物理で100分以上使う

2次試験

数学4完できないし理科は物理で100分以上使う

(練習でできなかったことが本番で出来るわけないという当たり前のことを実感する)

2012/2下

IIDXやりたい

2012/3上

卒業式めんどくさい

2012/3/10(合格発表)

受かっていた

今では立派な受験余裕でした勢です

今

SP1級受かったよ〜

感想

直前の対策でなんとかなりすぎだと思う．

僕が言えたことではないけど，もうちょっと直前の対策だけではどうにもならないような入試問題にするべきなのでは……．

それはいいとして，僕が受験成功したのは本当に神のおかげなのではないだろうか．「神はいると思いますか？」「僕についています」みたいな感じだった．

ところで今回の受験で悔やむところはふたつほどあって，ひとつは僕がダメすぎるということ．頭では分かっているのに堕落しすぎだし，ちゃんと勉強してれば本物の受験余裕勢にもなれただろうに．

もうひとつは合格してしまったので，IOI日本代表は受験に失敗しないという悪しき風習を破ることができなかったこと．誰か，受験に成功しつつこの悪習を打ち破る方法を考えて実践してほしい．

まあ，最終的な感想として一切反省していないようなことを言うけど，終わりよければ全てよしですよネ．

今後

IIDX頑張ります！！！！！！！！

あとICPCも頑張ります．

2012-02-14

「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;
}