UAPC2011Summer
開催1時間前くらいに存在を知ってしまったので、修行の一環として出ることに。
解いた順に流れを追ってみます。
- -
A : Popularity Estimation
- 各時間で得られるポイントを調べてから、各キャラが得るポイントを調べるだけ
- 罠もなさそうだったので、さっくり実装したら通った
C : Time Manipulation
- Bメンドクセと思ってこっちに逃げてきた
- ノーラさん！ノーラさんじゃないか！
- 100年ものも結構レベルが必要だった気がするけど、2000000000年ものとかぱない
- m≦20だったので、はいはい包除原理包除原理と思ったらWAだった
- えー…と思って確かめてたら答えはn/2で良い気がしたので、それで通した
E : SAT-EN-3
- Dはハマりそうな予感がしたので逃げてきた(結果的にホントにDでハマった)
- 1個でも充足できる節があればyesで良い
- …ので、適当に調べて通した
F : Cosmic Market
- 最後の命令で動いた人は確定できるなぁ…
- その人達を抜けば最後から2つめの命令で動いた人も確定するなぁ…
- と思って後ろからクエリを処理してみたら通った
J : The Incubator
- HもIも解いてる人がいたので、ネタでJに飛んでみた
- なぜGも飛ばしたかは記憶が定かでない
- 問題文で不覚にも笑った
- 最終防衛かと思いきや、普通にBIT使えば間に合いそう
- x番目 : i-(i番目までで円環の理に導かれた人数) = x になる最小のi
- i番目までで円環の理に導かれた人数をBITで求める
- 実装してみたらサンプル通ったので、投げてみたら通った
I : 11224111122411
- DPで同じ数字が連続したときの場合の数を求めておくだけでは…
- と思ったけど、ループの処理にちょっと迷う
- 考えたところ、ループはいつ入っても良さそう
- ループなしでDPして、x文字使う場合の数 + x-5文字使う場合の数 + … を求めた
- さっくり実装したところ、サンプルの最後3つが合わない
- どういうこと…と思ったらMODがおなじみの1,000,000,007ではなく100,000,007だった
- 恐ろしい罠だった…。直したら通った
H : World domination
- ロックマンっぽい設定だし、各循環の中で誰を最初に倒すか決めれば良いのでは
- 各循環でスタート地点の数を調べ、コンビネーションで頑張れば場合の数も出そう
- 期待値は級数の和の公式を使ってこんな感じだろう…
- などと適当にやってたら期待値の立式が間違ってて酷くハマった
- サンプルが通ったところで投げてみたら無事にAC
B : High & Low Cube
- 左右反転と上下反転と90度回転と270度回転を実装して、問題の通りにゴリゴリ
- '-'と'|'の入れ替えとか無視しても良い気がしたものの、何となくやってみた
- 問題文から各数字のパターンをコピペして比較して数字を特定
- 数字さえ特定したら後はやるだけだったので、普通に通った
G : Everything Starts With Your Vote
- Dが通らなすぎて涙目だったので、こっちに逃げてきた
- 考えた結果、K位以内に入れる人数について二分探索することに
- 順位の高い人から貪欲に必要な分だけ順位を上げていけば必要な票数が求まる
- それがL以内に収まっているかどうかで判定
- 速い入力を使うべきというありがたい忠告を無視してcinを使ったけど通った
D : The Great Summer Contest
- 数学ゲーなら、MathとDP1問ずつ + Math or DP という感じの組合せだと思ってた
- 各種パラメータ(?)を調整しても一向にWAのまま
- ランダムケースを生成しまくったものの、反例も見つからず…
- 終盤で、ひょっとしてMathのみ or DPのみもアリなのでは‥と思って試す
- パラメータをゴニョゴニョしてた部分と上手く相互作用を起こしてACになった
- 今は反省している
- 結果的に8WAを記録して大惨事だった
- -
結果 6位(solved:10, time:1529)
| A | B | C | D | E | F | G | H | I | J |
| 6/0 | 205/0 | 39/1 | 293/8 | 52/0 | 62/0 | 279/0 | 173/0 | 127/0 | 107/0 |
Dが嘘な感じで通ってしまったものの、なんとか全完。
強い人たちがごっそりTCOに行ってしまった影響もありますが、
順位的には珍しく調子の良い感じだったのではという気がします。
以下，書いたコード一覧。(Dを除く)
A : Popularity Estimation
#include <iostream> #include <vector> #include <string> using namespace std; int main(){ int N; while(cin >> N, N){ string name[20]; vector< vector<int> > t(N); vector<int> pt(30, N+1); for(int i=0;i<N;i++){ cin >> name[i]; int m; cin >> m; for(int j=0;j<m;j++){ int d; cin >> d; t[i].push_back(d); pt[d]--; } } int idx = 0, mpt = 10000000; for(int i=0;i<N;i++){ int cur = 0; for(int j=0;j<t[i].size();j++) cur += pt[t[i][j]]; if(cur < mpt){ mpt = cur; idx = i; } else if(cur == mpt){ if(name[idx] > name[i]) idx = i; } } cout << mpt << " " << name[idx] << endl; } }
B : High and Low Cube
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; vector<string> revA(vector<string> vs){ vector<string> res = vs; for(int i=0;i<5;i++) reverse(res[i].begin(), res[i].end()); return res; } vector<string> revB(vector<string> vs){ vector<string> res = vs; for(int i=0;i<5;i++) for(int j=0;j<5;j++) res[4-i][j] = vs[i][j]; return res; } vector<string> rot90(vector<string> vs){ vector<string> res = vs; for(int i=0;i<5;i++) for(int j=0;j<5;j++){ res[4-j][i] = vs[i][j]; if(res[4-j][i]=='-') res[4-j][i] = '|'; else if(res[4-j][i]=='|') res[4-j][i] = '-'; } return res; } vector<string> rot270(vector<string> vs){ return rot90(rot90(rot90(vs))); } int getNum(vector<string> vs){ string num[5] = { ".......-....-.........-....-....-....-....-..", "...|....|....|..|.|..|....|......|..|.|..|.|.", ".......-....-....-....-....-.........-....-..", "...|..|......|....|....|..|.|....|..|.|....|.", "..-....-....-.........-....-.........-....-.." }; for(int i=0;i<10;i++){ bool ok = true; for(int j=0;j<5;j++) if(vs[j]!=num[j].substr(5*i,5)) ok = false; if(ok) return (i+1)%10; } return -1; } int main(){ string str[21]; int x[] = { 0, 7, 7, 7, 7, 14 }; int y[] = { 7, 0, 7, 14, 21, 7 }; while(cin >> str[0]){ if(str[0]=="0") break; for(int i=1;i<21;i++) cin >> str[i]; int num[2][6]; for(int i=0;i<2;i++){ for(int j=0;j<6;j++){ vector<string> vs(5); for(int k=0;k<5;k++) vs[k] = str[x[j]+k+1].substr(y[j]+29*i+1, 5); if(j==5) vs = revB(vs); vs = revA(vs); if(j==1) vs = rot90(vs); if(j==3) vs = rot270(vs); num[i][j] = getNum(vs); } } int win = 0; for(int i=0;i<6;i++){ for(int j=0;j<6;j++){ if(num[0][i] > num[1][j]) win++; if(num[0][i] < num[1][j]) win--; } } cout << (win < 0 ? "LOW" : "HIGH") << endl; } return 0; }
C : Time Manipulation
#include <iostream> using namespace std; int main(){ int n, m; int p[20]; while(cin >> n >> m, n){ bool ok = true; for(int i=0;i<m;i++){ cin >> p[i]; if(p[i]==1) ok = false; } printf("%.6lf\n", ok ? 0.5*n : 0); } return 0; }
E : SAT-EN-3
#include <iostream> #include <string> #include <cstring> using namespace std; bool ok(string &expr, int &idx){ int val[256]; memset(val, -1, sizeof(val)); int v = 0; bool res = true; while(expr[idx]!=')'){ if(expr[idx]=='&'){ idx++; continue; } if(expr[idx]=='~') v = 0, idx++; else v = 1; if(val[expr[idx]] != -1 && val[expr[idx]] != v) res = false; val[expr[idx]] = v; idx++; } idx++; return res; } int main(){ string expr; while(cin >> expr){ if(expr == "#") break; bool flg = false; for(int i=0;i<expr.size();i++){ flg |= ok(expr, i); } cout << (flg ? "yes" : "no") << endl; } return 0; }
F : Cosmic Market
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int main(){ int r, c, q; int A[50000], B[50000], ord[50000]; bool row[50000], col[50000]; while(cin >> r >> c >> q, r){ for(int i=0;i<q;i++) scanf("%d %d %d", &A[q-i-1], &B[q-i-1], &ord[q-i-1]); memset(row, false, sizeof(row)); memset(col, false, sizeof(col)); int lestR = r, lestC = c; long long res = 0; for(int i=0;i<q;i++){ if(A[i]==0){ if(row[B[i]]) continue; if(ord[i]==1) res += lestC; lestR--; row[B[i]] = true; } else { if(col[B[i]]) continue; if(ord[i]==1) res += lestR; lestC--; col[B[i]] = true; } } cout << res << endl; } }
G : Everything Starts With Your Vote
#include <iostream> #include <vector> #include <string> #include <cstdio> #include <set> #include <algorithm> using namespace std; int main(){ int N, M, K, L; while(cin >> N >> M >> K >> L, N){ vector< pair<int, string> > vp; for(int i=0;i<N;i++){ string str; int d; cin >> str >> d; vp.push_back(make_pair(-d, str)); } sort(vp.begin(), vp.end()); set<string> S; for(int i=0;i<M;i++){ string str; cin >> str; S.insert(str); } vector<int> rank; for(int i=0;i<N;i++) if(S.count(vp[i].second)) rank.push_back(i); int l = 0, h = min(M, K)+1; while(h-l>1){ int mid = (l+h)/2; int lest = mid; int against = K-mid; long long vote = 0; for(int i=0;i<mid;i++){ if(rank[i] <= against) against++; else { vote += -vp[against].first + vp[rank[i]].first + (vp[against].second < vp[rank[i]].second); } } if(vote > L) h = mid; else l = mid; } cout << l << endl; } }
H : World Domination
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; const int mod = 100000007; long long modpow(long long a, long long p){ if(p==0) return 1; long long res = modpow(a, p/2); res = (res*res)%mod; if(p%2==1) res = (res*a)%mod; return res; } int main(){ int n; double p[100], w[100]; int nxt[100]; double exp[100]; bool visit[100]; while(cin >> n, n){ for(int i=0;i<n;i++) cin >> p[i] >> nxt[i] >> w[i]; for(int i=0;i<n;i++){ visit[i] = false; exp[i] = 1 + (1-p[i])/p[i]; for(int j=nxt[i];j!=i;j=nxt[j]) exp[i] += 1 + (1-w[j])/w[j]; } double res = 0.0; long long pat = 1; int lest = n; for(int i=0;i<n;i++){ int cnt = 0; int mul = 1; double mx = 1e12; if(visit[i]) continue; for(int j=i;!visit[j];j=nxt[j]){ cnt++; visit[j] = true; if(mx > exp[j]) mul = 0, mx = exp[j]; if(abs(mx-exp[j]) < 1e-9) mul++; } res += mx; long long add = mul; for(int j=0;j<cnt;j++) add = (add*(lest-j))%mod; for(int j=0;j<cnt;j++) add = (add*modpow(j+1, mod-2))%mod; pat = (pat*add)%mod; lest -= cnt; } printf("%.10lf %d\n", res, pat); } return 0; }
I : 11224111122411
#include <iostream> #include <string> #include <cstdio> #include <cstring> using namespace std; int main(){ const int MOD = 100000007; int dpA[100001], dpB[100001]; memset(dpA, 0, sizeof(dpA)); memset(dpB, 0, sizeof(dpB)); dpA[0] = 1, dpB[0] = 1; for(int i=0;i<=100000;i++){ for(int j=1;j<=5;j++) if(i+j<=100000) dpA[i+j] = (dpA[i+j]+dpA[i])%MOD; } for(int i=0;i<=100000;i++){ for(int j=1;j<=3;j++) if(i+j<=100000) dpB[i+j] = (dpB[i+j]+dpB[i])%MOD; } int sumA[100001], sumB[100001]; memset(sumA, 0, sizeof(sumA)); memset(sumB, 0, sizeof(sumB)); for(int i=0;i<=100000;i++){ sumA[i] = dpA[i]; if(i-5>0) sumA[i] = (sumA[i]+sumA[i-5])%MOD; } for(int i=0;i<=100000;i++){ sumB[i] = dpB[i]; if(i-3>0) sumB[i] = (sumB[i]+sumB[i-3])%MOD; } string str; while(cin >> str){ if(str=="#") break; int idx = 0; long long res = 1; while(idx < str.size()){ int cur = str[idx]-'0'; int cnt = 0; while(idx < str.size() && str[idx]-'0' == cur) cnt++, idx++; if(cur == 0 || cur == 8) res = (res*sumB[cnt])%MOD; else res = (res*sumA[cnt])%MOD; } cout << res << endl; } }
J : The Incubator
#include <iostream> #include <cstdio> #include <cstring> #include <map> using namespace std; int bit[1<<19+1], n = 1<<19; int sum(int i){ int s = 0; for( ;i>0;i&=i-1) s += bit[i]; return s; } void add(int i, int x){ for( ;i<=n;i+=i&-i) bit[i] += x; } int getXth(int x, int end){ int L = 1, R = end; while(R-L>1){ int mid = (L+R)/2; int cur = mid - sum(mid); if(cur < x) L = mid; else if(x < cur) R = mid; else{ if(mid == 1 || mid-1-sum(mid-1) != cur) return mid; R = mid; } } return L; } int main(){ int q, lim; int id[400000]; while(cin >> q >> lim, q){ int end = 1, size = 0; map< int, int > mp; memset(bit, 0, sizeof(bit)); for(int Q=0;Q<q;Q++){ int query, x; scanf("%d %d", &query, &x); if(query == 0){ id[end] = x; mp[x] = end; end++; size++; } if(query == 1){ int idx = getXth(x, end); add(idx, 1); size--; } if(query == 2){ int idx = getXth(x, end); printf("%d\n", id[idx]); } if(query == 3){ int idx = mp[x]; add(idx, 1); size--; } while(size > lim){ int idx = getXth(1, end); add(idx, 1); size--; } } printf("end\n"); } }
