Peking University Online Judge 2229 Sumsets
memo1[i] : 2のべき乗数による i の分割のうち、1を含む分割の個数
memo2[i] : 1を含まない分割の個数
memo1[i] は、i - 1の分割に + 1をそのまま付け加えれば全列挙できるので、memo1[i] = memo1[i - 1] + memo2[i - 1]で表される。
memo2[i] は、例えばi = 8ならば8, 4 + 4, 4 + 2 + 2, 2 + 2 + 2 + 2の4個だが、すべての項を2で割ると4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1となり、これは4の分割の総数と等しくなる。よって、memo2[i] = memo1[i / 2] + memo2[i / 2](ただし、i が奇数の場合は0)
#include<cstdio> using namespace std; typedef long long int ll; static const int MAX_N = 1000000; static const ll MOD = 1000000000; int N; ll memo1[MAX_N + 1], memo2[MAX_N + 1]; int main(){ scanf("%d", &N); memo1[1] = 1; for(int i = 2; i <= N; i++){ memo1[i] = memo1[i - 1] + memo2[i - 1]; if(i % 2 == 0) memo2[i] = memo1[i / 2] + memo2[i / 2]; memo1[i] %= MOD; memo2[i] %= MOD; } printf("%lld\n", (memo1[N] + memo2[N]) % MOD); return 0; }
Peking University Online Judge 3669 Meteor Shower
今回は300×300の範囲から脱出してもOKだと気付かず。
問題文はちゃんと読まなきゃダメですね（いや絶対書き方悪いって）
#include<cstdio> #include<queue> #include<algorithm> using namespace std; static const int MAX_H = 300; static const int MAX_W = 300; static const int INF = 1 << 30; typedef pair<int, int> P; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; int M; int field[MAX_H + 2][MAX_W + 2]; int dist[MAX_H + 1][MAX_W + 1]; bool visited[MAX_H + 1][MAX_W + 1]; int bfs(int y, int x){ if(field[y][x] == INF) return 0; fill(visited[0], visited[MAX_H + 1], false); fill(dist[0], dist[MAX_H + 1], INF); queue<P> qa; qa.push(P(y, x)); visited[y][x] = true; dist[y][x] = 0; while(!qa.empty()){ P p = qa.front(); qa.pop(); int cy = p.first; int cx = p.second; for(int i = 0; i < 4; i++){ int ny = cy + dy[i]; int nx = cx + dx[i]; if(ny < 0 || nx < 0) continue; if(field[ny][nx] == INF) return dist[cy][cx] + 1; if(!visited[ny][nx] && field[ny][nx] > dist[cy][cx] + 1){ dist[ny][nx] = dist[cy][cx] + 1; visited[ny][nx] = true; qa.push(P(ny, nx)); } } } return -1; } int main(){ scanf("%d", &M); fill(field[0], field[MAX_H + 2], INF); for(int i = 0; i < M; i++){ int X, Y, T; scanf("%d %d %d", &X, &Y, &T); field[Y][X] = min(field[Y][X], T); for(int j = 0; j < 4; j++){ int ny = Y + dy[j]; int nx = X + dx[j]; if(ny < 0 || nx < 0) continue; field[ny][nx] = min(field[ny][nx], T); } } printf("%d\n", bfs(0, 0)); return 0; }
Peking University Online Judge 2376 Cleaning Shifts
これとんでもない回数WA出したんですけど、何故だと思います？
N = 2, T = 10, C = {(1, 5), (5, 10)} のケースは成立するけど、 N = 2, T = 10, C = {(1, 5), (6, 10)} のケースは成立しないと思ってたんですよ。
社会人ならシフト替わりの引継ぎなんか常識じゃないですか（お前競プロ向いてねえわ）
#include<cstdio> #include<algorithm> using namespace std; static const int MAX_N = 25000; struct Range{int start; int end;}; int N, T; Range c[MAX_N]; bool comp(const Range &a, const Range &b){ return a.start < b.start; } int main(){ scanf("%d %d", &N, &T); for(int i = 0; i < N; i++){ scanf("%d %d", &c[i].start, &c[i].end); } sort(c, c + N, comp); int res = 0; int s = 0; for(int i = 0; i < N; i++){ s++; if(s < c[i].start){ printf("-1\n"); return 0; } int next_s = c[i].end; while(c[i + 1].start <= s && i < N){ i++; next_s = max(next_s, c[i].end); } res++; s = next_s; if(s == T) break; } if(s != T) printf("-1\n"); else printf("%d\n", res); return 0; }
Aizu Online Judge 0121 seven puzzle
mapのkeyとしてvector
#include<iostream> #include<vector> #include<queue> #include<map> using namespace std; vector<int> va(8); int main(){ vector<int> vec(8); for(int i = 0; i < 8; i++) vec[i] = i; map<vector<int>, int> mpa; queue<vector<int> > qa; mpa[vec] = 1; qa.push(vec); while(!qa.empty()){ vector<int> vb = qa.front(); qa.pop(); for(int i = 0; i < 8; i++){ if(vb[i] == 0){ if(i != 0 && i != 4){ vector<int> vc = vb; swap(vc[i], vc[i - 1]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } if(i != 3 && i != 7){ vector<int> vc = vb; swap(vc[i], vc[i + 1]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } if(i >= 0 && i <= 3){ vector<int> vc = vb; swap(vc[i], vc[i + 4]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } if(i >= 4 && i <= 7){ vector<int> vc = vb; swap(vc[i], vc[i - 4]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } } } } while(cin >> va[0]){ for(int i = 1; i < 8; i++) cin >> va[i]; cout << mpa[va] - 1 << endl; } return 0; }
AtCoder Grand Contest 027 総括
結果は1問AC。最近パッとしませんな（ギャンブル提出を控えてWA連発を避けようとしている）
（身も蓋もないことを言うと、プライベートキツいんすよ（帰れ））
ペナ差は意外と怖い。順位表で近かった相手とどんどん離れていく感覚は辛いものがある
A問題 AC
発想はすぐ出ると思うけど、実装が意外と厄介な代物。特にN番目の要素あたりで余りが出る場合の処理に自信が無かった。
綺麗に実装しようと思わない方がいいかもしれない。
ACコード
#include<cstdio> #include<algorithm> using namespace std; typedef long long int ll; int N, x; int a[110]; int main(){ scanf("%d %d", &N, &x); for(int i = 0; i < N; i++) scanf("%d", &a[i]); sort(a, a + N); int res = 0; int i; for(i = 0; i < N; i++){ if(x < a[i]) break; res++; x -= a[i]; } if(x != 0 && x >= a[i]) res--; printf("%d\n", max(0, res)); return 0; }
ちなみにバグの取り方なんですけど、「サンプルがすべて合って、なおかつある程度確信があればいったん提出。」「それでもWAが出たら、バグりそうなケースを作る」の流れで最近はやっています。
きょうのWAコードはこれなんですけど、
#include<cstdio> #include<algorithm> using namespace std; typedef long long int ll; int N, x; int a[110]; int main(){ scanf("%d %d", &N, &x); for(int i = 0; i < N; i++) scanf("%d", &a[i]); sort(a, a + N); int res = 0; for(int i = 0; i < N; i++){ if(x < a[i]) break; res++; x -= a[i]; } if(x != 0) res--; printf("%d\n", max(0, res)); return 0; }
これだとN = 2, x = 99, a = {50, 50}でWAが出るので、「全員に配り切って、なおかつキャンディが余っている」場合のみres--の処理をするよう改造しました。
B問題 no submit
「これは頑張ったら出来るやろ！」と思って見てたら順位表の1ページ目ですら穴だらけ。
コメントはプロに任せます。
Peking University Online Judge 3009 Curling 2.0
見る人が見たら酷いコードなんだろうなという自覚はある。（ansをグローバルにする行為に敗北感が）
ともあれ蟻本の深さ優先探索についての練習問題は全完
#include<cstdio> #include<algorithm> using namespace std; static const int MAX_W = 20; static const int MAX_H = 20; static const int INF = 1 << 30; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; int w, h; int field[MAX_H][MAX_W]; int res; int sy, sx; void dfs(int y, int x, int cnt){ if(cnt > 10) return ; for(int i = 0; i < 4; i++){ if(field[y + dy[i]][x + dx[i]] == 1) continue; for(int j = 0;; j++){ int ny = y + dy[i] * j; int nx = x + dx[i] * j; if(ny < 0 || ny > h - 1 || nx < 0 || nx > w - 1) break; if(field[ny][nx] == 3){ res = min(cnt, res); return ; } else if(field[ny][nx] == 1){ field[ny][nx] = 0; dfs(ny - dy[i], nx - dx[i], cnt + 1); field[ny][nx] = 1; break; } } } return ; } int main(){ for(;;){ scanf("%d %d", &w, &h); if(w == 0 && h == 0) break; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ scanf("%d", &field[i][j]); if(field[i][j] == 2){ sy = i; sx = j; } } } res = INF; dfs(sy, sx, 1); printf("%d\n", (res == INF ? -1 : res)); } return 0; }
Peking University Online Judge 2236 Wireless Network
制限時間は10秒なので安心してください。
Union Find木、隣接リストを使って愚直に実装しても通ります。
#include<cstdio> #include<vector> #include<algorithm> using namespace std; static const int MAX_N = 1001; int N, D; int x[MAX_N], y[MAX_N]; vector<int> G[MAX_N]; bool fixed[MAX_N]; int par[MAX_N]; int rnk[MAX_N]; void init(int n){ for(int i = 0; i < n; i++){ par[i] = i; rnk[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(rnk[x] < rnk[y]){ par[x] = y; }else{ par[y] = x; if(rnk[x] == rnk[y]) rnk[x]++; } } bool same(int x, int y){ return find(x) == find(y); } int main(){ scanf("%d %d", &N, &D); for(int i = 0; i < N; i++) scanf("%d %d", &x[i], &y[i]); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(i == j) continue; if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= D * D){ G[i].push_back(j); G[j].push_back(i); } } } init(N); fill(fixed, fixed + N, false); for(;;){ char ch; if(scanf("%c", &ch) == EOF) break; if(ch == 'O'){ int p; scanf("%d", &p); p--; fixed[p] = true; for(int i = 0; i < G[p].size(); i++){ if(fixed[G[p][i]] == true) unite(p, G[p][i]); } }else if(ch == 'S'){ int p, q; scanf("%d %d", &p, &q); p--; q--; if(same(p, q)) printf("SUCCESS\n"); else printf("FAIL\n"); } } return 0; }
