Hatena::Grouptopcoder

kuuso1の日記

2016-10-03

KUPC 2016 参加記

| 02:51 | KUPC 2016 参加記 - kuuso1の日記 を含むブックマーク はてなブックマーク - KUPC 2016 参加記 - kuuso1の日記

KUPC 2016に京都オンサイトで参加してきました.

背景

オンサイトイベントは前々から興味があったのですが,いくつか外的要因*1や内的要因*2もあってなかなか参加できないことを寂しく思っていました.

今回KUPCがタイムリーに開催されるということで,ここぞとばかりに参加してきましたので,メモ書き程度ですが参加記を書いておきます.

あこがれの箇条書きスタイル参加記.

8月初旬

カーナビとデスクトップPCが立て続けにクラッシュ.

盆休みに帰省したついでにヨドバシでSurfacePro3を購入.財布が痛い.

デスクトップを買うまでのつなぎのつもりだったが十分機能する.外的要因を1つクリア.

9月初旬くらい?

KUPC開催とオンサイトの情報をゲット.

これなら予選とかもないので行こうと思えば行ける.内的要因をクリア.

とはいえ富山からはなかなか遠いな...

おっ,10月はクルマの点検で1回は帰省しないといけないな.

点検と兼ねることで交通費はクルマの維持費に計上,外的要因をクリア.

f:id:kuuso1:20161004014016p:image

前日

実家へのお土産*3を購入後,まずは車のディーラーへ.

点検1時間.待ち時間の間,カバンの中身を確認.これでPC忘れてたりしたらギャグだよ..

・・・ん?電源コード入ってないやんけ.マジかよ.

(点検完了後ヨドバシへ)

・・・は?電源コード高すぎなんだけどマジ?

⇒KUPC2016が課金ゲーと化した.

当日AM

甥っ子が半年前くらいに生まれたばかりなので,行きがけに寄って朝イチでご尊顔を拝見する.チョーかわいい.

スケルトンのサッカーボールのようなおもちゃがあったので「はーい切頂二十面体ですよ~」と英才教育.

京大に移動.時計台はかれこれ12年ぶりくらいな気がした.

コンテスト会場

自己紹介タイム.twitterでは知ってる方が多数.あと人々が若い(それはそう).

大学の教室だとなんだか資格試験を受けに来たみたいな気分になった.

コンテスト本番

毎年オンラインで参加しては2完とかで玉砕することが多かったが,今回は課金プレイ()だと自分に言い聞かせる.

あと調子が最近悪いのは考察が雑になってるからだと思っていたので,最後まで切らさないようにとは思ってた.

問題を開く.

A - バリケード / A Barricade

・これは書くだけ.

public void Solve(){
	int cnt = 0;
	for(int i=0;i<N;i++){
		var k = int.Parse(Console.ReadLine())
		if(k<A || k>=B)cnt++;
	}
	Console.WriteLine(cnt);
}
B - 作問委員会 / Problem Committee

・貪欲にとっていけばよさそう.一番多い文字がネックになるはず.

⇒ソートを最初にしかしてなくて1WA.しっかりしろ.

public void Solve(){
	int[] A = new int[26];
	for(int i=0;i<N;i++){
		A[P[i][0] - 'A']++;
	}
		
	int ans = 0;
	while(true){
		Array.Sort(A);
		Array.Reverse(A);
		int k=0;
		for(int i=0;i<26;i++){
			if(A[i] == 0)continue;
			k++;
			A[i]--;
			if(k==K) break;
		}
		if(k==K){
			ans++;
			continue;
		}
		break;
	}
	Console.WriteLine(ans);
}
C - クッキー☆増殖装置 / Cookie Breeding Machine

・手が止まった.

・制約が結構厳しいので,O(1)かO(logD)くらいで判定しないといけない.

・xorの問題はビットごとに分かれることが多い.この前のSRM*4でも出たばかりじゃないか.

⇒1.5h 正座,嘘解法投げるも通らず.あきらめて次へ

D - 長い黒板 / Long Blackboard

・KUPCの代名詞(?)リアクティブ問題.

・最初は幅優先のコード(1列追加してtrueなものをハッシュで覚えておいて増やしていく)を書いた

・3つめくらいのテストケースでQLE(QueryLimitExceed).

 それはそう.状態数が多くなりすぎる.(長さ4くらいで破たんしそう)

・倍々にクエリを投げて,長く一致するパーツを求める?それは上より多くなりそう.

・例えば,N=100に対して長さ64のパーツを運よく見つけられたとして,どこから始まるかは36通りやっぱり試さないといけない.

