問題 A: 二匹のカエル

問題リンク：https://codeforces.com/contest/2055/problem/0

アプローチ:

アリスが先手で勝つ状況は、位置 a と b の距離が奇数の場合に限られます。

ACコード:

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 void process() {
5     long long n, p, q;
6     cin >> n >> p >> q;
7     if ((abs(p - q) % 2) == 1) {
8         cout << "YES\n";
9     } else {
10         cout << "NO\n";
11     }
12 }
13 
14 int main() {
15     ios::sync_with_stdio(false);
16     cin.tie(0);
17     int t = 1;
18     cin >> t;
19     while (t--) process();
20     return 0;
21 }

問題 C: トレイル

問題リンク：https://codeforces.com/contest/2055/problem/C

アプローチ:

最初のサンプルを参考にし、行列和 X を満たす方法を探します。この場合、X を仮定して経路上の要素を修正する必要があります。行または列に経路上の点が一つしかない場合、他の点の値を使ってその点の値を計算できます。

具体的には、隣接リストのようなデータ構造を使用して、各点の値を適切に設定します。

ACコード:

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 const int MAXN = 2e6 + 10;
5 int N, M;
6 int grid[2000][2000];
7 vector<int> row_set[MAXN], col_set[MAXN];
8 long long row_sum[MAXN], col_sum[MAXN];
9 
10 bool verify() {
11     set<long long> row_check, col_check;
12     for (int i = 1; i <= N; ++i) {
13         long long total = 0;
14         for (int j = 1; j <= M; ++j) {
15             total += grid[i][j];
16         }
17         row_check.insert(total);
18     }
19     for (int j = 1; j <= M; ++j) {
20         long long total = 0;
21         for (int i = 1; i <= N; ++i) {
22             total += grid[i][j];
23         }
24         col_check.insert(total);
25     }
26     return (row_check.size() == 1 && col_check.size() == 1 && *row_check.begin() == *col_check.begin());
27 }
28 
29 void adjust() {
30     string path;
31     cin >> N >> M >> path;
32     for (int i = 1; i <= N; ++i) {
33         for (int j = 1; j <= M; ++j) {
34             cin >> grid[i][j];
35             row_sum[i] += grid[i][j];
36             col_sum[j] += grid[i][j];
37         }
38         row_set[i].clear();
39     }
40     for (int j = 1; j <= M; ++j) {
41         col_set[j].clear();
42     }
43 
44     int x = 1, y = 1;
45     row_set[x].push_back(y);
46     col_set[y].push_back(x);
47     for (char c : path) {
48         if (c == 'D') x++;
49         else if (c == 'R') y++;
50         row_set[x].push_back(y);
51         col_set[y].push_back(x);
52     }
53 
54     while (!verify()) {
55         for (int i = 1; i <= N; ++i) {
56             if (row_set[i].size() == 1) {
57                 int j = row_set[i][0];
58                 grid[i][j] = -row_sum[i];
59                 col_sum[j] += grid[i][j];
60                 row_set[i].clear();
61                 col_set[j].erase(find(col_set[j].begin(), col_set[j].end(), i));
62             }
63         }
64         for (int j = 1; j <= M; ++j) {
65             if (col_set[j].size() == 1) {
66                 int i = col_set[j][0];
67                 grid[i][j] = -col_sum[j];
68                 row_sum[i] += grid[i][j];
69                 row_set[i].erase(find(row_set[i].begin(), row_set[i].end(), j));
70                 col_set[j].clear();
71             }
72         }
73     }
74     for (int i = 1; i <= N; ++i) {
75         for (int j = 1; j <= M; ++j) {
76             cout << grid[i][j] << " ";
77         }
78         cout << "\n";
79     }
80 }
81 
82 int main() {
83     ios::sync_with_stdio(false);
84     cin.tie(0);
85     int T = 1;
86     cin >> T;
87     while (T--) adjust();
88     return 0;
89 }