ICPC国内予選
去年と同様，haskell-loverでICPC参加しました．メンバーはid:eagletmtさんとid:draftcodeさんと自分．
結果はAB(+1)C(+1)DEで10位．学内では1位．
問題はhttp://icpc2011.ait.kyushu-u.ac.jp/icpc2011/contest/all_ja.html．順位表はhttp://imoz.jp/icpc/2011-domestic.html．
A
とりあえず作戦として自分が最初に簡単なやつ解いて，そのあいだに二人がBC考えるというのを事前に決定．普通にエラトステネスで素数求めて数えあげるだけ．
Aを書き終わる頃になって，コーチのほうで問題が見えず印刷できないというお達しが出る．急いでBCD印刷．
サンプル通ったのでSubmit．まずは1AC．
#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { vector<int> is_prime(123457*2, 1); vector<int> primes; int lim = sqrt(123457*2); is_prime[0] = is_prime[1] = 0; for(int i = 2; i < is_prime.size(); ++i) { if(is_prime[i]) { primes.push_back(i); if(i <= lim) { for(int j = i*i; j < is_prime.size(); j += i) is_prime[j] = 0; } } } while(true) { int N; cin >> N; if(!N) break; int cnt = 0; for(int i = 0; i < primes.size(); ++i) { if(N < primes[i] && primes[i] <= 2*N) ++cnt; } cout << cnt << endl; } return 0; }
B
コーチの問題印刷がなかったため予定が崩れたので，とりあえずBも見てみる．書くだけっぽいのでこれも自分が書くことにした．
とりあえず書いたがサンプル通らない．開きカッコと閉じカッコを種類ごとに対応させるだけで，くくる範囲が交差するパターンを考えていなかったのが原因だったのでstackを使って書き直し．サンプル通ったので投げる．WA．終了後にstackが空になってるか判定してなかった……．修正してAC．
#include <iostream> #include <string> #include <stack> using namespace std; int main() { while(true) { string str; getline(cin, str); if(str == ".") break; stack<char> st; int maru, kado; bool valid = true; maru = kado = 0; for(int i = 0; i < str.size(); ++i) { switch(str[i]) { case '(': st.push('('); break; case ')': if(st.empty() || st.top() != '(') valid = false; if(!st.empty()) st.pop(); break; case '[': st.push('['); break; case ']': if(st.empty() || st.top() != '[') valid = false; if(!st.empty()) st.pop(); break; } } if(!st.empty()) valid = false; cout << (valid?"yes":"no") << endl; } return 0; }
C
id:eagletmtさんから問題説明聞く．Cにしては重い探索かと思ったが，電極が左上にしかないし問題規模も小さいから普通に全探索でいけそうと判断．実装をまかせてid:draftcodeさんとDを考える．
なんか間違ってinputを投げて1WAしたらしいがすぐにAC．GCJみたいにフォーマットがおかしいファイルはVerifyして弾いてくれる（そもそも採点に使わない）システムにしてほしいなぁ．
D
id:draftcodeさんから概要を聞く．チップが4色*6枚で高々24枚しかないので，状態数はどんなに大きくても224．各状態からどのチップを取るかは最大で5C2*4になるけど，状態も全部が有効なわけじゃないしICPCだから-O2かけて実行すりゃいいやということでそのまんまDijkstra．
状態番号から有効なチップを求める処理がちょっと効率悪いが，とりあえずサンプルが通るものができたので投げる．最大ケースで数秒かかったけど一発AC．
#include <iostream> #include <vector> #include <algorithm> #include <complex> #include <cmath> #include <queue> using namespace std; typedef complex<int> Point; struct Circle { Point center; int r; int color; Circle() {} Circle(const Point &c, int r, int clr) : center(c), r(r), color(clr) {} bool intersect(const Circle &other) const { return norm(center - other.center) < (r+other.r)*(r+other.r); } }; int main() { while(true) { int N; cin >> N; if(!N) break; vector<vector<int> > on(N); vector<int> refered(N, 0); vector<Circle> chips; for(int i = 0; i < N; ++i) { int x, y, r, c; cin >> x >> y >> r >> c; --c; Circle chip(Point(x, y), r, c); for(int j = 0; j < i; ++j) { if(chips[j].intersect(chip)) { on[j].push_back(i); refered[i]++; } } chips.push_back(chip); } vector<int> memo(1<<24, -1); priority_queue<pair<int,int> > q; q.push(make_pair((1<<N)-1, 0)); int ans = 0; while(!q.empty()) { const int state = q.top().first; const int num = q.top().second; q.pop(); if(memo[state] != -1) continue; memo[state] = num; ans = max(ans, num); vector<int> ref_buf = refered; vector<vector<int> > enabled(4); for(int s = state, idx = 0; s; s >>= 1, ++idx) { const int b = s&1; if(b == 0) { for(int i = 0; i < on[idx].size(); ++i) { int to = on[idx][i]; --ref_buf[to]; } } } for(int i = 0; i < N; ++i) { if(ref_buf[i] == 0 && (state&(1<<i))) { const Circle &c = chips[i]; enabled[c.color].push_back(i); } } for(int i = 0; i < enabled.size(); ++i) { const vector<int> &v = enabled[i]; if(v.size() < 2) continue; vector<int> chk(v.size(), 0); chk[0] = chk[1] = 1; reverse(chk.begin(), chk.end()); do { vector<int> sel; for(int i = 0; i < chk.size(); ++i) if(chk[i]) sel.push_back(v[i]); int ns = state & ~((1<<sel[0]) | (1<<sel[1])); if(memo[ns] < num+2) q.push(make_pair(ns, num+2)); } while(next_permutation(chk.begin(), chk.end())); } } cout << ans << endl; } return 0; }
E
EとFの問題概要を聞いて，幾何を二人で考えてもしょうがなさそうなのでEを自分とid:draftcodeさん，Fをid:eagletmtさんが考えることに．
Eの制約条件を理解するのにちょっと時間がかかる．最小値の最大化っぽいので二分探索かと思ったが，グループ数の最大化を優先しないといけないので違う．いろいろ考えてたら，任意の矩形領域について最大の分割をDPすればいいことに気づく．id:draftcodeさんと細かい条件を確認しながらチェックし，コーディング．
@ymzk000さんがめんどい構造にはアクセサ作るって言ってたのを思い出しつつ，DP配列のアクセサと累積和のアクセサを書く．ペアプロのおかげでミスが抑制できて，添字の操作とかバグの混入しやすいところを上手く書けた．
サンプルが通ったのでデータセット落として実行して，ちょっと不安なので最初のケースの検算．合ってる．投げる．AC！
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <utility> using namespace std; int dp[32][32][32][32]; int best[32][32][32][32]; int visited[32][32][32][32]; int integral[32][32]; int H, W, S; int ALL_VAL; inline void sel_max(int &ref, int val) { if(ref < val) ref = val; } inline int get_integral(int r, int c) { if(r < 0 || H <= r || c < 0 || W <= c) return 0; return integral[r][c]; } inline int get_integral_region(int top, int left, int bottom, int right) { int val = get_integral(bottom,right) - get_integral(bottom,left-1) - get_integral(top-1, right) + get_integral(top-1, left-1); return val; } inline int isok(int top, int left, int bottom, int right) { return get_integral_region(top, left, bottom, right) >= get_integral(H-1, W-1) - S; } pair<int,int> rec(int top, int left, int bottom, int right) { if(visited[top][left][bottom][right]) return make_pair(dp[top][left][bottom][right], best[top][left][bottom][right]); //assume args are valid(isok returns true) dp[top][left][bottom][right] = 1; best[top][left][bottom][right] = get_integral_region(top, left, bottom, right); for(int tb = top; tb < bottom; ++tb) { if(!isok(top, left, tb, right) || !isok(tb+1, left, bottom, right)) continue; const pair<int,int> res1 = rec(top, left, tb, right); const pair<int,int> res2 = rec(tb+1, left, bottom, right); int ngroups = res1.first + res2.first; int yojo = min(res1.second, res2.second); if(ngroups == dp[top][left][bottom][right]) { sel_max(best[top][left][bottom][right], yojo); } else if(ngroups > dp[top][left][bottom][right]) { dp[top][left][bottom][right] = ngroups; best[top][left][bottom][right] = yojo; } } //copype for(int lr = left; lr < right; ++lr) { if(!isok(top, left, bottom, lr) || !isok(top, lr+1, bottom, right)) continue; const pair<int,int> res1 = rec(top, left, bottom, lr); const pair<int,int> res2 = rec(top, lr+1, bottom, right); int ngroups = res1.first + res2.first; int yojo = min(res1.second, res2.second); if(ngroups == dp[top][left][bottom][right]) { sel_max(best[top][left][bottom][right], yojo); } else if(ngroups > dp[top][left][bottom][right]) { dp[top][left][bottom][right] = ngroups; best[top][left][bottom][right] = yojo; } } visited[top][left][bottom][right] = 1; return make_pair(dp[top][left][bottom][right], best[top][left][bottom][right]); } int main() { ios::sync_with_stdio(0); while(true) { cin >> H >> W >> S; if(!H && !W && !S) break; vector<vector<int> > u(H, vector<int>(W)); for(int r = 0; r < H; ++r) { for(int c = 0; c < W; ++c) { cin >> u[r][c]; } } memset(dp, 0, sizeof(dp)); memset(best, 0, sizeof(best)); memset(visited, 0, sizeof(best)); memset(integral, 0, sizeof(integral)); integral[0][0] = u[0][0]; for(int r = 0; r < H; ++r) { for(int c = 0; c < W; ++c) { int pr = r-1 >= 0 ? integral[r-1][c] : 0; int pc = c-1 >= 0 ? integral[r][c-1] : 0; int prpc = (r-1>=0 && c-1>=0) ? integral[r-1][c-1] : 0; integral[r][c] = pr + pc - prpc + u[r][c]; } } ALL_VAL = get_integral_region(0, 0, H-1, W-1); const pair<int,int> ans = rec(0, 0, H-1, W-1); cout << ans.first << ' ' << ans.second - (ALL_VAL - S) << endl; } }
F
id:eagletmtさんから方針を聞く．どうも場合分け+円弧の交差を求めるという強実装らしい．いろいろな条件とか交差判定とか確認して，id:eagletmtさんが実装を開始．が，途中まで書いて合ってるか確かめるとどうも答えが合わない．そのままバグが取り切れず時間切れ．
総評
5問解けたのは純粋に嬉しい．ただ，後でG考えてみたら割とあっさり解けそうだったのでFに固執してしまったのはミスだった（E通した時点で1時間あったので，Gを0から考えたとしても思いつけるはず）．
あと2WAがちょっと痛い．1WA少なければ7位に入れたっぽい．上でも書いたけど，提出ミスを防ぐためにも不正なoutputは弾くようにしてほしいなぁ．
なにはともあれアジア地区に駒を進めることはできたので，良い結果を残せるように精進しなくては．
