ACM-ICPC 2014 アジア地区予選東京大会 参加記
オリセンで開かれたICPCアジア地区予選に参加してきました.アジア地区予選に出場するのは個人でも学校でも初の経験でした.
結果は4完29位(大学別24位)でした.29位だったのでリクルートさんからNiku Awardをいただきましたありがとうございます.
チーム編成
- 僕(よわいソルバ)
- たこくん(ソルバ)
- マスコット(vimrc,テンプレート打ち込み,目diff,お茶くみ)
大体の流れ
開始前
前日からわかっていたことだが,周りが強豪ばっかでこわい.向かいがkatou(東工大),斜め前がprimasta(京大),右隣がnekonyaso(筑波),右斜め後ろがUTouto@Kyoto(東大)とかどんないやがらせですか...本番中みじめになる予感しかしない.
開始~AB解くまで
マスコットにvimrcとテンプレートを打ち込んでもらう.たこくんと一緒にA問題を読み,方針の確認.どうやら,前の方から詰めていくだけっぽい.たこくんに書いてもらうことにし,僕はB問題を読み始める...紙って配られないの?
B問題は構文解析しないといけない可能性も考えたが,左側から順番に計算する方法は単純なループで計算でき,掛け算を優先する方法は先に掛け算記号の処理をすればいい.結局その方針で解くことに.
A問題をたこくんがサブミット→WA.ちょっと時間がかかりそうだったので印刷して代わってもらう.Bを実装し提出,AC.たこくんが条件のミスを発見.訂正し提出→AC.
FとCを解くまで
AB正解したので僕はCを読み,たこくんには後ろの方からざっくりと問題を読んでもらうように指示を出す.
ここでC問題の読み間違えが起こり,依存関係が入口に遠い方から,入口に近い方にしかない(c < d)という条件を忘れてしまう(僕のミス1回目).「他のチームがいっぱい解いているのに,こんなに難しいの?」とか思ってた.ここでだいぶ時間を使ってしまう.
スコアボードを確認すると,Fを解いているチームが結構ある.詰まってしまったのでFを読んでみる.グラフっぽい問題,クラスカル+橋の列挙でいけるなぁと思い,たこくんにライブラリの打ち込みを頼む.(僕のミス2回目.マスコットにやってもらうべきだった)
たこくんがライブラリの入力を終了し,実装に移る.ここでふと気が付く.
「この二辺連結成分のライブラリ...どうやって使うんだっけ?」
幸い,うろ覚えの使い方でよかったのだが,ここで一気に混乱してしまい,実装がうまく進まない.
一端PCから離れて考え直したり,冷静になろうと思ってペットボトルで頭を殴ったりしてた.
ぐだぐだ悩みながら実装を行い,何とかAC.この段階でC問題を他のチームがかなり解いてる.
やっぱりCって簡単なんだよなーと思い,問題を読み直す.しばらくして,c < dの条件に気が付く.なんだC問題簡単じゃん→実装→AC.
後でコーチに聞いた話だと,Cを飛ばしてFを解き最下位争いをしている僕らのチームが一瞬取り上げられたらしい.
終わりまで
「軽食食ってきまーす.」と言って問題とともに去る.Gを解いているところが結構あったので,Gの解法を考えてみる.なんだかSegment Tree使いそうな気配がビンビンする.でもよくわからないなぁとか思ってた.
階乗に戻ると,たこくんがD問題をやっている.いろいろ質問されたが,変なことを言ってしまう(僕のミス3回目).ここでちゃんと対応していれば,5完できていたのですごく失敗だったと思う.
終了間際に,たこくんがDの実装を完了し,提出→WA.これは直せないかなーと思いながらも最後まであがくがACできず.
反省
初の参加で,かつ,全員開催日前後に何らかのタスクを抱えていて練習できてなかったのがつらかった.
そして,僕のワンマンチームだとずっと思い込んでいたのが失敗だった.たこくんをもっと有効活用してあげられたらもっと上を狙えたのかなぁと.完全に采配ミス.
目標の4完は達成できたのでよかった.しかし,順位では下から数えた方が圧倒的に早いので悔しい.
唯一の救いはリクルートさんがNiku Awardをくれたこと.
僕のわがままに付き合ってくれた,たこくん,マスコット(あおこ)さん,先生,ありがとうございました.肉がもらえるらしいので許してください.
来年からは,九大から参加することになる予定なので,足を引っ張らないように頑張りたいと思います.それまでにいっぱい練習しておかないと.
ICPC-JAG Day4 Problem F
解説では,Suffix Array + Range Minimum Queryでの解法が紹介されていましたが,僕はクエリ先読み + Aho-Corasick法で通しました.というか,Suffix Arrayよくわかってない.
ある人には,「クエリ先読みするなよ」と言われました.
概要
文字列SとQ個のクエリが与えられる.
i番目のクエリは2つの文字列x[i], y[i]で表現され,クエリに対してSの部分文字列の中でx[i]で始まりy[i]で終わるものを探す.
方針
クエリを先読みし,オートマトンをつくり,Sの中でx[i]が初めに出現するところと,y[i]が最後に出現するところを探す.
Sと全てのy[i]を前後逆にしてしまえば,両方とも全く同じアルゴリズムでよい.
Aho-Corasick法のマッチングを全部取っていくのは無駄.例えば,a, aa, aaa, ... みたいなケースが来たときに,aの判定を真面目にやると計算量が大きくなって時間的にもメモリ的にもつらい.これを改善するため,各状態について受理された文字列の判定は1回だけしか行わない.その時点で受理された文字列があるかの判定は,失敗したとき用のリンクを使って根か,既に判定済みの状態に到達するまでさかのぼることで行う.
ライブラリ写して,ちょっと手を加えて,簡単な実装やるだけだった.ライブラリになっているとはいえ,そこそこ実装コストがある.ただ,聞いた話だとSuffix Arrayも似たようなぐらいの実装量が必要になるらしい.そこにRMQの実装も加わるので,実装コストはこっちの方が若干軽いのかもしれない.
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define ALL(x) (x).begin(),(x).end() using namespace std; typedef long long ll; string S; int m; vector<string> vx, vy; struct PMA{ int id; PMA *next[30]; vector<int> accept; bool flag; PMA() { fill(next, next+30, (PMA*) NULL); flag = false; } }; void buildPMA(const vector<string> &words, vector<PMA*> &vp){ int n = words.size(); PMA *root = new PMA(); root -> id = 0; vp.push_back(root); int count = 1; for(int i = 0; i < n; ++i){ PMA* v = root; int m = words[i].size(); for(int j = 0; j < m; ++j){ int c = words[i][j] - 'a'+1; if(v->next[c] == NULL){ v->next[c] = new PMA; v->next[c] -> id = count++; vp.push_back(v->next[c]); } v = v->next[c]; } v->accept.push_back(i); } queue<PMA*> Q; root->next[0] = root; for(int c = 1; c < 27; ++c){ if(root->next[c] != NULL){ root ->next[c]->next[0] = root; Q.push(root->next[c]); } else root->next[c] = root; } while(!Q.empty()){ PMA *v = Q.front(); Q.pop(); for(int c = 1; c < 27; ++c){ if(v->next[c] != NULL) Q.push(v->next[c]); PMA *r = v->next[0]; while(r->next[c]==NULL) r = r->next[0]; if(v->next[c] != NULL) v->next[c] ->next[0] = r->next[c]; else v->next[c] = r->next[c]; } } } void searchfirst(const string &s, const vector<string> &word, vector<int> &r){ vector<PMA*> vp; buildPMA(word, vp); PMA *p = vp[0]; for(int i = 0; i < s.size(); ++i){ p = p->next[s[i]-'a'+1]; PMA *q = p; while(!(q->flag)){ EACH(j, q->accept){ r[*j] = i-word[*j].size() + 1; } q->flag = true; q=q->next[0]; } } } int main(){ cin >> S >> m; for(int i = 0; i < m; ++i){ string x, y; cin >> x >> y; reverse(ALL(y)); vx.push_back(x); vy.push_back(y); } vector<int> rx(m, -1), ry(m,-1); searchfirst(S, vx, rx); reverse(ALL(S)); searchfirst(S, vy, ry); for(int i = 0; i < m; ++i){ int idx = S.size()-ry[i]; if(idx < rx[i]+vx[i].size() || rx[i] < 0 || ry[i] < 0){ printf("0\n"); } else{ printf("%d\n", (S.size()-ry[i])-rx[i]); } } return 0; }
POJ 2441: Arrange the Bulls
概要
牡牛がN頭いて,M個のコートに1頭ずつ割り当てたい.
牡牛はそれぞれ好むコートが決まっている.
割り当て方は何通りあるか.
解法
bitDPやるだけ.
ただし,愚直に実装するとMLEを起こすはずなので,配列の再利用をする.
int N, M; int P[30]; int B[30][30]; int dp[2][1 << 20]; int main(){ scanf("%d%d", &N, &M); for(int i = 0; i < N; ++i){ scanf("%d", P+i); for(int j=0;j<P[i];++j){ scanf("%d", B[i]+j); --B[i][j]; } } memset(dp, 0, sizeof(dp)); int *prev = dp[0], *next = dp[1]; prev[0] = 1; for(int i = 0; i < N; ++i){ memset(next, 0, sizeof(dp[0])); for(int s = 0; s < (1 << M); ++s){ if(!prev[s]) continue; for(int j = 0; j < P[i]; ++j){ int f = 1 << B[i][j]; if(!(f & s)){ next[s | f] += prev[s]; } } } swap(prev, next); } int res = 0; for(int i = 0; i < (1 << M); ++i){ res += prev[i]; } printf("%d\n", res); return 0; }
POJ 2886: Who Gets the Most Candies?
POJ100問AC記念.
概要
N人の子供が一枚ずつカードを持っていて,輪になって並んでいる.
K番目の子供からスタートする.まず,現在選んでいる子供を輪から除外する.除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ.これを繰り返す.
i番目の操作で除外された子供は,iの約数の数だけキャンディをもらえる.
一番多くキャンディをもらえる子供は誰か.
解法
約数の個数は篩みたいにするとうまく計算できる.
子供を除外してずれる番号は,BITをうまく利用して管理する.
次に選ぶ子供はBIT上で二分探索をして求めることができる.
注意
同じ個数を得る子供は,先に輪の外に出た方を出力.
カードの番号が負の時の扱いに注意
const int MN = 500010; int N, K; int A[500010]; char name[500010][16]; int bit[500010]; bool isPrime[500010]; ll F[500010]; void update(int i, int v){ ++i; while(i <= N){ bit[i] += v; i += i & -i; } } int get(int i){ ++i; int res = 0; while(i>0){ res += bit[i]; i -= i & -i; } return res; } int find(int num){ int lb = -1, ub = N; while(ub - lb > 1){ int mid = (ub + lb) / 2; if(get(mid)-1 < num){ lb = mid; } else{ ub = mid; } } return ub; } void solve(){ memset(bit, 0, sizeof(bit)); for(int i=0;i<N;++i)update(i,1); int mx = 0, ridx = 0, idx = --K; for(int k=0;k<N;++k){ if(F[k+1] > mx){ mx = F[k+1]; ridx = idx; } update(idx, -1); if(k == N - 1) break; int num = N - k - 1; if(A[idx] > 0){ K = (K + A[idx] - 1) % num; }else{ K = (K + A[idx]) % num; } if(K < 0) K += num; idx = find(K); } printf("%s %d\n", name[ridx], mx); } main(){ for(int i = 0; i < MN; ++i) F[i] = 1; for(int i = 2; i < MN; ++i) if(!isPrime[i]){ for(int j = i; j < MN; j += i){ int k = 0; for(int l=j; l % i == 0; l /= i, ++k); isPrime[j] = true; F[j] *= k + 1; } } while(~scanf("%d%d", &N, &K)){ for(int i=0;i<N;++i){ scanf("%s%d", name+i, A+i); } solve(); } return 0; }
POJ2155: Matrix
概要
N次正方行列があり,初期状態ではすべての成分が0である.
T個のクエリが来て,内容は
- (x1,y1),(x2,y2)で定まる矩形領域に反転操作を行う.
- (x1,y1)の成分を答える
である.
解法
2次元のBITを用意する.これは,(1,1),(x,y)によって定まる矩形領域の値を合計したものを返す.
更新のときは,(x1,y1),(x1,y2+1),(x2+1,y1),(x2+1,y2+1)のそれぞれに1を加える.(中央二つは引き算のため.2を法とする演算であるから,加算と減算は等価である)
こうすると,(1,1),(x,y)の範囲の合計が(x,y)の値になる.
二次元平面上に矩形上に値vを足しこむとき,左下と右上にvをたし,左上と右下に-vを足しておいて最後にまとめて計算するテクニックをBITに応用したもの.
const int MAX_T = 50010; int X, N, T; int q[MAX_T]; int X1[MAX_T], Y1[MAX_T], X2[MAX_T], Y2[MAX_T]; int bit[1010][1010]; int get(int x, int y){ int res = 0; int tx = x; while(y>0){ x = tx; while(x>0){ res = (res + bit[y][x]) % 2; x -= x & -x; } y -= y & -y; } return res; } void update(int x, int y, int v){ int tx = x; while(y<=N){ x = tx; while(x<=N){ bit[y][x] = (bit[y][x] + v) % 2; x += x & -x; } y += y & -y; } } void solve(){ memset(bit, 0, sizeof(bit)); for(int i = 0; i < T; ++i){ if(q[i] == 'Q'){ int x = X1[i], y = Y1[i]; printf("%d\n", get(x, y)); } else{ update(X1[i], Y1[i], 1); update(X1[i], Y2[i]+1, 1); // v-1=v+1 (mod 2) update(X2[i]+1, Y1[i], 1); update(X2[i]+1, Y2[i]+1, 1); } } } int main(){ scanf("%d", &X); for(;X>0;--X){ scanf("%d%d", &N, &T); for(int i = 0; i < T; ++i){ char buf[8]; scanf("%s%d%d", buf, X1+i, Y1+i); q[i] = buf[0]; if(q[i] == 'C'){ scanf("%d%d", X2+i, Y2+i); } } solve(); if(X > 1) printf("\n"); } return 0; }
POJ 3109: Inner Vertices
概要
2次元格子上においてある黒い石の情報が与えられる.
ある格子点において,x方向,y方向共に黒い石に挟まれているならそこにも黒い石を置く.
最終的に格子上においてある黒い石の個数はいくつか?
解法
扱いやすいように座標圧縮をしておく.
各x座標について,そのx座標をもつ最小(最大)のy座標を計算.
y座標についても同様の操作を行う.この時,「同じy座標をもつ中で最小(最大)のx座標の点で線分の追加(削除)をする」というイベントにして管理する.
x座標の小さい方から,縦方向の範囲をBITに足しこむ.線分の追加・削除のところで点の個数をカウントするとうまくいく.
コードが雑で,変な使い回しをしているためわかりにくい.
typedef int Type; struct Fenwick{ vector<Type> bit; Fenwick(int n){ bit = vector<Type>(n + 1); } void update(int i, Type v){ int n = bit.size(); ++i; while(i <= n){ bit[i] += v; i += i & -i; } } Type get(int i){ Type res = 0; ++i; while(i > 0){ res += bit[i]; i -= i & -i; } return res; } }; int n, nx, ny; pair<int, int> p[200010]; int xl[100010], yl[100010]; int sx[100010], sy[100010]; int ex[100010], ey[100010]; Fenwick bit(100010); int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%d%d", xl+i, yl+i); p[i] = make_pair(xl[i], yl[i]); } sort(xl, xl+n); nx = unique(xl, xl+n) - xl; sort(yl, yl+n); ny = unique(yl, yl+n) - yl; for(int i = 0; i < n; ++i){ sx[i] = sy[i] = 200010; ex[i] = ey[i] = 0; } for(int i = 0; i < n; ++i){ p[i].first = lower_bound(xl, xl+nx, p[i].first) - xl; p[i].second = lower_bound(yl, yl+ny, p[i].second) - yl; sy[p[i].first] = min(sy[p[i].first], p[i].second); ey[p[i].first] = max(ey[p[i].first], p[i].second); sx[p[i].second] = min(sx[p[i].second], p[i].first); ex[p[i].second] = max(ex[p[i].second], p[i].first); } for(int i = 0; i < ny; ++i){ p[2*i] = make_pair(sx[i], i); p[2*i+1] = make_pair(ex[i], i+ny); } ll cnt = 0; int idx = 0; sort(p, p+ny*2); for(int i = 0; i < nx; ++i){ while(idx < ny * 2 && p[idx].first == i && p[idx].second < ny){ int y = p[idx].second; cnt -= bit.get(y); ++idx; } bit.update(sy[i], 1); bit.update(ey[i]+1, -1); while(idx < ny * 2 && p[idx].first == i){ int y = p[idx].second - ny; cnt += bit.get(y); ++idx; } } printf("%d\n", cnt); return 0; }
POJ 1990: MooFest
概要
一次元座標x[i]と,値v[i]が与えられる.iとjの間の通信コストはmax(v[i],v[j])*|x[i]-x[j]|である.コストの総和を求めよ
解法
座標でソートしておく.
各iについて,BITを用いてv[i]以下であるiより小さい場所の座標の総和とそのような場所の個数を計算する.
const int M = 20010; int N; pair<ll, ll> c[20010]; ll bit1[20010], bit2[20010]; void init(){ memset(bit1, 0, sizeof(bit1)); memset(bit2, 0, sizeof(bit2)); } pair<ll,ll> sum(int x){ ll r1 = 0, r2 = 0; while(x > 0){ r1 += bit1[x]; r2 += bit2[x]; x -= x & -x; } return make_pair(r1, r2); } void add(int x, ll v){ while(x < M){ bit1[x] += v; bit2[x] += 1; x += x & -x; } } main(){ scanf("%d", &N); for(int i = 0; i < N; ++i){ ll v, x; scanf("%lld%lld", &v, &x); c[i] = make_pair(x, v); } sort(c, c + N); ll res = 0LL; init(); for(int i=0;i<N;++i){ //printf("%lld,%lld\n", c[i].first, c[i].second); pair<ll, ll> r = sum(c[i].second); //printf("[%lld, %lld]\n", r.first, r.second); res += c[i].second * (r.second*c[i].first-r.first); add(c[i].second, c[i].first); } //printf("%lld\n", res); init(); for(int i=N-1;i>=0;--i){ pair<ll, ll> r = sum(c[i].second-1); res += c[i].second * (r.first-r.second*c[i].first); add(c[i].second, c[i].first); } printf("%lld\n", res); return 0; }