2011-09-30

このくらいのことを理解していればGoogle Code Jam Japan 2011で200位以内に入ってコードジャムＴシャツをもらうには十分だろうと思われる程度のＣ言語の知識まとめ

・sortが抜けていたので追加
・long longが抜けていたので追加

Google Code Jam Japan 2011公式サイト
オンライン予選：10 月 1 日 (土)　13：00〜19：00（この時間帯のどこかで問題を解けばよい）（予選開催中にも参加登録が可能）
オンライン決勝：10 月 8 日 (土)　13：00〜16：00

＜※補足１＞
（誤）この程度のＣ言語の知識をもっていればおそらく200位以内に入れる
（正）Ｃ言語を使って200位以内に入るには、このくらいのことを知っておけばたぶん知識は十分。（あとは思考力）

＜※補足２＞
・Ｃ以外のプログラミング言語など（無料で入手できるものに限る）で問題を解くことも可能。
・プログラムを使わず、人力で答えを出すことも可能。だれか、人力のみで予選を突破してみてくれませんか。

・ソースコードのひながた

//摂氏温度を華氏温度に変換する問題に対する回答プログラムの例
//（※注意）ケース番号の読み込みや出力の形式は、本番の形式と異なる可能性があります。問題文をよく読みましょう
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int main(void){
	int casenum;
	scanf("%d",&casenum);
	for(int casecnt=1;casecnt<=casenum;casecnt++){
		double c,f;
		scanf("%lf",&c);//（１）入力を変数に読み込む
		f = 9.0 / 5.0 * c + 32.0;//（２）読み込んだ入力に対応する答えの数値を計算
		printf("Case #%d: %.10f\n",casecnt,f);//（３）求めた答えを出力
	}
	return 0;
}

・変数の宣言、配列変数の宣言

int a,b,c;
double x,y;
long long n,m;
int num[1000];//1次元配列（num[0]〜num[999]が使える）
char field[100][100];//2次元配列（field[0][0]〜field[99][99]が使える）

・scanfとprintf（入力と出力）

int n;
double d;
long long a;
char st[1000];

scanf("%d",&n);//int型の読み込み
scanf("%lf",&d);//double型の読み込み
scanf("%lld",&a);//long long型の読み込み
scanf("%s",st);//文字列の読み込み（スペースまたは改行区切りでひとかたまりと認識される）（読み込む文字列の長さの最大値＋１以上のサイズの配列を宣言しておくこと）

printf("Hello World\n");//文字列の出力（'\n'は改行記号）
printf("%d",n);//int型変数の出力
printf("%lld",a);//long long型変数の出力
printf("%f",d);//double型変数の出力
printf("%.10f",d);//出力精度（小数点以下の桁数）を指定してdouble型変数を出力（指定した桁数の次の桁で四捨五入）
printf("%s",st);//char型配列の中身を文字列として出力

・演算子

a + b;//和
a - b;//差
a * b;//積
a / b;//商
a % b;//剰余
a = 3 + 2;//代入

＜使うかも？＞　ビット演算子

a & b;//and
a | b;//or
a ^ b;//xor
~ a;//not
a << 1;//左シフト
a >> 1;//右シフト

・if文と演算子２

if(a==0){
	//aが0のとき
}

if(a==0){
	//aが0のとき
}else{
	//それ以外
}

if(a!=0)//aが0でないとき
if(a<0)//aが0より小さいとき
if(a<=0)//aが0以下のとき
if(a>0)//aが0より大きいとき
if(a>=0)//aが0以上のとき
if(a==0 || a==1)//「aが0」または「aが1」のとき
if(a==0 && b==0)//「aが0」かつ「bが0」のとき

・for文

for(int i=0;i<100;i++){
	//iが0、iが1、……、iが99、とループ
}

・while文

while(a>0){
	//aが0より大きい間だけループ
}

・break,continue

for(int i=0;i<10;i++){
	if(i==3)continue;
	if(i==7)break;
	printf("%d\n",i);//最終的に表示されるのは0,1,2,4,5,6
}

・平方根

sqrt(2);//<math.h>をインクルードする必要あり

・関数

int plusone(int a){
	return a + 1;//a+1を戻り値として返す
}

int main(void){
	int n;
	scanf("%d",&n);
	printf("%d\n",plusone(n));//n+1の値を出力
	return 0;
}

＜使うかも？＞　参照（Ｃ＋＋の機能）

void plusone(int &a){//引数に&をつけると参照渡しになる（関数内で値を変更すると、それが呼び出し元にも反映されるようになる）
	a = a + 1;
}

int main(void){
	int n;
	scanf("%d",&n);
	plusone(n);//nの値が1増える
	printf("%d\n",n);
	return 0;
}

・ローカル変数とグローバル変数

//（※注意）ローカル変数は、宣言したときの初期値が未定義
//グローバル変数の初期値は、指定しなければint,double,char型では0
//（※注意）ローカルでは、あまり大きすぎるサイズの配列を宣言することはできない

int num;//グローバル変数（どの関数内でも使える）

void func(void){
	int x,y;//ローカル変数（func関数内でのみ使える）
}

int main(void){
	int n;//ローカル変数（main関数内でのみ使える）
}

・ソート（Ｃ＋＋（ＳＴＬ）の機能）

//C言語ならqsort関数を使うが、C++(STL)のsortの方が簡単なのでそちらで

#include<algorithm>//sort関数を使うのに必要。他にはmaxとかminとかuniqueとかが便利
#include<functional>//降順ソートにするのに必要
using namespace std;

int main(void){
	int num[10]={3,1,4,1,5,9,2,6,5,3};
	sort(&num[0],&num[10]);//（ソート領域の先頭、ソート領域の末尾の１つ先）を指定する。昇順ソート
	sort(&num[0],&num[10],greater<int>());//降順ソート。<   >の中には変数の型名を書く
	return 0;
}

