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; } }