GCJJ出る人の助けになれば…

プログラミング

「
追記、本家へのリンクを張っておきます。
今回取り上げるのは、ここにある練習のＡです、他にも様々な情報があるのでみてみましょう！
http://code.google.com/codejam/japan
」
さて、明日あたりにGCJJが始まるわけですが、初参加の人が増えれば良いなぁ…と願って、
実際にどのように競技がどのようなもので、どのように参加すれば良いのかをまとめてみたので
ちょい長いですがよければご覧ください
さて、例は、今GCJJのサイトに上がっている練習問題のA問題としましょう
これを実際に解いていく過程で、どのように参加したらいいかを説明したいと思います。
まず、問題を開きます
読んでいきましょう、ふもふも、なんかスイッチが切り替わるわけですね
しっかし、良くわからんなぁ…よし、とりあえず、愚直にシミュレートしてみることにしましょう
さて、実際にプログラムを書いていくことにしましょう（今回はC++言語とします）
恐らく、こういう競技初参加の人にとって、2つほど疑問が上がるでしょう
入力って何？という疑問と、出力って何？という疑問です
GCJJでは、全ての入力はファイルから、出力もファイルに行われます
（ぐえーーファイル入出力！と言う人がいるかもしれませんが、これは後で解決します）
さて、入力の欄を見ていきます
ふむ、あるファイルが与えられて、入力の一行目にテストケース数
続くT行に2つの数字があるわけですね
つまり、こういうファイルが与えられるわけです（後で出てきます）
出力ファイルはというと、書いてあるようなファイルを生成すれば良いわけです
Case #hoge: ON or OFFと各行に書いてあるようなファイルですね
では早速書きましょう、かきかきかき

#include<iostream>

using namespace std;

int main(){
	int tn=0;
	cin>>tn; // read test case number
	for(int ttn=1;ttn<=tn;ttn++){
		cout<<"Case #"<<ttn<<": "; //output test number
		int n,m;
		int L[50]; //L[i]==0 => OFF, 1 => ON
		for(int i=0;i<50;i++)L[i]=0; //set OFF
		cin>>n>>m; //read two int
		for(int i=0;i<m;i++){ //simulate
			for(int j=49;j>=0;j--){
				int flag=1;
				for(int k=j-1;k>=0;k--){
					if(L[k]==0) flag=0;
				}
				if(flag==1){
					if(L[j]==0)L[j]=1;
					else L[j]=0;
				}
			}
		}
		int flag2=1;
		for(int i=0;i<n;i++){ //check on or off
			if(L[i]==0)flag2=0;
		}
		if(flag2==0){ // output answer
			cout<<"OFF"<<endl;
		}else{
			cout<<"ON"<<endl;
		}
	}
	return 0;
}

というわけで上記のようなプログラムが出来上がりました
あれ？お前これファイル入出力じゃなくて、これキーボードから読んで画面に出すアレじゃん？
と思った方、魔法の構文がありますので、それは後ほど、コンパイルして、サンプルを手入力してみて
どうやら正しそうなので提出してみましょう
A-smallを解くのボタンを押すと、A-small.inをダウンロードするというのがあるはずです
それを押すと、A-small-practice.inというファイルがダウンロードされるはずです
これがインプットになるので、大切に扱いましょう
（中身は本文に指定されているような形式のただのテキストファイルです）
さて、いよいよ解答作成です、魔法のコマンドを入力します
a.exe < A-small-practice.in > A-small.out
これは、真ん中のファイルを手入力の代わりに入れて、その出力を後ろのファイルに入れろというものです
別に出力ファイルの名前はこれでなくてもよいのですが、分かりやすいのでこうしています。
さて、このA-small.outの中身をテキストエディタで見てみましょう
それっぽいファイルが出来ていますね、これはGCJJで覚えておくと便利です
リダイレクト、というOSの機能をつかっています、様々な場面で応用が利くので、覚えておきましょう
さて、これを提出してみます、提出ー
おお、正解と出ました、どうやら正しかったようです。
続いてLargeも…と行きたいところですが
実は、このままではだめです、理由は、試しにA-large-practiceをこのプログラムに食わすとわかります。
…終わりませんね、なかなか
今は練習セッションなので、提出に制限はありませんが、本番ではLargeはダウンロードしてから8分
しかも一回のみしか提出できないので注意してください（smallはダウンロードから4分、何回か提出はできます）
もっと早く動くプログラムを書かないといけないようです
ここで余談ですが、試しにループの中身が最大何回ほど実行されるのかカウントしてみましょう
テストケース数5000*K(10^8)*50*50で、とりあえずとんでもない大きさになります
経験のある人は、この数字が大体10^8以内になるように調整します
だいたいの目安なので、覚えておきましょう
余談おわり
もっと早いプログラムを書かねばならないようです
試しに、ON,OFFの変化を一回指を鳴らすごとに絵に描いてみましょう
なにか気付きませんか？そう、2進数です
スイッチのON,OFFという状態は、何回指を鳴らしたかの2進表記になっているのです。
よって、ある数字を2進表記で書いた後、Nbit目以下が全て1かどうかを判定すればよいです
これをもとに、Large用のプログラムを書いてみます、かきかきかき

#include<iostream>

using namespace std;

int main(){
	int tn=0;cin>>tn;
	for(int ttn=1;ttn<=tn;ttn++){
		cout<<"Case #"<<ttn<<": ";
		int n,m;cin>>n>>m;
		int ans=1;
		for(int i=n-1;i>=0;i--)if((m&(1<<i))==0)ans=0;
		if(ans)cout<<"ON"<<endl;
		else cout<<"OFF"<<endl;
	}
	return 0;
}

だいぶ短くなりましたね、しかもわりと変なコードです（なぜ動くのかの説明はしません）
これでループの回数は5000*30で充分間にあいそうです
提出してみましょう…
a < A-large-practice.in > A-large.out
正解と帰ってきました、どうやら正しかったようです
と、ここまでが問題を解く流れです
少し加えて述べると
まず、smallは提出した時点で判定が行われる上、何回か提出が可能です
しかし、largeに関しては、1回しか提出チャンスがないので(8分の縛りもある)注意して下さい
正解かどうかも試合後に判定されます
ここら辺詳しくは、GCJJサイトのルールを見てみてください
予選はsmall-largeのセットを1問題分解けば決勝ですね！
皆さんのご健闘をお祈りしています！（といいつつ僕も落ちないよう頑張らねば…）
ではGood luck and Have fun!