2013-03-10

受験記

東京大学理科 I 類に合格しました

はじめに

東大模試で偏差値 80 あればまず落ちません

模試について

模試をほとんど受けない人もいますが、少しは受けておいたほうが自分の実力がわかってよいかもしれません。東進のセンター、東大同日、東大本番レベル 1 個、iPad 模試と駿台の東大実戦を受けました
センター形式に自信がある人は iPad 模試（東進の高校生テスト）を受けるとよいかもしれません、無料で受けられて上位者は iPad ももらえてうれしい試験です（今年も iPad 配布するのかは不明）。但し勧誘には気をつけましょう

勉強法

国語

センターまでは、過去問や模擬問題を大量に解いたり古文単語を覚えたりした。
センター後は若干ネット上に掲載されている過去問（古文漢文のみ）をやった程度。

数学

適当に問題を解いた。ネット上に東大の過去問を大量に載せているところや国公立の理系数学を大量に載せているところがあったので解いた。ただし本番形式の練習はまったくしなかった。少しはやっておくべきだった感。簡単な問題でも焦ると全然解けなくなることがあるので（本番の [2] がかなりそれに近かった）

理科

物理は適当に問題を解く。化学は最初あまりできなかったので「新演習」をやったら夏の駿台の化学が高 2 模試になった
その後は、25 ヵ年を解きまくった。最終的にはほとんど解いてしまった

社会（倫理政経

黄色い本（点数が面白いほどとれる本）を読んで、過去問や模擬問題をたくさん解いた。本番難化しててかなり焦ったが思ったよりとれてた

英語

英語ははじめ全然できなかったのでとりあえず鉄壁を覚えた。
その後は適当に本を読んだりしたらけっこう上がった。
リスニングは学校の先生の勧めで 7 時の NHK ニュースを英語で聴くようにしたらかなり上がった気がする（同日リスニング 10 点→本番リスニング自己採点 26 点）

2013-03-08

TopCoder SRM475 Div1Hard

Algorithm TopCoder

問題

うさぎがプログラミングコンテストに参加した。コンテストはいくつかの問題からなり、そのうちいくつかは採点され全うさぎについての正誤が判明しているが、それ以外の問題についてはまだどのうさぎの正誤も判明していない。
このコンテストの上位 qualified 匹を選び（同点のときは番号の早い順）、そのうち selected 匹を代表チームに選ぶ。チームの組み合わせは何通り考えられるか求めよ。

解法

各うさぎについて、得られる最低得点と最高得点がわかるのでまず求める。同点の場合の処理は、得点を 50 倍くらいして、番号の早い順に 49, 48, … と足してやるとよい。
ある組み合わせがチームとして有りうるかを考えたとき、そのチームのうさぎは全て最高得点、他のうさぎは全て最低得点であったとしてよい。
そこで、うさぎを最高得点の昇順にソートする。あるうさぎが最も低い得点で代表になったうさぎだとするとき、他のうさぎは次の 3 通りに分類できる。

どうやっても最低点うさぎより点数が高くならないうさぎ
絶対に最低点うさぎより点数が高くなるうさぎ
最低点うさぎより点数が高くなったり高くならなかったりするうさぎ

1. は考える必要はない。2. と 3. から合わせて selected-1 匹のうさぎを選ぶ必要がある。2. と 3. について選ぶ数を固定したとき、何通りのチームができるかはすぐに分かる。但し、上位 qualified 匹中 qualified-selected 匹しか 2. からは除外できないので、これを満たさないときはチームは作れない。
以上のことをすべてのうさぎを最低点うさぎとして考えて組み合わせを求めればよい。

コード

#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long i64;

