読者です 読者をやめる 読者になる 読者になる

kengo92iの日記

プログラミングとかやったことの記録を書いていきます。

CODE THANKS FESTIVAL 2014 B日程 参加記

CODE THANKS FESTIVAL 2014というリクルート主催のプログラミングコンテストに参加してきました。12月14日に「コワーキング・スペース MONO」で行われました。

概要

  • 参加資格
    • 予選AまたはBで200点以上獲得
    • CODE FESTIVAL本戦不参加
  • 交通費
    • 交通費全額負担
    • 参加にあたっての往復交通費は全額負担いたします。
  • 賞品
    • 1~10位までは高級焼肉招待
    • 5問以上正解で、オリジナルトートバッグプレゼント
    • 各問題にFA賞があります
  • 親睦会
    • 肉、ピザ、寿司祭!
    • 各日程ともにコンテスト終了後に懇親会を予定。

移動フェイズ

5時起きで、新幹線に乗って東京(品川)へ。
品川 -> 新橋 -> テレコムセンターに向かう。
ゆりかもめの切符が青い切符だったので、ちょっと珍しかった。
会場が14Fだったのに、エレベーターに14Fのボタンがなくてちょっと焦った。
とりあえず、20Fに行くと、降りるためのエレベーターがあった。

準備フェイズ

領収書を渡して、交通費申請をする
Tシャツと名札をもらって席に着いてWi-Fiの設定をする
しばらくすると、お弁当が配布されだしたので、好きなお弁当を選ぶ。

f:id:kengo92i:20141216001318j:plain

叙々苑の焼肉弁当を選びました。めちゃおいしかったです。また食べたいと思いました。

11:30くらいから開会式が始まりました。
5問正解するとCODE THANKS FESTIVALのトートバックがもらえると説明されました。トートバックもらうために頑張ろうと決めました。

問題フェイズ

12:00~15:00までの3時間8問出題されました。

オープンコンテストも同時開催されていたので、下のURLから問題が見れます。
Welcome to code thanks festival 2014 B日程(オープンコンテスト) - code thanks festival 2014 B日程(オープンコンテスト) | AtCoder

A問題

2つの値で大きい方を出力するだけ

int main()
{
	int A,B;
	cin >> A >> B;
	cout << max( A, B ) << endl;
	return 0;
}

B問題

3つの数字を,足し算と掛け算を使って一番大きくなる数を求める問題
4通りをすべて試して、一番大きな数を取る。

int main()
{
	int A,B,C;
	cin >> A >> B >> C;
	int ans = max(A+B+C, (A*B)*C);
	ans = max(ans, (A+B)*C);
	ans = max(ans, (A*B)+C);
	cout << ans << endl;
	return 0;
}

C問題

きつね派とうさぎ派で人気投票を行って、きつね派が過半数を取った地域の数を出力する。全体の数が100の場合に、過半数は50ではないことに注意(51が過半数)。

int main()
{
	int N;
	cin >> N;
	vector<int> V(N);
	vector<int> F(N);
	
	rep(nth,N){
		cin >> V[nth];
	}

	rep(nth,N){
		cin >> F[nth];
	}

	int ans=0;
	rep(i,N){
		if((V[i]/2)-F[i] < 0){
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

D問題

足ゲームというタコ星人に人気なゲームを行う。T秒間の間、それぞれのボタンをA秒毎に押さなければならない。足ゲームをクリアするために必要な足の数を出力する。

配列に目印を付けて行って、配列内の最も大きな値を出力する。

int main()
{
	int N,T;
	cin >> N >> T;
	
	vector<int> turn(T,0);
	int A;
	rep(i,N){
		cin >> A;
		A--;
		for(int j=A; j<T; j+=(A+1)){
			turn[j]++;
		}
	}
	cout << *max_element(ALL(turn)) << endl;
	return 0;
}

E問題

与えられた領域の、示された領域を黒く塗っていく。スタート地点からゴール地点まで、黒いマスだけを通ってクリア出来るか判定する。スタート地点とゴール地点が黒いマスじゃない場合はアウト。

始めに、指定された領域を黒く塗りつぶす。あとは深さ優先探索(dfs)で、ゴール地点に到着出来るか判定する。

const int NONE = 0;
const int BLACK = 1;
const int VISIT = -1;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

vector<vector<int>> field;
int R,C,N;
bool flag;

void fill_b(int r, int c, int h ,int w)
{
	REP( y, r, r+h ){
		REP( x, c, c+w ){
			field[y][x] = BLACK;
		}
	}
	return;
}

void dfs(int r, int c, int er, int ec)
{
	if( r<0 || r>=R || c<0 || c>=C ){ return; }
	if(field[r][c] == VISIT){ return; }
	if(field[r][c] != BLACK){ return; }
	field[r][c] = VISIT;
	if( r==er && c==ec ){ flag=true; return; }

	rep(d,4){
		dfs(r+dy[d],c+dx[d],er,ec);
	}

	return;
}

int main()
{
	cin >> R >> C;
	field.assign(R,vector<int>(C,NONE));

	int sr,sc,er,ec;
	cin >> sr >> sc;
	cin >> er >> ec;
	sr--; sc--; er--; ec--;

	cin >> N;
	int r,c,h,w;
	rep(nth,N){
		cin >> r >> c >> h >> w;
		r--; c--;
		fill_b(r,c,h,w);
	}

	flag=false;

	if(field[sr][sc] != BLACK || field[er][ec] != BLACK){
		//Do Nothing...
	}else{
		dfs(sr,sc,er,ec);
	}

	cout << ( (flag) ? "YES":"NO" ) << endl;
	return 0;
}

とりあえず、ここまでで1時間ぐらい。トートバックがもらえることが確定。

あと3問あるから1問くらいは解こうと意気込む。

F~H問題

2時間Google先生に相談してみたけど解けず..
ここまで、それなりに手は止まらずコーディング出来ていたものの、F問題から方針が立たず。
G問題の石取りゲームの必勝法みたいのが検索したら出て来た。F問題までは解きたかった。

5完はしていたので、トートバックはもらえた。

f:id:kengo92i:20141216010900j:plain

後半の体たらくが駄目すぎた。もっと精進しなくては。

表彰・解説

コンテストが終了したら、表彰と解説が行われました。生chokudaiさんが見れてうれしかった。F,Gは動的計画法(DP)の問題だった。動的計画法の勉強します。Hはオイラー路を使うと解けるという問題だった。解説聞いてて勉強になった。

懇談会

肉と寿司とピザのいっぱいあった。DDRと太鼓を置いてあってすごい盛り上がってた。色々な人としゃべれて楽しかったです。CODE FESTIVALで話題になってた書道コーディングがあった。

f:id:kengo92i:20141216010836j:plain

結構たくさんの人が書道コーディングをしていました。もうコーディングじゃなくね?っていうものもあります。

f:id:kengo92i:20141216010749j:plain

最後に

始めてのオンサイトで楽しかったです。東京までの交通費が全額負担してもらえるというのがすごかったです。とりあえず、トートバック持って帰れてよかったです。リクルートの方々ありがとうございました。