・このあたりで,課金しても2完フラグが見え隠れして結構泣きそうになったが,投げださないと決めたことを思い出した.

・どこから始まるかを決めなくても,確定した文字列を含むものを探しながら伸ばしていけばいいんじゃないのかこれ.

・前に1列追加して見つからなければ後ろに追加する方向で探そう.コードを投げる.7割方通った.もう一声.

・前に追加して見つからなくなってから以降は後ろ方向だけ探せばいい.そうだよ.

・再度投げる.2,3のエンバグ・デバグを経てAC

public void Solve(){
	
	List<String> L1 = new List<String>();
	List<String> L2 = new List<String>();
	String[] A = new String[]{ "..",".#","##","#."};
	foreach(var s in A){
		var res = Query(s);
		if(res =="T"){
			L1.Add(s.Substring(0,1));
			L2.Add(s.Substring(1));
		}else if(res =="end"){
			return;
		}
	}
	
	var ans = L1[0]+L2[0];
	bool forward = true;
	while(true){
		if(forward){
			bool chk = false;
			for(int t=0;t<L1.Count;t++){
				int n = ans.Length/2;
				var res = Query(L1[t]+ans.Substring(0,n)+L2[t]+ans.Substring(n));
				if(res == "end"){
					return;
				}else if(res == "T"){
					ans = L1[t]+ans.Substring(0,n)+L2[t]+ans.Substring(n);
					chk = true;
					break;
				}
			}
			if(!chk)forward = false;
		}else{
			for(int t=0;t<L1.Count;t++){
				int n = ans.Length/2;
				var res = Query(ans.Substring(0,n)+L1[t]+ans.Substring(n)+L2[t]);
				if(res == "end"){
					return;
				}else if(res == "T"){
					ans = ans.Substring(0,n)+L1[t]+ans.Substring(n)+L2[t];
					break;
				}
			}
		}
		
	}
}

String Query(String s){
	int n = s.Length/2;
	Console.WriteLine(s.Substring(0,n) +"\n" + s.Substring(n));
	Console.Out.Flush();
	return Console.ReadLine();
}

E - 柵 / Fences

・紙で考える.

・羊の周辺のマスの状況だけでは最善の配置が決まらないし,たぶんいくつか解がある.

・うーん,貪欲っぽいようなDPっぽいようなうまく書けないような.

・たぶんフローでしょ(適当)でギブアップ

C - クッキー☆増殖装置 / Cookie Breeding Machine

・再び.

・残り40minくらいあるけどもう分からんしエスパーするしかない.

・とりあえずN=2の全探索コード(for文 1重ループ)を書いて眺める.

・N=3(for文 2重ループ),N=4(for文 3重ループ)も書く.まだ分からん.

・最大値を得た時のそれぞれのクッキーの数を書く.つらい.

・あれ,N=4は(127,127,127,127-D),N=3は(127,127,D)じゃね?

・投げる.AC

・Last Acceptだった(2016/10/02 17:57:54)

public void Solve(){
	for(;T>0;T--){
		var d = int.Parse(Console.ReadLine());
		var N = d[0];
		var D = d[1];
		
		if(N%2 == 0){
			Console.WriteLine(127 * (N-1) +(127-D));
		}else{
			Console.WriteLine(127 *(N-1) + D );
		}
	}
}

というわけで4完.もうちょっと解きたかったが最後まで粘ったのでかなりエンジョイできました.

懇親会

クルマで来たしクルマで富山に帰らないといけない*5ので,焼き肉だったがノンアルコール参加.

「焼くクエリ」「(肉を網に)載せるクエリ」「食べるクエリ」

リアルに競プロerあるいはプログラマの知り合いが希少なのでこういう会話に飢えています.

今回は話が出来なかった方も居たけど,twitter上でしか知らない方々とも話が出来て楽しかった.

22:00ごろに京都を立つ.途中草津でガソリンスタンドを探して高速を降りてうろうろしたりしたが無事帰宅.

感想

オンサイトは,なるほど,リアルタイムな感じが非常に良かったです.

コンテスト後の解説とか,動画とかで見たことしかなかったので「これか~」って感じでした.

電源コンセントの減価償却もしたいので,また機会をみつけて参加したいですね.

*1:遠い,ノートPC不所持

*2:頭が足りない

*3:ますのすし,富山名産

*4https://community.topcoder.com/stat?c=problem_statement&pm=14396

*5:月曜は有給をとってはいたがうっかり歯医者の予約を入れてしまっていた