Autumn Fest
結果 : ooox------- 30+50+60=140pts, 63rd.
感想 :
最後の一時間は参加していなかったものの、結局これ以上の点は望めなかったと思う. 実力通りかなあ.
結局答え聞いちゃえば分かるんだけど、閃かなかったら何にもならないし、それがコンテストなんだと思う.
あと、Dの埋め込みは思いついたけど不安でやらなかったので、取り敢えず次からは"思いついたことは(ある程度正当性を示して)できるだけ実装する"ことを心がけようと思う.
解答 :
A. 焦っていたので汚いです.
#include <cstdio> #include <algorithm> using namespace std; int main() { int N, T; int part[20], ptr[20]; pair<int, int> tbl[20][10]; scanf("%d %d", &N, &T); for (int i = 0; i < N; i++){ scanf("%d", &part[i]); } int idx; for (int i = 0; i < 2; i++){ idx = 0; for (int j = 0; j < N; j++){ for (int k = 0; k < part[j]; k++){ int t; scanf("%d", &t); if (i == 0){ tbl[j][k].first = t; } else { tbl[j][k].second = t; } } } } memset(ptr, -1, sizeof(ptr)); int res = 0; int time = 0; while (1){ int flg = true; for (int i = 0; i < N; i++){ if (ptr[i] + 1 != part[i]){ flg = false; break; } } if (flg) break; pair<int, int> mx = make_pair(10000, 10000); int pos = -1; for (int i = 0; i < N; i++){ if (ptr[i] + 1 != part[i] && mx.first > tbl[i][ptr[i] + 1].first){ mx = tbl[i][ptr[i] + 1]; pos = i; } } if (time + mx.second > T) break; else { ptr[pos]++; time += mx.second; } } for (int i = 0; i < N; i++){ if (~ptr[i]) res += tbl[i][ptr[i]].first; } printf("%d\n", res); return (0); }
B. 縦と横で累積和を取ってdfs. UnionFindでも良いらしい.
#include <cstdio> #include <algorithm> using namespace std; char str[128][128]; int h[128][128], w[128][128]; int H, W; bool v[128][128]; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; void dfs(int ty, int tx) { v[ty][tx] = true; for (int i = 0; i < 4; i++){ int mx = tx + dx[i], my = ty + dy[i]; if (0 <= mx && mx < W && 0 <= my && my < H && !v[my][mx] && str[my][mx] == str[ty][tx] && (w[my][mx] >= 3 || h[my][mx] >= 3)){ dfs(my, mx); } } } int main() { scanf("%d %d", &H, &W); for (int i = 0; i < H; i++) scanf("%s", &str[i]); for (int i = 0; i < W; i++) h[0][i] = 1; for (int i = 0; i < H; i++) w[i][0] = 1; for (int i = 0; i < H; i++){ for (int j = 1; j < W; j++){ w[i][j] = (str[i][j] == str[i][j - 1]) ? w[i][j - 1] + 1 : 1; } for (int j = W - 2; j >= 0; j--){ w[i][j] = (str[i][j] == str[i][j + 1]) ? w[i][j + 1] : w[i][j]; } } /* for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ printf("%d%c", w[i][j], j == W - 1 ? '\n' : ' '); } } */ for (int i = 0; i < W; i++){ for (int j = 1; j < H; j++){ h[j][i] = (str[j][i] == str[j - 1][i]) ? h[j - 1][i] + 1 : 1; } for (int j = H - 2; j >= 0; j--){ h[j][i] = (str[j][i] == str[j + 1][i]) ? h[j + 1][i]: h[j][i]; } } /* for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ printf("%d%c", h[i][j], j == W - 1 ? '\n' : ' '); } } */ int res = 0; for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ if (!v[i][j] && (h[i][j] >= 3 || w[i][j] >= 3)){ res++; dfs(i, j); } } } printf("%d\n", res); return (0); }
C. dpだったり数学だったりするらしい. ACした中では一番コードが短いです.
#include <cstdio> #define TEST (20000000) using namespace std; int main() { int N; int dat[20]; double res; scanf("%d", &N); int tot = 0; for (int i = 0; i < N; i++){ scanf("%d", &dat[i]); tot += dat[i]; } printf("%.7lf\n", tot * 1.0 / N * (N - 1)); return (0); }
D以降は、解けたら掲載します.