KUPC オンサイト参加記

参加してきました。ぱない大学生に囲まれてこっそり京都大学オンサイトで参加していました。

[9:30]家出る。

  • 京橋でjubeat(音ゲー)等してから京阪特急乗ったりいろいろ。

[11:16] 出町柳に到着する。

  • 迷い道がはじまる・・・・。

[11:40] 時計塔到着

  • キャンパス付近で迷い道しまくって、やっとたどり着くも、誰も居ない。仕方なく緊急連絡先に電話を入れると、id:kamingさんがわざわざ着てくれて申し訳なさMAX。
  • id:ir5さんとかに名刺渡す。
  • その後適当にセッティングして、４人くらいで１００円ローソンにお買い物に。いなり寿司買った。

[12:45]

  • 式辞と自己紹介タイム(あといなり寿司もぐもぐ)。５分くらいで終わった。

[12:55] コンテスト開始5分前である。

  • ご歓談タイム。fura2さんが声を掛けにきてくれる。お互いに健闘を祈る。彼は僕のＯＢに当たる方ですが、なんだかんだで初対面だったりした。すごい人なのでウキウキ。コンテスト前なのでさらにウキウキ。

[-00:01]

  • コンテスト直前に紙で問題が配られる。なんか緊張感がそこまでないままはじまる。

[00:00] コンテスト開始

  • A読む。「看板」・「KUPC」・「最大」という単語とサンプルだけ見て把握。10秒くらい。
  • 実装したものの、コンパイルがなぜか通らずパニくる。ローカルでうまくうごかないのでそのまま提出。

[00:01] A AC.

  • 3番目くらいの提出だった。パニくらなきゃFirst Acceptance取れたんじゃないかと思って唇を噛む。ただスタートは好調らしい。
  • ちょっとstandings眺めてからBを読む。ああ、ただのDPか、「出発・到着地点に蝉はいないな！コーナーケースないな！」で提出。

[00:06] B AC.

  • 好調ではある。Cを読む。出た！対話型！"できるだけ小さく"という記述を勘違いする。
  • AIは"ちょうど"2文字の単語言えるのかー。←勘違い②。
  • とりあえず戦略は相手の自爆狙いで言っていくしかないなー。ただ、もしかしたら最適解じゃないかもしれない。。。どうしよう。悩む。
  • 明確にステップが想像できない。このレベルのゲームですらゲームは苦手・・・。とりあえず書こう。
  • 書いた!

[00:20] C WA.

  • ええー、どうしてー・・・結構な頻度でWAだ。
  • やっぱり最適じゃなかったからかなあと思ってたら50回という上限にここで気づく。
  • 理由を考えていたらAIは1文字も言ってくることに気づく！
  • 2文字固定でやってたので、その場合の戦略を書く。

[00:29] C AC.

  • ミスったぁぁあ！完全に勢いを失ってしまった・・・。
  • D読む。よく分からないから飛ばす。J読む。W<=16なのでBitDPなんだろうなーと思ったが全く分からなかったので、10分くらいしてDに戻ってくる。
  • Dの題意を理解した。手でやるときは影響度でかいやつからきめてくよなーという感じはしつつも、反例がありそうで書く気になれない。
  • でも頭が悪くて反例が思いつかない。
  • 「Dだし難しいはずがない。貪欲か何かでできるはずだ。正答者こそ少ないけれど、提出していないだけだからみんな惑わされているだけだ！」とかいうことを考えて変な自信が沸き、さっきの方針を実装しようとする。
  • 書けた。サンプル通ったので提出。

[00:59] D AC.

  • あれ・・・？本当に通ってなんか勝ち誇った気分になる。再び1桁順位ひゃっほい。
  • E読む。しえるさんだ。ちゅっちゅできたよ！
  • しかし分からない。ので、G読む。
  • 「合宿でこんなんあったなぁ・・・、もっと簡単だったけど。基本的にこの手の問題は二分して絞り込んでくんだよナー。」みたいなことを思って適当な方針で実装しはじめる。ただ、200が何を意味する値設定なのか分からない。
  • まあなんとか書いたので提出。