class RabbitProgramming
{
	int N;
	vector<pair<int, int> > P;
	i64 C[51][51];
public:
	i64 getTeams(vector<int> pt, vector<string> stand, int Q, int S)
	{
		for(int i=1;i<=50;i++) C[0][i] = 0; C[0][0] = 1;
		for(int i=1;i<=50;i++){
			C[i][0] = 1;
			for(int j=1;j<=50;j++) C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
		
		N = stand.size();
		
		for(int i=0;i<N;i++){
			//pMin[i] = 0; pMax[i] = 0;
			int mn=0, mx=0;
			for(int j=0;j<pt.size();j++) if(stand[i][j]=='Y'){
				if(pt[j]>0){ mn += pt[j]; mx += pt[j]; }
				else mx -= pt[j];
			}
			P.push_back(make_pair(mx*50+49-i, mn*50+49-i));
		}
		
		sort(P.begin(), P.end());
		
		i64 ret = 0;
		for(int i=0;i<N;i++){
			printf("%d, %d\n", P[i].first, P[i].second);
			int alSelect = 0, maySelect = 0;
			for(int j=0;j<N;j++){
				if(P[j].second > P[i].first) alSelect++;
				else if(P[j].first > P[i].first) maySelect++;
			}
			
			for(int j=0;j<S;j++){
				//choose j from alSelect, (S-1-j) from maySelect
				if(Q-S < alSelect-j) continue;
				ret += C[alSelect][j] * C[maySelect][S-1-j];
			}
		}
		
		return ret;
	}
};

2013-03-06

TopCoder SRM572

Algorithm TopCoder

250

パスワードの先頭 K 文字と末尾 K 文字が一致するように、パスワードの文字を変える。できるだけ変える文字数を少なくするときその数を求めよ。

union find を使うとどことどこが等しいかわかるのでやるだけ

500

hit and blow の hit だけバージョン。質問とそれに対する答えが与えられるので答えを特定せよ。

ただの半分全列挙だったのにわからなかった…＞＜

1000

謎

結果

oxx 245.81 不参加(103 位)

rating: 2627 -> 2607

2013-03-03

TCO2013 Round1B

Algorithm TopCoder

div1 なのにやたら自明だった

250

自明

500

やるだけ

1000

長さが奇数だったら最後の文字は決して動かない。
あとは 2 文字ずつ動く（2 文字内の順番はどうでもいい）。
それぞれ可能な辞書順最小文字列に変換してからソートする。

結果

16 分で終わって眠くて challenge する気にもならなかったから寝る

ooo 1652.27(4 位)
rating: 2513->2627

2013-02-04

スリザーリンクの自動解答（続き）

http://d.hatena.ne.jp/semiexp/20100828/1283027177 とはまったく異なる手法によりスリザーリンクを解く試みをしました。

設計

前の手法と異なり、線を直接管理するようにした。

すると、基本的に「何か変更があった場所の近く」以外は新たに決まることはないから、更新を伝播させる方法が使える。すなわち、ある位置について解く関数を用意しておけば、その関数が新たに決まりうる場所について関数をさらに呼び出すことにより、高効率で解答を決定できる。背理法がない場合、関数呼び出し回数は（後述する線管理のコストを除くと）盤面の大きさの線形になり、きわめて効率が良い。実際、20*36 の問題について、前の手法によるプログラムの 90 倍近い速度を達成した。
さらに、この手法では、「解法が比較的人間に近い」というメリットがある。誰も簡単な問題に前バージョンのような「線の内外」の手法は使わないと思うが、この解法は人間が解く際の解法に近く、さらに「背理法の難易度」も評価することができるようになる。

データ構造

背理法

2 段以上の背理法が必要な問題は人間には解けないから、1 段のみとしてよい。

2013-01-19

センター試験

自己採点（東進と河合の速報に基づく）

2012-11-12

パソコン甲子園 2012 本選

Algorithm Programming

今年は Algorithm タグがつきました（後述）。

競技について

今年は分業をしました。1, 2, 3 を kitayuta が解いて、4 以降を semiexp が解くようにしました。最初のうちは 1, 2, 3 と 4 以降を交代で実装して、途中で冷えたら交代して紙デバッグするようにしました。

kitayuta が準備をしたり 1 を解いたりする間に 4, 5, 6 を眺める。4 は問題文を読むと簡単そうだけど実装つらそうなので後回し
5 はわけわからないので 6 を見たら典型自明問題なので、1 の後に解く
その後は、実装が詰まったら交代するなどを繰り返して、4, 5, 2, 7, 3 の順に AC。3 を解いてもらってる間に 8, 9, 10 を考える
最初 8 は幾何に見えたので敬遠して 9 を考える。9 は「ビット DP + 最小費用流」までわかったがけっこう実装大変そうなので保留。10 はちょっと考えた感じ無理ゲーなので放置
8 はよく考えると比較的楽な実装で解けそうとわかったので 3 が終わってから解く。事前にある程度考えたことで実装が行き当たりばったりにならず効率が上がった気がする
途中で P02 に追い越されたりして冷えるも冷静に 8 を実装して追い抜く
そのまま 9 を実装。ビット DP 書いたらあとはほぼライブラリの写経で、ライブラリは合っている設定だったので間違っていたらビット DP のデバッグに集中できた
途中で P02 と同点になる。WA 数では勝てる気がしなかったので冷えていたが 9 を実装して追い抜く
10 だけ残る。順位表見ると hogloid が通していたので無理ゲーじゃないとわかるが結局よくわからず、やけくそ（30 分前に 9 完しているチームが他にないので全完したら 1 位は確実なはずで、さらに解けなかった問題に対する WA 数は無視されるので 10 での WA の数はどうでもいいという発想）で遅いコードを送って TLE をもらう
結局わからなかったので他のチームが 9 完しないことを祈って終了

上位 3 チームは凍結地点(終了 30 分前)から点数の変動がなく、1 位だった！
今年は問題が良質で（去年は理不尽な強実装、理不尽なテストケースなどいろいろひどかった）解いていて楽しかった。難問の 8, 9 などは実装量は多かったが、単調な実装ではなく考えさせる実装で、実装が重いとは思わなかった
今年は質問票が用意され、問題について質問できるようになっていた

他

10 周年だからかわからないが普段は大学でやるレセプションがホテルで行われた。レセプションは 2 つあって、1 つめは 10 周年記念のもので食事がサンドイッチだけでふえぇ＞＜となっていたが 2 つめの参加者交流会では普通に食事が出たのでサンドイッチあまり食べなきゃよかった
パソコンを放置するのは大変危険なのでやめましょう
去年は閉会式が大遅延してて大変なことになっていたが今年は開会式も閉会式も定刻に終わった。閉会式は表彰が始まるまでが異様に長い印象があったが今年はなんとなく短かった（挨拶が普段より少なかったかもしれない）
今年は入賞すると概して (100000 * n) 円以外にもいろいろなものがもらえていた。プログラミング部門は 1 位だと米 30[kg] とパソコン（1 人 1 台）、2 位だと去年と同じ PCK 参加者は使わないようなソフト、3 位だと「サーバー」、4 位だと 2 位のソフトの部分集合、5 位〜8 位は「パソコン甲子園オリジナルグッズ」。パソコンは今持ってるノートの半分の質量と厚さで持ち運びに適しているらしくてうれしい。2 位のソフトより 3 位のサーバーのほうが、4 位のソフトより 5〜8 位のグッズのほうがいい気がするのは気のせいだろうか