結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 Sqrt10
|
| 提出日時 | 2026-05-02 17:50:33 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,032 ms / 2,000 ms |
| コード長 | 7,159 bytes |
| 記録 | |
| コンパイル時間 | 3,579 ms |
| コンパイル使用メモリ | 355,404 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 1,890,667 |
| 最終ジャッジ日時 | 2026-05-02 17:52:10 |
| 合計ジャッジ時間 | 44,824 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:152:30: warning: 'si1' may be used uninitialized [-Wmaybe-uninitialized]
152 | cout << (si2 - si1) * (sj2 - sj1) << endl;
| ~~~~~^~~~~~
main.cpp:24:13: note: 'si1' was declared here
24 | int si1, si2, sj1, sj2;
| ^~~
main.cpp:152:30: warning: 'si2' may be used uninitialized [-Wmaybe-uninitialized]
152 | cout << (si2 - si1) * (sj2 - sj1) << endl;
| ~~~~~^~~~~~
main.cpp:24:18: note: 'si2' was declared here
24 | int si1, si2, sj1, sj2;
| ^~~
main.cpp:152:44: warning: 'sj1' may be used uninitialized [-Wmaybe-uninitialized]
152 | cout << (si2 - si1) * (sj2 - sj1) << endl;
| ~~~~~^~~~~~
main.cpp:24:23: note: 'sj1' was declared here
24 | int si1, si2, sj1, sj2;
| ^~~
main.cpp:152:44: warning: 'sj2' may be used uninitialized [-Wmaybe-uninitialized]
152 | cout << (si2 - si1) * (sj2 - sj1) << endl;
| ~~~~~^~~~~~
main.cpp:24:28: note: 'sj2' was declared here
24 | int si1, si2, sj1, sj2;
| ^~~
ソースコード
#include <bits/stdc++.h>
using namespace std;
int a[21][21] = {};
int s[22][22] = {};
int sum(int x1, int y1, int x2, int y2) { return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]; }
int main() {
int n, t;
cin >> n >> t;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + a[i][j];
}
}
int si1, si2, sj1, sj2;
int m = 0;
for (int i1 = 0; i1 < n; i1++) {
for (int i2 = i1 + 1; i2 <= n; i2++) {
for (int j1 = 0; j1 < n; j1++) {
for (int j2 = j1 + 1; j2 <= n; j2++) {
if ((i2 - i1) * (j2 - j1) <= t) {
int sum_ = sum(i1, j1, i2, j2);
if (sum_ > m) {
m = sum_;
si1 = i1;
si2 = i2;
sj1 = j1;
sj2 = j2;
}
}
}
}
}
}
double best_score = -1e18;
double best_alpha = 0.0;
vector<pair<int, int>> best_path;
for (double alpha = 0.2; alpha <= 0.9001; alpha += 0.05) {
vector<vector<bool>> visited(n, vector<bool>(n, false));
auto calc_c = [&](const vector<vector<bool>>& visited) {
vector<vector<double>> c(n, vector<double>(n, 0));
vector<double> pow_alpha(2 * n + 1, 1.0);
for (int d = 1; d <= 2 * n; d++) pow_alpha[d] = pow_alpha[d - 1] * alpha;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j]) continue;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (visited[x][y]) continue;
int d = abs(i - x) + abs(j - y);
c[i][j] += a[x][y] * pow_alpha[d];
}
}
}
}
return c;
};
auto c = calc_c(visited);
// (1) Find the cell with the largest c
int si = 0, sj = 0;
double maxc = -1e18;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (c[i][j] > maxc) {
maxc = c[i][j];
si = i;
sj = j;
}
}
}
int ci = si, cj = sj;
visited[ci][cj] = true;
vector<pair<int, int>> path;
path.emplace_back(ci, cj);
int moves = 1;
int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
double score = a[ci][cj];
while (moves < t) {
c = calc_c(visited);
int ni = -1, nj = -1;
double best = -1e18;
vector<pair<int, int>> candidates;
for (int d = 0; d < 4; d++) {
int ti = ci + di[d], tj = cj + dj[d];
if (ti < 0 || ti >= n || tj < 0 || tj >= n) continue;
if (visited[ti][tj]) continue;
int adj_visited = 0;
for (int dd = 0; dd < 4; dd++) {
int ai = ti + di[dd], aj = tj + dj[dd];
if (ai < 0 || ai >= n || aj < 0 || aj >= n) continue;
if (visited[ai][aj]) adj_visited++;
}
if (adj_visited < 3) {
if (c[ti][tj] > best) {
best = c[ti][tj];
ni = ti;
nj = tj;
}
} else {
candidates.emplace_back(ti, tj);
}
}
// If no "good" candidate, allow those with 3+ adjacent visited
if (ni == -1 && !candidates.empty()) {
for (auto [ti, tj] : candidates) {
if (c[ti][tj] > best) {
best = c[ti][tj];
ni = ti;
nj = tj;
}
}
}
if (ni == -1) break;
ci = ni;
cj = nj;
visited[ci][cj] = true;
path.emplace_back(ci, cj);
score += a[ci][cj];
moves++;
}
if (score > best_score) {
best_score = score;
best_alpha = alpha;
best_path = path;
}
}
if (best_score > m) {
// 出力
cout<<best_path.size() << endl;
for (auto [i, j] : best_path) {
cout << i << ' ' << j << endl;
}
} else {
cout << (si2 - si1) * (sj2 - sj1) << endl;
for (int i = si1; i < si2; i++) {
if ((si1 - i) % 2 == 0) {
for (int j = sj1; j < sj2; j++) {
cout << i << ' ' << j << endl;
}
} else {
for (int j = sj2 - 1; j >= sj1; j--) {
cout << i << ' ' << j << endl;
}
}
}
}
}