JOI予選 2012-2013
順当にいけば104点だと思います.
(2以外の)解答も載せるので良ければ参考にしてください.
一応ソースや解答, validationのために作ったプログラムは
http://www1.axfc.net/uploader/so/2717504
に置いています.
1.
解法 :
答えは L - max(国語を終わる日数, 算数をおわる日数)で, それぞれの切り上げを忘れない様に引き算を行う.
#include <cstdio> #include <algorithm> using namespace std; typedef __int64 lint; int main() { int L, a, b, c, d; scanf("%d %d %d %d %d", &L, &a, &b, &c, &d); printf("%d\n", L - max((a + c - 1) / c, (b + d - 1) / d)); return (0); }
13 5 27 3 9
2.
解法 : バケットを作って, 実際に1つしかないかを各ターン毎に見ていく.
#include <cstdio> #include <cstring> using namespace std; typedef __int64 lint; int main() { int n; int a[200][3]; int occ[101][3]; int point[200]; scanf("%d", &n); memset(occ, 0, sizeof(occ)); for (int i = 0; i < n; i++){ for (int j = 0; j < 3; j++){ scanf("%d", &a[i][j]); occ[a[i][j]][j]++; } } memset(point, 0, sizeof(point)); for (int i = 0; i < n; i++){ for (int j = 0; j < 3; j++){ point[i] += (occ[a[i][j]][j] == 1 ? a[i][j] : 0); } } for (int i = 0; i < n; i++) printf("%d\n", point[i]); return (0); }
3.
解法 : ずらす量と先頭位置を決めて全探索すれば良い. 境界が怖いので配列を大きく取ってごまかした(が、実際は長さと比べて適切にbreakすれば良い.
#include <cstdio> #include <cstring> using namespace std; typedef __int64 lint; int main() { int n; int len; char name[32]; int ans = 0; scanf("%d", &n); scanf("%s", name); len = strlen(name); for (int i = 0; i < n; i++){ static char query[10240]; int qlen; memset(query, -1, sizeof(query)); scanf("%s", query); qlen = strlen(query); for (int dx = 1; dx <= 34; dx++){ for (int pos = 0; pos < qlen; pos++){ bool ok = true; int k = 0; for (int p = pos; k != len; p += dx){ if (name[k] != query[p]){ ok = false; break; } k++; } if (ok){ ans++; goto next; } } } next:; } printf("%d\n", ans); return (0); }
7 11 63 42 47
4.
解法 : (日付, その日に来たシャツ)を状態としてもちDPをする. 2年前からの問4DPシリーズでは比較的取り組みやすいように感じた.
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef __int64 lint; int main() { int n, d; int dp[256][256]; //i日目に服jを着た時の最大値 int heat[256]; int mi[256], ma[256], val[256]; memset(dp, 0, sizeof(dp)); scanf("%d %d", &d, &n); for (int i = 1; i <= d; i++){ scanf("%d", heat + i); } for (int i = 0; i < n; i++){ scanf("%d %d %d", mi + i, ma + i, val + i); } for (int i = 2; i <= d; i++){ for (int j = 0; j < n; j++){ if (!(mi[j] <= heat[i] && heat[i] <= ma[j])) continue; for (int k = 0; k < n; k++){ if (!(mi[k] <= heat[i - 1] && heat[i - 1] <= ma[k])) continue; dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(val[j] - val[k])); } } } int ans = -1; for (int i = 0; i < n; i++) ans = max(ans, dp[d][i]); printf("%d\n", ans); return (0); }
235 409 18586 19556 19148
5.
扱う数の範囲に対して直方体の数が少ないので, 座標圧縮を行う.
その後に配列を塗りつぶし, K以上の数の直方体が被っている区間の大きさを足せば良い.
#include <cstdio> #include <cstring> #include <map> #include <vector> using namespace std; typedef __int64 lint; int main() { int N, K; static int cube[128][128][128]; int x1[64], x2[64], y1[64], y2[64], z1[64], z2[64]; vector<int> xs, ys, zs; map<int, int> convx, convy, convz; map<int, int> motox, motoy, motoz; scanf("%d %d", &N, &K); for (int i = 0; i < N; i++){ scanf("%d %d %d %d %d %d", x1 + i, y1 + i, z1 + i, x2 + i, y2 + i, z2 + i); xs.push_back(x1[i]); xs.push_back(x2[i]); ys.push_back(y1[i]); ys.push_back(y2[i]); zs.push_back(z1[i]); zs.push_back(z2[i]); } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); sort(zs.begin(), zs.end()); int idx = 0; convx[xs[0]] = idx; motox[idx++] = xs[0]; for (int i = 1; i < 2 * N; i++){ if (xs[i] != xs[i - 1]){ convx[xs[i]] = idx; motox[idx++] = xs[i]; } } idx = 0; convy[ys[0]] = idx; motoy[idx++] = ys[0]; for (int i = 1; i < 2 * N; i++){ if (ys[i] != ys[i - 1]){ convy[ys[i]] = idx; motoy[idx++] = ys[i]; } } idx = 0; convz[zs[0]] = idx; motoz[idx++] = zs[0]; for (int i = 1; i < 2 * N; i++){ if (zs[i] != zs[i - 1]){ convz[zs[i]] = idx; motoz[idx++] = zs[i]; } } for (int i = 0; i < N; i++){ //printf("%d %d %d %d %d %d\n", convx[x1[i]], convy[y1[i]], convz[z1[i]], convx[x2[i]], convy[y2[i]], convz[z2[i]]); for (int x = convx[x1[i]]; x < convx[x2[i]]; x++){ for (int y = convy[y1[i]]; y < convy[y2[i]]; y++){ for (int z = convz[z1[i]]; z < convz[z2[i]]; z++){ cube[x][y][z]++; } } } } lint ans = 0; for (int i = 0; i < 128; i++){ for (int j = 0; j < 128; j++){ for (int k = 0; k < 128; k++){ /*if (cube[i][j][k] >= K){ printf("!!\n"); printf("motox[i + 1] = %d motox[i] = %d motoy[j + 1] = %d motoy[j] = %d motoz[k + 1] = %d motoz[k] = %d\n", motox[i + 1], motox[i], motoy[j + 1], motoy[j], motoz[k + 1], motoz[k]); }*/ ans += (cube[i][j][k] >= K ? (lint)(motox[i + 1] - motox[i]) * (motoy[j + 1] - motoy[j]) * (motoz[k + 1] - motoz[k]) : 0); } } } printf("%I64d\n", ans); return (0); }
1801 347149566041429203 124015464949851877 991380998439054609 65264947770876113
6.
わからなかったので部分点狙いの再帰関数を書いた. 想定解法は直前の6手をもつbitDPらしいです. ほえ~
#include <cstdio> #include <algorithm> using namespace std; typedef __int64 lint; int w, h; char field[64][64]; bool vis[64][64][3]; int ans; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; void search(int ny, int nx, int left, int val) { if (ny == h - 1 && nx == w - 1){ ans = max(val, ans); if (left == 0) return; } for (int i = 0; i < 4; i++){ if (left == 0 && i >= 2) continue; int ty = ny + dy[i], tx = nx + dx[i]; if (ty < 0 || tx < 0 || ty >= h || tx >= w || field[ty][tx] == '#') continue; if ('1' <= field[ty][tx] && field[ty][tx] <= '9'){ int plus = field[ty][tx] - '0'; field[ty][tx] = '.'; //if (!vis[ty][tx][left - (i >= 2)]){ vis[ty][tx][left - (i >= 2)] = true; search(ty, tx, left - (i >= 2), val + plus); field[ty][tx] = plus + '0'; vis[ty][tx][left - (i >= 2)] = false; //} } else { //if (!vis[ty][tx][left - (i >= 2)]){ vis[ty][tx][left - (i >= 2)] = true; search(ty, tx, left - (i >= 2), val); vis[ty][tx][left - (i >= 2)] = false; //} } } return; } int main() { int k; scanf("%d %d %d", &h, &w, &k); for (int i = 0; i < h; i++){ scanf("%s", field[i]); } search(0, 0, k, 0); printf("%d\n", ans); return (0); }
21
?
?
?
?
去年からやってきたことが, 少しは実った気がするので良かったです.
本選にいけることを祈ります.