JOI予選参加記
6問目が例年よりかなり簡単だったみたいです。
結果
全完でした。本選が本当の地獄となるでしょう。
日記
予選が始まる前におやつと野菜ジュース500mlを買ってきました。
500mlの野菜ジュースを探すのが非常に難しかったです。
開始直後はまず5問目を読み、思ったより楽そうだったのでその後6問目を読みました。
6問目も易化していたおかげで頑張って実装しきり、バグるなどして確かここまでで1時間20分前後でした。
かなり時間をかけてしまいましたが、無事6問目の実装が終わったおかげで安心して5問目以下に取り組めました。
上から順番に解いていったので3問目以下を解くときがとても楽しかったです(こなみ)。
ただ、4問目は例年と傾向が違いそうだったので一瞬冷や汗をかかせてくれました。
バグや時間不足が怖かったので、全体的に安全で低速なプログラムを書いた感じです。
解法とコード
1問目
はい。
#include<bits/stdc++.h> using namespace std; #define int long long int A[4], B[2]; signed main() { int sum = 0; for (int i = 0; i < 4; i++) cin >> A[i], sum += A[i]; for (int i = 0; i < 2; i++) cin >> B[i], sum += B[i]; sort(A, A + 4); sort(B, B + 2); printf("%lld\n", sum - A[0] - B[0]); return 0; }
2問目
はい。
#include<bits/stdc++.h> using namespace std; #define int long long int N, M, A[100]; signed main() { cin >> N >> M; for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 1; i <= M; i++) { for (int j = 0; j < N - 1; j++) { if (A[j]%i > A[j + 1]%i) swap(A[j], A[j + 1]); } } for (int i = 0; i < N; i++) { printf("%lld\n", A[i]); } return 0; }
3問目
はい。
#include<bits/stdc++.h> using namespace std; #define int long long const int INF = LLONG_MAX/2; int N, M; char fld[50][50]; int CountDiff(int a, int b, char c) { int res = 0; for (int i = a; i < b; i++) { for (int j = 0; j < M; j++) { if (fld[i][j] != c) res++; } } return res; } signed main() { cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> fld[i][j]; } } int ans = INF; for (int i = 1; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { ans = min(ans, CountDiff(0, i, 'W') + CountDiff(i, j, 'B') + CountDiff(j, N, 'R')); } } printf("%lld\n", ans); return 0; }
4問目
考えるのが面倒だったので、計算量を犠牲にしてで解きました。
実際はつらら(過去問)みたいにしてでいけます。
#include<bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 100000, MAX_Q = 1000; int N, T, Q, A[MAX_N], D[MAX_N], X[MAX_Q]; int Find(int x, int d) { for (int i = x; 0 <= i && i < N; i += d) { if (D[i] != d) return i; } return -1; } signed main() { vector<int> a1, a2; cin >> N >> T >> Q; for (int i = 0; i < N; i++) { cin >> A[i] >> D[i]; D[i] = (D[i] == 1) ? 1 : -1; } for (int i = 0; i < Q; i++) { cin >> X[i]; X[i]--; int x = Find(X[i], D[X[i]]); if (x == -1) { printf("%lld\n", A[X[i]] + T*D[X[i]]); continue; } int y = Find(x, D[x]); if (X[i] == y) { int t = abs(A[X[i]] - A[x])/2; printf("%lld\n", (t <= T) ? (A[X[i]] + A[x])/2 : A[X[i]] + T*D[X[i]]); continue; } int t = abs(A[X[i]] - (A[x] + A[y])/2); printf("%lld\n", (t <= T) ? (A[x] + A[y])/2 : A[X[i]] + T*D[X[i]]); } return 0; }
5問目
幅+ダイクストラでです。
#include<bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 100000; const int INF = LLONG_MAX/2; struct Data { int v, cost; Data() {} Data(int _v, int _cost) { v = _v; cost = _cost; } bool operator < (const Data &a) const { return cost > a.cost; } }; int N, M, K, S, P, Q, C[MAX_N]; vector<int> edge[MAX_N]; int isDanger[MAX_N]; void BFS() { queue<pair<int, int> > q; for (int i = 0; i < K; i++) { q.push(make_pair(C[i], 0)); } bool isUsed[MAX_N] = {}; while (!q.empty()) { pair<int, int> f = q.front(); q.pop(); if (f.second > S) return; if (isUsed[f.first]) continue; isUsed[f.first] = true; isDanger[f.first] = ((f.second == 0) ? 2 : 1); for (int i = 0; i < edge[f.first].size(); i++) { q.push(make_pair(edge[f.first][i], f.second + 1)); } } } int Dijkstra() { priority_queue<Data> q; q.push(Data(0, 0)); bool d[MAX_N] = {}; while (!q.empty()) { Data t = q.top(); q.pop(); if (t.v == N - 1) return t.cost; if (d[t.v]) continue; d[t.v] = true; if (t.v > 0) t.cost += (isDanger[t.v] == 0) ? P : Q; for (int i = 0; i < edge[t.v].size(); i++) { if (isDanger[edge[t.v][i]] == 2) continue; q.push(Data(edge[t.v][i], t.cost)); } } } signed main() { cin >> N >> M >> K >> S >> P >> Q; for (int i = 0; i < K; i++) { cin >> C[i]; C[i]--; } for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; edge[a].push_back(b); edge[b].push_back(a); } BFS(); printf("%lld\n", Dijkstra()); return 0; }
6問目
bitDPを書こうとするとif文まみれになりそうで怖かったのでメモ化再帰で解きました。
8近傍全部の「屋台で買ったか」という情報を保存して、実際には 右上、上、今いる場所、左、左下 の5地点だけをメモすることで実装しやすくしました。(でも汚い)
しかしよく考えたら今いる場所は絶対買わなければいけないのでメモする必要がなかったです。
の定数がかかっていますが
です。
#include<bits/stdc++.h> using namespace std; #define int long long const int MAX_H = 1000, MAX_W = 1000; const int INF = LLONG_MAX/2; const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; const int ex[5] = {1, 0, 1, 0, 2}, ey[5] = {1, 1, 0, 2, 0}; int H, W; char fld[MAX_H][MAX_W]; int memo[MAX_H][MAX_W][1 << 5]; void Move(bool s[3][3], int dir) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { int nx = j + dx[dir], ny = i + dy[dir]; if (nx < 3 && ny < 3) s[i][j] = s[ny][nx]; else s[i][j] = false; } } } int ToKey(bool s[3][3]) { int res = 0; for (int i = 0; i < 5; i++) { if (s[ey[i]][ex[i]]) res = res | (1 << i); } return res; } bool IsOutside(int x, int y) { return x < 0 || W <= x || y < 0 || H <= y; } int DFS(int x, int y, bool s[3][3]) { int key = ToKey(s); if (memo[y][x][key] != INF) return memo[y][x][key]; int c = 0; if (fld[y][x] != '.' && !s[1][1]) { c = fld[y][x] - '0'; s[1][1] = true; } vector<int> yatai; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (IsOutside(nx, ny)) continue; if (fld[ny][nx] == '.' || s[dy[i] + 1][dx[i] + 1]) continue; yatai.push_back(i); } for (int i = 0; i < max((unsigned)1, yatai.size()); i++) { int c_ = c; bool ns[3][3]; memcpy((bool*)ns, (bool*)s, sizeof(bool)*3*3); for (int j = 0; j < yatai.size(); j++) { if (i == j) continue; ns[dy[yatai[j]] + 1][dx[yatai[j]] + 1] = true; c_ += fld[y + dy[yatai[j]]][x + dx[yatai[j]]] - '0'; } if (x == W - 1 && y == H - 1) return c_; for (int j = 0; j < 2; j++) { int nx = x + dx[j], ny = y + dy[j]; if (IsOutside(nx, ny)) continue; bool ns_[3][3] = {}; memcpy((bool*)ns_, (bool*)ns, sizeof(bool)*3*3); Move(ns_, j); memo[y][x][key] = min(memo[y][x][key], DFS(nx, ny, ns_) + c_); } } return memo[y][x][key]; } signed main() { fill((int*)memo, (int*)memo + MAX_H*MAX_W*(1 << 5), INF); cin >> H >> W; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cin >> fld[i][j]; } } bool s[3][3] = {}; printf("%lld\n", DFS(0, 0, s)); return 0; }
