Hatena::ブログ(Diary)

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

2012-03-14

[]受験記

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

時系列

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

2011-09-20

[]問題の行方

問題ができるとだいたいは次のような感じになる。

  • if 問題がすごく面白い or 形式が特殊 then IJPC用にする
  • else if N<=50 ぐらいで通用しそう then TopCoder用にする
  • else if 問題は面白いが N>50 が必要 then Codeforces用にする
  • else てきとうに放出する

まあ、だいたいです。だいたい。

2011-07-23

[][]IOI 2011 Day 2

  • Day 1 夜
  • 寝るはずがIOI過去問を読んだりしていて遅くなる
  • 死ぬように眠りについた
  • Day 2 朝
  • なんとか起床するが眠すぎて死ぬ
  • 目を覚ますために合成数を切断して素数を叩くゲームをやる
  • とりあえずがんばって朝ごはんを食べにいく
  • 朝ごはんはバイキングのようなアレだった
  • ハム類が豊富に用意されていたのですべて2つずつとったら皿がハムだけになった
  • ごはんは美味しいけどホテルのメシっぽい感じが漂っていた
  • タイ料理を食べてみたい
  • 9時からは開会式
  • よく寝ました(ごめんなさい)
  • ほんとうにずっと寝ていた気がするので内容をあまり覚えていない
  • 人が何かのオーラをまとったり,よくわからないものと戦闘を繰り広げているあたりで目が覚めた
  • 国紹介のときには眠気がすっかり飛んでいたので大きく手をふっておいた
  • おひるごはん
  • チキンの入ったカレーのような何かがタイっぽくて嬉しかった
  • デザートにアイスクリームがあったが,苺味がなかったので女子力は上がらなかった
  • ひとつのカップにチョコとバニラのアイスを両方入れてくれと言っている人がいた
  • ふつうにうまかった
  • その後は Practice Session
  • 所持品に関する規定がなんか厳しくなっているようで困惑する
  • とりあえず上から羽織れるものと筆記用具を預けた
  • Practiceは特にやることもなかった
  • ひと通り問題を解いたあとパソコンの画面いっぱいに「/\_/\」と表示しておいた
  • ところ,ドイツの人にいじられて「<(^-^)>」こういうものになっていた(日本の顔文字が好きらしい)
  • ので,さらにいじって「\(^o^)/」に変えた
  • そしてそのドイツの人と「\(^o^)/」このポーズで一緒に写真を撮った
  • さらにその後で「/\_/\ < fox!」としておいた
  • ところ,ドイツの人に free the fish というGNOMEイースター・エッグを走らされた
  • 小さな魚が画面に現れて「/\_/\ < fox!」を横断していくシュールな光景が繰り広げられた
  • Practice後はFree Time
  • このFree Timeが終わるあたりで選手とリーダーたちの接触が禁止される時間がくる
  • ので,インターネットもできなくなる(できるかもしれないがやらないことが推奨される)
  • そうすると死んでしまうので,その前にネカフェに来る
  • そこでblogなどを書く

2011-07-22

[][]IOI 2011 Day 1

  • 成田
  • 朝 qnighy に起こされるが起きない
  • ホテルで朝ごはんを食べる
  • 昨夜インターネットがないという事態だったのでロビーでつかの間のインターネットを楽しむ
  • 朝なので人があまりいなかった
  • 空港へ行く
  • 両替弱者だったのでいそいで両替をする
  • 女子力をあげるためにとちおとめのアイスクリームを imos と食べる
  • 人が無限に並んでいる列の最後尾に並ぶ
  • 出国審査はさすがに余裕で Passed System Test
  • 飛行機に乗る
  • iPadのPrimeSmash(合成数を切断して素数を集めるゲーム)をやりまくる
  • 座席についてるゲームでテトリスをやるが操作性が悪すぎて死ぬ
  • 寝る
  • PrimeSmashで人権を得られるレベルの得点を頑張ってとる
  • バンコクにつく
  • IOI最難問入国審査に怯える
  • 去年は見事に引っかかってなぜか移民扱いされたらしいのでトラウマ
  • 今年は ome さんが引っかかってくれるに違いないとフラグをたてまくる
  • が,タイの入国審査はサイレント入国審査だった(まったく質問されなかった)
  • ので Passed System Test
  • バスでパタヤに向かう
  • ヤシの木がてきとーに生え続けているような風景が無限に続く
  • 寝て起きると街のようになっていた
  • 気がつくとリゾート感まるだしのホテルに到着
  • はやくごはんがたべたかった
  • インターネットもそこそこに切り上げる(予定)
  • 部屋に戻る(予定)
  • 明日の朝はとても早いようなのでおとなしく寝る(予定)