lp6m’s blog

いろいろかきます

ICPC2016国内予選に参加しました

今年も参加しました.情報学科3人で.
2年前: 126位 LP6m メモ ICPC予選に参加してきました
1年前: 90位 ICPC2015国内予選に参加しました - lp6m’s blog

今年: 67位 3完
去年は「来年は4完するぞ」とか言ってたのにできなかった.
去年終わってから競プロの勉強をぜんぜんしてこなかったし,前日までHardware and Software Laboratory Project 3B (Software Part) に追われていたのが完全に悪い.それでもとりあえずいま自分ができる実力を発揮しようということで頑張った.

A問題 4分

2重forループ回しただけ.
チーム全員で問題を読んだ.自分は後ろでコードを眺めて指示したりした.2分でかいて4分でACしたっぽい.
ちなみにこの時点では15位でイエーイとか言ってた.

int main(){
	while(1){
		int n;
		cin >> n;
		if(n == 0) break;
		ll int a[1001];
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		long long int res = 1000000000;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j) continue;
				res = min(res, abs(a[i] - a[j]));
			}
		}
		cout << res << endl;

	}
}

B問題 24分

自分はCを読んでいたので問題を見ていない.ちょっとだけハマったらしいけど焦ってたからだと思う.

int main(){
	while(1){
		int n;
		cin >> n;
		if(n == 0) break;
		map<char, int> m;
		for(int i = 0; i < 26; i++){
			m[i + 'A'] = 0;
		}
		char tmp[101];
		for(int i = 0; i < n; i++){
			cin >> tmp[i];
		}
		for(int i = 0; i < n; i++){
			char c = tmp[i];
			m[c]++;
			vector<pair<int, char> > result(26);
			for(int i = 0; i < 26; i++){
				result.push_back(make_pair(m['A' + i], 'A' + i));
			}
			sort(result.begin(), result.end());
			reverse(result.begin(), result.end());
			int sub = result[0].first - result[1].first;
			if(sub > n - i - 1){
				cout << result[0].second << " " << i + 1 << endl;
				break;
			}
			if(i == n - 1) cout << "TIE" << endl;
		}
	}
}

C問題 70分

自分はCをずっと眺めていたのにふるいすれば終わりに気がつかなかった。言われて実装したらなんかなかなか処理が終わらない.ぼくが無駄な処理してるところに気がついて直してAC

int oksize  = 7400000;
int main(){
	int n,m;
	bool ok[oksize];
	while(1){
		cin >> m >> n;
		if(n == 0 && m == 0) break;
		REP(i,oksize) ok[i] = true;
		REP(i,m) ok[i] = false;
		int cnt = 0;
		int tmp = m;
		REP(j,n){
			for(int i = 0; i * tmp < oksize; i++){
				if(i*tmp < m) continue;
				ok[i*tmp] = false;
			}
			FOR(i,tmp,oksize){
				if(ok[i]){
					tmp = i;
					break;
				}
			}
		}
		cout << tmp << endl;
	}
}

D問題 提出できず

C問題をACしてとりあえず去年と同じなのでホッとした.D問題を読んだ.ダルマのどこを崩すかって枝分かれしていくわけだからdfsを思いついたので一番競プロをまじめにやってるチームメイトに書いてもらった.サンプルが通ったので入力データをダウンロードして実行したが全然終わらない.とりあえずメモ化できるのでメモ化してみたんだけど、全然早くならなかった.
結局そのまま試合終了まで考えてもどうにもならなくて終わってしまった.
以下、遅いコード

int n;
int ans = 0;
map<vector<int> , int> m;

int solve(vector<int> v){
	// cout << v.size() << endl;
	if(m.find(v) != m.end()) return m[v];
	m[v] = n - (int)v.size();
	for(int i = 0; i < ((int)v.size() - 1); i++){
		//cout << "jhe" << v.size() <<" " <<  i << endl;
		if(abs(v[i] - v[i + 1]) <= 1){
			vector<int> newv = v;
			newv.erase(newv.begin() + i);
			newv.erase(newv.begin() + i);
			m[v] = max(solve(newv), m[v]);
		}
	}
	return m[v];
}
 
int main(){
	while(1){
		cin >> n;
		if(n == 0) break;
		vector<int> w;
		for(int i = 0; i < n; i++){
			int tmp;
			cin >> tmp;
			w.push_back(tmp);
		}
		ans = 0;
		m.clear();
		cout << solve(w) << endl;
	}
}

反省

Cはもっとはやくふるいで解けることに気がつくべきだった.まあ全然練習してないので雑魚なのは当然.
コンテストに出るたびにやっときゃよかったとか行ってるので少しくらいがんばってみるかなあという感じ.
今日は平安神宮に行った.精進しろと言われた.
f:id:lp6m:20160626150841j:plain


あとは全然関係ないのだけど前日まで追われていた実験でCっぽいSmallCのコンパイラを作ったのは面白かった.
文系の父親が大学生のときくらいにかいていたZ80アセンブラのコードを印刷したノートが家にあって、実験のことについてたくさん話せただろうなあとかおもってすこし寂しかった.