[01:47] G WA.

  • 全くの嘘解法というか、サンプルも通るか怪しかったかもしれない。和がそのままじゃなくて、それをxorした結果が返ってくるということに気づき、後回しにしたくなる。
  • しかも、I提出している人がいて、ザッと見バイバイな二次元の不等式が載っていただけで簡単なんじゃね？とか思ったりして余計そっちやったほうがいいんじゃないかと焦る。

[02:00]

  • G分からなかったので、Iにうつる。1番目の行と列使って縦と横ソートするだけでいいんじゃイカ！？というよく分からない直感に基づいて実装してみたらサンプル通ったので提出する。

[02:11] I WA.

  • うーん。やっぱりな。……ってん？63個中最後の最後のケースだけでWAを出しているぞ？
  • コーナーケースを考えるが思いつかない。バグを探すが思いつかない。
  • 自分が部内コンテストwriterしたときに、テストケース完全乱数生成したら弱くなりすぎて、急遽最後に手動ケースを追加したことを思い出して、自分の中で超嘘解法臭がしはじめる。
  • とりあえずもうひとつ思い当たる実装をして提出。

[02:30] I WA(2回目).

  • WA増えた。
  • まてよ。最後の1つしか間違ってないんだからそのケース特定すればええやん！←カス
  • assert()さんを使って特定を試みる。(ここらへんからWA出しまくる)
  • ジャッジ要員がかなり横にいるのにも関わらず堂々と怪しいソース提出しまくるきゅうりで涙がそこに居た。
  • にぶたん用いつつ10回くらいWAして、63番目のケースは5 * 5ということが発覚。ただ、３つくらい5*5のケースがある。入力に特徴の違いはないかなと思いさらに調べる。
  • さあ、入力の値を調べようと思ったところで、内部エラーとか出るようになる。
  • さすがにまずいことしたのかなーと思いつつ何食わぬ顔でclarを送ると、"テストケースが弱いことが確認できたため追加作業中です。"とか書いてあって絶望。俺の30分くらいと膨大なペナルティ(予定)とはなんだったのか。

[02:50]

  • 暫く放心状態になるも、気を取り直して真面目に正攻法を考える。
  • 成り立たないケースを考えてみると、修正してこれで通るんじゃないかみたいなのは思いつく。
  • しかし通らない。

[03:54] I WA(18回目)

  • 最後のWAである。
  • Gとかを再び読むが、やっぱり最後にxorを取られる場合の解法思いつかない。200回少なくね・・・。
  • Eとか実は冷静に考えたら解けるのではないかと思い読む＞
  • Bが小さいので区間篩っぽいことをするはず。そして「A-Bが2未満にならないように気をつけないといけない。」というところまでは気づいた。
  • そこから効率的な篩が思いつかないのでとりあえず全探索をしまくる。ただ、4時間ぶっつづけはさすがに疲れがきているのか頭悪いエンバグしまくる。

[04:55]

  • 実はこの時点で、Eのサンプル通るソースを書けていない。絶望する。
  • 絶望したのでtwitterなどをはじめてしまう(悪い)

[05:00] こんてすと　いず　おーばー

  • 4:00時点では13位だけど、めっちゃ落ちるだろうなーと思いガクンと肩を落とす。
  • とりあえずid:hasi_tさんに声かける。なんかGの基本アプローチはやっぱり二分だけど、ランダムシャッフルつかって解いたと聞いて驚く。さらにDもランダムで通したと聞いて驚く。
  • しかもid:ir5さんが「どっちも想定解法で、Gの乱択は正攻法です！そういうコンテストです！ふふふ！」みたいなことを言っていて耳を疑う。良い悪いかはさておき、斬新すぎた・・・！
  • とりあえず撤収準備。id:Respect2Dさんとか、yuta1024さんとかに名刺を渡す。あと一人名刺を渡す予定だったんだけど渡すの忘れていた！
  • 懇親会会場までついていってからお別れする。
  • 結局、電車の中でtwitterやっててid:roxion1377に教えてもらったけど、10位くらい下がっていた。