＜※補足３＞
以上の知識に、STLのmapを加えれば、「このくらいのことを理解していればGoogle Code Jam Japan 2011で1位をとって 256,000円をもらうには十分だろうと思われる程度のＣ言語の知識まとめ」にしてもあまり問題はないかと思います。

2011-09-20

Marathon Match 70　獲得賞金のまとめ

（1ドル＝76.56円として計算）

1位に5000ドル（＝382,800円）の賞金が与えられるMarathon Match 70に参加しました。
ちなみに、2位は2000ドル、3位は1500ドル、4位は1000ドル、5位は500ドルで、賞金総額は10000ドル。

そして、1位を獲得。

ただし、同率1位が自分を含めて16人出たため、賞金総額10000ドルを16人に等分配。
・382,800×2÷16＝47,850円

TopCoder社から賞金が送られてくるときに、税金30％がマイナス。
・47,850×0.7＝33,495円

Paypalから自分の銀行口座に出金するときに、為替手数料2.5％と手数料250円が引かれる。
・33,495×0.975−250＝32,407円

賞金を獲得するのが初めての場合、米国大使館でAffidavitの公証に50ドル（＝3,828円）必要。
・32,407−3,828＝28,579円

その際には、米国大使館の予約が必要で、そのためにはパスポートが必要。
パスポートの期限が切れていたので、更新手続きに16,000円かかる。
・28,579−16,000＝12,579円

その際に、写真（1,700円）と戸籍謄本（手数料450円）が必要。
・12,579−1,700−450＝10,429円

公証したAffidavitとW-8BENをTopCoder社に郵送するのに、EMSを使用（1200円）。
・10,429−1,200＝9,229円

パスポート更新や公証などにかかった交通費、合計約1300円。
・9,229−1,300＝7,929円

最終的な残高：7,929円　（1位の賞金5000ドルの、約2％）

2011-07-26

SRM513

解答例

250

全探索。

500

「揃うことが確定しているペアがあるならそれをめくる、そうでないなら未知のカードをめくる」が最善戦略。
dp[i][j]＝「場にi枚残っていてそのうちj枚が1度はめくられたことのあるカードである状態から始めて、最善戦略をとったときにかかるゲーム終了までに必要なターン数の期待値」とでもおいてDP。O(2500^2)。

参加記

250　→　175.41

10000*50*50を計算したら2億5000万になったので若干面倒くさいことをした。
途中まで問題文読み間違えて答えが合わなかった。

500　→　220.24

double dp[2500][2500]のサイズを計算したら500MBになったので若干面倒くさいことをした。
途中まで漸化式間違えてて答えが合わなかった。
若干面倒くさいことをしたせいでバグって再提出。

結果

R2188 → R2189
どうしようもない。

2011-07-24

TCO2011 Algorithm Round4

（問題文はTopCoderのサイトを見てください）

解答例

300

点iと点jが決まっているとき、( i , j )と交差するルートは、「領域Ａにある点の数×領域Ｃにある点の数＋領域Ｂにある点の数×領域Ｄにある点の数」になる。
i , jを全通り回し、各領域にいくつの点があるかも回して求めて、O(500^3)。
Ｘ座標とＹ座標にかぶりはないので、境界とかはあまり気にしなくてよい。
最後に重複をのぞくために２で割る。

500

ファイナルターンのドローでビンゴにする自分カードの集合Ａを回す。（2^5通り）
Ａの全カードに含まれる数字が１つ以上ない場合はスキップ。
Ａに含まれない自分のカードと相手の全カードをＢとする。Ｂは１枚もビンゴになってはいけない。
「数字の集合Ｘを選び、ＢのどのカードにもＸの元が１つ以上含まれているようにする」と、75-|Ｘ|ターン続けられる。つまり|Ｘ|が最小になるように選べばよい。
dp[i]＝「iの全カードにはＸの元が１つ以上含まれて、そうでないカードには１つも含まれていないようにしたときの、|Ｘ|の最小値」としてビットDPすると求められる。どの数字を使って達成したかは覚えておく必要がない。

参加記

300　→　0

Ｘ座標とＹ座標にかぶりがないという条件を読んだけれど頭から抜け落ち、面倒くさい場合分けを頑張るが、時間内に組みきれない。

500　→　0



（正）

for(i=0;i<(1<これを、

（誤）

for(i=0;i<(1<逆向きでもいけるような気がして逆向きにやってしまった。

結果

R2297　→　R2188

激弱ですらなくなった……。

2011-07-23

おそらく自分が最も輝いて見えるであろうランキング

＜MarathonよりSRMのレーティングの方が高い日本人のMarathonレーティング＞

１位：wata　2843（SRM：2863）
２位：jellies　1941（SRM：2297）
３位：［［iwi］］　1935（SRM：2594）
４位：rng_58　1861（SRM：3430）
５位：kita_masa　1785（SRM：2348）

そうそうたる面子に囲まれながらも２位につけている俺超強い、みたいな。

１位とはレート900以上の差があるので浮上する可能性は絶無に見えるけれども、よく見ると実はそうでもない。

2011-07-22

自己紹介

競技プログラミング界隈では、jellies、または、highjellies、のハンドルネームで活動中。
ICPCでは、チーム__________に所属。
個人では、主にTopCoder（SRM＆Marathon）、他にもGoogle Code Jamなど。

↓おおよその実力

解答例

250

500

参加記

250 → 175.41

500 → 220.24

結果

解答例

300

500

参加記

300 → 0

500 → 0

結果

250　→　175.41

500　→　220.24

300　→　0

500　→　0