JOI 2011代表選抜 Day1, Day2 ソースコード
とりあえずコードだけ投げておこう
Day1 Banner
#include <cstdio> int H, W, map[400][400], in; int solve(int p, int q) { int t[8] = {0}; for(int i=0;i<W;i++){ int v = map[p][i] | map[q][i]; t[v]++; } int ret = 0; for(int i=0;i<8;i++){ for(int j=i+1;j<8;j++) if((i|j)==7){ ret += t[i] * t[j]; } } return ret; } int main() { scanf("%d%d", &H, &W); for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ scanf("%d", &in); map[i][j] = 1<<in; } } long long ret = 0; for(int i=0;i<H;i++){ for(int j=i+1;j<H;j++){ ret += solve(i, j); } } printf("%lld\n", ret); return 0; }
Day1 Dragon
このコードには間違いがあって、80点しか取れません
#include <cstdio> #include <algorithm> using namespace std; struct minimum { inline int operator()(int &a, int &b) { if(a > b) return b; return a; } }; struct maximum { inline int operator()(int &a, int &b) { if(a > b) return a; return b; } }; template<class T> class seg_tree { T comp; int *data[21], size[21], len, def; public: seg_tree(int N, int _def) { def = _def; len = 0; size[len++] = N; while(size[len-1] > 1){ size[len] = (size[len-1] + 1) / 2; len++; } for(int i=0;i<len;i++){ int ln = (size[i] + 1) / 2 * 2; data[i] = new int[ln]; for(int j=0;j<ln;j++) data[i][j] = def; } } int query(int left, int right) { int ret = def; for(int i=0;left!=right;i++){ if(left&1) ret = comp(ret, data[i][left++]); if(right&1) ret = comp(ret, data[i][--right]); left >>= 1; right >>= 1; } return ret; } void set(int pos, int val) { data[0][pos] = val; pos >>= 1; for(int i=1;i<len;i++){ data[i][pos] = comp(data[i-1][pos*2], data[i-1][pos*2+1]); pos >>= 1; } } }; int H, W, N, x[100000], y[100000]; int xs[100000], xLast, ys[100000], yLast; pair<int, int> st[100000]; struct action { int X, lp; }; inline bool operator<(const action& a, const action& b) { return a.X < b.X || (a.X == b.X && a.lp < b.lp); } action act[400000]; int aLast; long long solve() { for(int i=0;i<N;i++){ ys[i] = y[i]; xs[i] = x[i]; } sort(xs, xs+N); sort(ys, ys+N); xLast = unique(xs, xs+N) - xs; yLast = unique(ys, ys+N) - ys; long long ret = 0; aLast = 0; int xc = H, yc = W; for(int i=0;i<N;i++){ st[i] = make_pair(x[i], y[i]); } sort(st, st+N); int p = 0; for(;p<N;){ int p2 = p; while(p2 < N && st[p].first == st[p2].first) p2++; act[aLast].X = st[p].first; act[aLast].lp = st[p].second; aLast++; p = p2; xc--; } for(int i=0;i<N;i++){ st[i] = make_pair(y[i], x[i]); } sort(st, st+N); p = 0; for(;p<N;){ int p2 = p; while(p2 < N && st[p].first == st[p2].first) p2++; act[aLast].X = st[p].second; act[aLast].lp = st[p].first + 1000000001; aLast++; yc--; p = p2; } seg_tree<maximum> seg1(N, -1); sort(act, act + aLast); for(int i=0;i<N;i++){ seg1.set(i, i); } for(int i=0;i<aLast;i++){ if(act[i].lp > 1000000000){ int ps = lower_bound(ys, ys+yLast, act[i].lp - 1000000001) - ys; seg1.set(ps, -1); }else{ //about "left" int pl = lower_bound(ys, ys+yLast, act[i].lp) - ys; int tmp = seg1.query(0, pl); //printf("%d %d %d\n", act[i].X, act[i].lp, tmp); //if(act[i].X==1) continue; if(tmp==-1){ //only up //ret = max(ret, (long long)act[i].X - (upper_bound(xs, xs+xLast, act[i].X) - xs) - 1); if(pl>0 && ys[pl-1] == ys[pl]-1){ ret = max(ret, (long long)ys[pl] - pl - 1); }else{ ret = max(ret, (long long)ys[pl] - pl - 2); } }else{ ret = max(ret, (long long)act[i].X - (upper_bound(xs, xs+xLast, act[i].X) - xs) + ys[tmp] - tmp - 1); } } } ret += (long long)xc * yc; return ret; } void turnX() { for(int i=0;i<N;i++){ x[i] = H - x[i] + 1; } } void turnY() { for(int i=0;i<N;i++){ y[i] = W - y[i] + 1; } } void turnXY() { for(int i=0;i<N;i++){ swap(x[i], y[i]); } swap(W, H); } int main() { scanf("%d%d%d", &H, &W, &N); xLast = yLast = N; for(int i=0;i<N;i++){ scanf("%d%d", x+i, y+i); } long long ret = 0; ret = max(ret, solve()); turnX(); ret = max(ret, solve()); turnY(); ret = max(ret, solve()); turnX(); ret = max(ret, solve()); turnY(); turnXY(); ret = max(ret, solve()); turnX(); ret = max(ret, solve()); turnY(); ret = max(ret, solve()); turnX(); ret = max(ret, solve()); printf("%lld\n", ret); return 0; }
Day1 Joitter
#include <cstdio> #include <algorithm> using namespace std; int N, type[1000], cost[1000][1000]; void solve1() { int cnt = 0, ret = 0; for(int i=0;i<N;i++){ for(int j=i+1;j<N;j++){ if(type[i]==1 || type[j]==1){ ret += cost[i][j]; cnt++; } } } printf("%d %d\n", cnt, ret); } void solve2(int T) { if(T==2){ int v1=-1, v2=-1; for(int i=0;i<N;i++){ if(type[i]==2){ if(v1==-1) v1 = i; else v2 = i; } } int ret = cost[v1][v2]; for(int i=0;i<N;i++){ if(i != v1 && i != v2){ ret += min(cost[i][v1], cost[i][v2]); } } for(int i=0;i<N;i++){ int tmp = 0; for(int j=0;j<N;j++) if(i != j) tmp += cost[i][j]; ret = min(ret, tmp); } printf("%d %d\n", N-1, ret); }else{ int ret = 2100000000; for(int i=0;i<N;i++){ int tmp = 0; for(int j=0;j<N;j++) if(i != j) tmp += cost[i][j]; ret = min(ret, tmp); } printf("%d %d\n", N-1, ret); } } void solve3() { int ret = 0; int minc[1000]; bool visited[1000]; for(int i=0;i<N;i++){ minc[i] = 1000000; visited[i] = false; } minc[0] = 0; for(int i=0;i<N;i++){ int mp = -1; for(int j=0;j<N;j++) if(!visited[j] && (mp==-1 || minc[mp] > minc[j])){ mp = j; } visited[mp] = true; ret += minc[mp]; for(int j=0;j<N;j++){ minc[j] = min(minc[j], cost[mp][j]); } } printf("%d %d\n", N-1, ret); } int uf[1000]; pair<int, pair<int, int> > edge[5100000]; int end; int root(int p) { return (uf[p]<0)?p:(uf[p]=root(uf[p])); } bool join(int p, int q) { p = root(p); q = root(q); if(p==q) return false; uf[p] += uf[q]; uf[q] = p; return true; } void kruskal() { for(int i=0;i<N;i++) uf[i] = -1; end = 0; for(int i=0;i<N;i++){ for(int j=i+1;j<N;j++){ edge[end++] = make_pair(cost[i][j], make_pair(i, j)); } } sort(edge, edge+end); int ret = 0; for(int i=0;i<end;i++){ if(-uf[root(0)] == N) break; if(join(edge[i].second.first, edge[i].second.second)){ ret += edge[i].first; } } printf("%d %d\n", N-1, ret); } int main() { int ones=0, twos=0; scanf("%d", &N); for(int i=0;i<N;i++){ scanf("%d", type+i); if(type[i]==1) ones++; if(type[i]==2) twos++; } for(int i=0;i<N;i++){ for(int j=0;j<N;j++) scanf("%d", &(cost[i][j])); } if(ones>0){ solve1(); }else if(twos>0){ solve2(twos); }else{ solve3(); //kruskal(); } return 0; }
Day2 Guess Them All
#include <cstdio> #include <vector> using namespace std; int N, ret[100]; int output[100], one_pos; int query() { int rt; for(int i=0;i<N;i++) printf("%d\n", output[i]); fflush(stdout); scanf("%d", &rt); return rt; } bool determineX(int X) { vector<int> cand; for(int i=0;i<N;i++) if(ret[i]==-1) cand.push_back(i); int left=0, right=cand.size(); while(right-left > 1){ int mid = (left + right) / 2; int m2 = cand[mid]; for(int i=0;i<m2;i++) output[i] = X; for(int i=m2;i<N;i++) output[i] = 1; int q = query(); if(q==N) return true; if(m2 <= one_pos) q--; if(q==1){ right = mid; }else{ left = mid; } } ret[cand[left]] = X; return false; } int main() { scanf("%d", &N); if(N==1){ output[0] = 1; query(); return 0; } for(int i=0;i<N;i++) ret[i] = -1; for(int i=0;i<N;i++){ for(int j=0;j<N;j++) output[j] = 1; output[i] = 2; int q = query(); if(q==N) return 0; if(q==0){ one_pos = i; ret[one_pos] = 1; break; } } for(int i=2;i<=N;i++) if(determineX(i)) return 0; for(int i=0;i<N;i++) output[i] = ret[i]; query(); return 0; }
Day2 Keycards
#include <cstdio> #define MOD 1000000007 #define MAX 1000000 int N, K; long long invs[MAX+1]; long long kaijo[MAX+1], kaijo_inv[MAX+1]; long long inv(int X, long long M) { long long a=X, b=1; while(a>1){ long long t = M / a; b = (b * t) % M; a = M % a; b = (M - b) % MOD; } return b; } inline long long C(int a, int b) { return ((kaijo[a] * kaijo_inv[b])%MOD * kaijo_inv[a-b]) % MOD; } long long modpow(int X, long long Y, int M) { if(Y == 0) return 1; if(Y == 1) return X; long long tmp = modpow(X, Y/2, M); tmp = (tmp * tmp) % M; if(Y%2==1) tmp = (tmp * X) % M; return tmp; } int main() { scanf("%d%d", &N, &K); if(N == K){ printf("1\n"); return 0; } for(int i=1;i<=N;i++) invs[i] = inv(i, MOD); kaijo[0] = kaijo_inv[0] = 1; for(int i=1;i<=N;i++){ kaijo[i] = (kaijo[i-1] * i) % MOD; kaijo_inv[i] = (kaijo_inv[i-1] * invs[i]) % MOD; } long long ret = 0; long long mpw = 2; for(int i=0;i<=N-K;i++){ int sign = ((N-K-i)%2==0)?1:(-1); long long tmp = C(N-K, i); //tmp *= modpow(2, modpow(2, i, MOD-1), MOD); tmp *= mpw; mpw = (mpw * mpw) % MOD; tmp %= MOD; if(sign==1) ret = (ret + tmp) % MOD; else ret = (ret + MOD - tmp) % MOD; } ret *= C(N, K); ret %= MOD; printf("%lld\n", ret); return 0; }
Day2 Shiritori
下のコード中において、「strongness」なんていう英語は存在しません。正しくは「strength」です。
#include <cstdio> struct word { int v[5]; }; struct node { node* next; int val; }; int N, kind; char in[11]; word wd[500000]; int bg[100], ed[100], edge[100][100]; bool visited[100]; node* con[100][100]; node pool[500000]; int pl; bool strongness[100][100]; int uf[100]; int id[100], iLast; inline int root(int p) { return (uf[p]<0)?p:(uf[p]=root(uf[p])); } void join(int p, int q) { p = root(p); q = root(q); if(p==q) return; uf[p] += uf[q]; uf[q] = p; } void str_visit1(int p) { if(visited[p]) return; visited[p] = true; for(int i=0;i<kind;i++) if(edge[p][i]) str_visit1(i); id[iLast++] = p; } void str_visit2(int p, int id) { if(visited[p]) return; visited[p] = true; join(p, id); for(int i=0;i<kind;i++) if(edge[i][p]) str_visit2(i, id); } void determine_strongness() { iLast = 0; for(int i=0;i<kind;i++) visited[i] = false; for(int i=0;i<kind;i++) if(bg[i] || ed[i]){ str_visit1(i); } for(int i=0;i<kind;i++){ visited[i] = false; uf[i] = -1; } for(int i=iLast-1;i>=0;i--){ str_visit2(id[i], id[i]); } int bgs[100], eds[100]; for(int i=0;i<kind;i++) bgs[i] = eds[i] = 0; for(int i=0;i<kind;i++){ for(int j=0;j<kind;j++) if(edge[i][j]){ bgs[i]++; eds[j]++; } } int mg = -1; for(int i=0;i<kind;i++) if(bgs[i]==1 && eds[i]==0) mg = i; if(mg>=0 && uf[mg]<-1) mg = -1; for(int i=0;i<kind;i++){ for(int j=0;j<kind;j++){ strongness[i][j] = false; if(edge[i][j]){ if(root(i) == root(j)) strongness[i][j] = true; else if(mg>=0 && i==mg) strongness[i][j] = true; } } } } void _visit(int p) { if(visited[p]) return; visited[p] = true; for(int i=0;i<kind;i++) if(edge[p][i]) _visit(i); } bool test(int v) { for(int i=0;i<kind;i++) visited[i] = false; _visit(v); for(int i=0;i<kind;i++) if(!visited[i] && !(bg[i]==0&&ed[i]==0)) return false; return true; } void output(int k) { for(int i=0;i<5;i++){ printf("%02d", wd[k].v[i]); } puts(""); } int main() { scanf("%d", &N); for(int i=0;i<100;i++){ bg[i] = ed[i] = 0; for(int j=0;j<100;j++){ edge[i][j] = 0; con[i][j] = NULL; } } for(int i=0;i<N;i++){ scanf("%s", in); for(int j=0;j<5;j++){ wd[i].v[j] = (in[j*2]-'0')*10 + (in[j*2+1]-'0'); } bg[wd[i].v[0]]++; ed[wd[i].v[4]]++; edge[wd[i].v[0]][wd[i].v[4]]++; } for(int i=0;i<100;i++){ if(bg[i]>0 || ed[i]>0) kind = i+1; } pl = 0; for(int i=N-1;i>=0;i--){ pool[pl].next = con[wd[i].v[0]][wd[i].v[4]]; pool[pl].val = i; con[wd[i].v[0]][wd[i].v[4]] = &(pool[pl]); pl++; } int over_p = -1; for(int i=0;i<kind;i++){ if(bg[i]-ed[i]==0) continue; if(bg[i]-ed[i]==1){ if(over_p == -1) over_p = i; else goto bad; } if(bg[i]-ed[i]>1) goto bad; } if(over_p==-1){ over_p = wd[0].v[0]; } if(!test(over_p)) goto bad; determine_strongness(); for(int i=0;i<N;i++){ int nex = -1; for(int j=0;j<kind;j++){ if(edge[over_p][j]==0) continue; if(edge[over_p][j]>=2){ goto valid; }else if(strongness[over_p][j]){ goto valid; } continue; valid: if(nex==-1) nex = j; else if(con[over_p][nex]->val > con[over_p][j]->val) nex = j; continue; } output(con[over_p][nex]->val); con[over_p][nex] = con[over_p][nex]->next; edge[over_p][nex]--; bg[over_p]--; ed[nex]--; if(edge[over_p][nex]==0) determine_strongness(); over_p = nex; } return 0; bad: puts("impossible"); return 0; }