結果

解いた : oooo-----(4完)

ペナルティ : 1:03(Cで1WA)

全体順位 : 23位


感想

楽しかった！オンサイトは久しぶりだったので、よかった。あと大学生たくさん居てそれもわくわくした。出会い厨ではないけれど、関西はあんまり競技erいない分(嘘かも)、動ける範囲で競技関連の催し物があったら行きたくなってしまうのです！

とりあえず４完でしたが、Ｄはオマケみたいなものなので、ＥやＩなどの問題をちゃんとした解法を思いついて解きたかったですね！精進します。

ていうかこの問題セットでも9完できる赤い人たち恐いです・・・。

ソース

A KUPC

だーっと書いた。

int main(){
	string s;
	cin >>s ;
	map<char,int> data;
	rep(i,s.size())data[s[i]]++;
	cout << min(min(data['K'],data['U']),min(data['P'],data['C'])) << endl;
}
<
>|cpp|

B 蝉

せみ最小化問題

int main(){
	int H,W;
	cin >> H >> W;
	char d[51][51];
	rep(i,H)rep(j,W) cin >> d[i][j] , d[i][j]-='0';
	int dp[100][100];
	rep(i,100)rep(j,100) dp[i][j] = 1000000;
	dp[0][0] = 0;
	rep(i,H)rep(j,W){
		if(i) dp[i][j] = min(dp[i-1][j] + d[i][j] , dp[i][j]);
		if(j) dp[i][j] = min(dp[i][j-1] + d[i][j] , dp[i][j]);
	}
	cout << dp[H-1][W-1] << endl;
}

C しりとり

戦略はとりあえずaで攻める！

map<string,bool> used;

bool isok(string a,string b){
	if(used[b] == true) return false;
	return a[a.size()-1] == b[0]; 
}

string talk(string g){
	cout << "?" << g << endl; fflush(stdout);
	fflush(stdout);
	string ans ; cin >> ans;
	return ans;
}
int main(){
	string prev = "a";
	used[prev] = true;
	while(1){
		string r = talk(prev);
		if(!isok(prev,r)){ cout << "!OUT" << endl; fflush(stdout); return 0; }
		if(r.size() == 1) prev = string(1,r[0]) + "a";
		else prev = string(1,r[1]) + "a";
		used[r] = true; 
		if(used[prev]) prev = "abba"; // これは必ず1回だけしか遷移しない。
		used[prev] = true;
	}
}

D 列の構成。

出現度でソートして、出現した回数が多いやつから優先的に1にしていく。3N/8を溢れないように気をつけながらネ！

ていうかこれは適当解法で通るらしい。

int main(){
	int n,m;
	while(cin >> n >> m){
		int mx = 3*n/8;
		int mi = n/8;
		int d[1000] = {0};
		vector< vector<int> > v(1000);
		vector<int> c(1000);
		rep(i,m){
			rep(j,n/2){
				int a;
				cin >> a;
				a--;
				v[a].push_back(i);
				d[a]++; 
			}
		}
		int seq[1000] = {0};

		vector< pair<int,int> > p;
		rep(i,n)p.push_back(make_pair(d[i],i));
		sort(p.begin(),p.end(),greater<pair<int,int> >() );
		rep(bigI,n){
			int i = p[bigI].second;
			bool f = true;
			rep(j,v[i].size()) if(c[ v[i][j] ] >= mx ) f = false;
			if(f)rep(j,v[i].size()) c[ v[i][j] ]++ , seq[i] = 1;
		}
		rep(i,n) cout << seq[i];
		cout << endl;
	}	
}