SMU Summer 2024 Contest Round 5
ロボット高橋君
思考プロセス
重み (W_i) でソートし、前後の 1 と 0 の個数を計算します。答えはおおよそ (\max(ans,pre_i+suf_{i+1})) の形式になります。
ソート後、(W_i = W_{i+1}) の場合、i と i+1 の間で分割できないため特別な処理が必要です。
コード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
vector<pair<int, int>> balls(n + 1);
for (int i = 1; i <= n; i++) {
cin >> balls[i].first;
balls[i].second = s[i] - '0';
}
sort(balls.begin() + 1, balls.end());
vector<int> prefix(n + 1), suffix(n + 2);
for (int i = 1; i <= n; i++)
prefix[i] = prefix[i - 1] + (!balls[i].second);
for (int i = n; i >= 1; i--)
suffix[i] = suffix[i + 1] + balls[i].second;
int result = 0;
for (int i = 0; i <= n; i++) {
if (balls[i].first != balls[i + 1].first) {
result = max(result, prefix[i] + suffix[i + 1]);
}
}
cout << result << '\n';
return 0;
}
6子連結
問題文
(N \times N) のグリッドがあり、(N) 行の文字列 (S_i) で表現されます。(S_{i,j}) が # ならば、その位置に駒があります。. ならば、駒がありません。
最大2個の駒を追加して、6個の駒が連続するライン（行、列、または対角線）を作れるか判定してください。
思考プロセス
全探索で判定します。
コード
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> board(n);
for (auto &row : board)
cin >> row;
bool possible = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i + 5 < n) { // 列方向
int count = 0;
for (int k = i; k <= i + 5; k++)
count += board[k][j] == '.';
possible |= count <= 2;
}
if (j + 5 < n) { // 行方向
int count = 0;
for (int k = j; k <= j + 5; k++)
count += board[i][k] == '.';
possible |= count <= 2;
}
if (i + 5 < n && j + 5 < n) { // 主対角線
int count = 0;
for (int k = 0; k <= 5; k++)
count += board[i + k][j + k] == '.';
possible |= count <= 2;
}
if (i - 5 >= 0 && j + 5 < n) { // 副対角線
int count = 0;
for (int k = 0; k <= 5; k++)
count += board[i - k][j + k] == '.';
possible |= count <= 2;
}
}
}
cout << (possible ? "Yes" : "No") << '\n';
return 0;
}
奇妙な玉
問題文
高橋君は (N) 個の奇妙な玉を受け取り、1列に並べています。各玉には数字が書かれており、(i) 番目の玉の数字は (a_i) です。
高橋君は玉を1から (N) の順番で桶に入れます。桶は円柱形で、底が閉じており、上からしか入れることができません。桶は狭く、玉はすべて縦に積み重ねられます。
高橋君が玉を入れていると、奇妙な現象が発生しました。もし桶の中に連続した (x) 個の値が (x) の玉がある場合、これらの玉は消滅します。
高橋君が1から (N) の順番で各玉を入れた後、桶の中に残っている玉の数を求めてください。
思考プロセス
スタックで各要素を記録し、cnt配列でスタックのトップ値の連続した個数を記録します。スタックのトップ値の連続個数が値と一致したら、対応する個数だけスタックからポップします。
コード
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> balls(n + 1);
for (int i = 1; i <= n; i++)
cin >> balls[i];
vector<int> stack, count(n + 1);
for (int i = 1; i <= n; i++) {
int size = stack.size();
if (size && balls[i] == stack.back())
count[size] = count[size - 1] + 1;
else
count[size] = 1;
stack.push_back(balls[i]);
if (count[size] == balls[i]) {
int k = balls[i];
while (k--)
stack.pop_back();
}
cout << stack.size() << '\n';
}
return 0;
}
線形探索
問題文
長さ (2^{20}) の数列 (a) を管理します。インデックスは 0 から (2^{20}-1) です。初期状態では各要素は (-1) です。(n = 2^{20}) とします。
(q) 回の操作が与えられます。各操作は以下の通りです：
1 x：変数 (h) の値を (x) に設定します。(a_{h \bmod n} = -1) になるまで (h) を1ずつ増やします。(a_{h \bmod n}) の値を (x) に設定します。2 x：(a_{x \bmod n}) の値を出力します。
思考プロセス
Union-Findの考え方を適用します。
まず、すべてのノードの親は自分自身です。自分が変更された場合、自分の親を右側で最初に (-1) でないノードを指すようにします。モジュロ演算とlong long、パス圧縮に注意してください。
コード
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int N = 1 << 20;
vector<ll> parent(N), arr(N, -1);
for (int i = 0; i < N; i++)
parent[i] = i;
function<int(int)> find = [&](int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
};
int q;
cin >> q;
while (q--) {
ll op, x;
cin >> op >> x;
if (op == 1) {
int y = find(x % N);
arr[y] = x;
parent[y] = find((y + 1) % N);
} else {
cout << arr[x % N] << '\n';
}
}
return 0;
}
赤いポリオミノ
問題文
(N \times N) の正方形グリッドが与えられます。# は黒いセル、. は白いセルを表します。白いセルから (K) 個を選んで赤く塗り、赤いセルが互いに接続（上下左右のみ）するようにしてください。可能な配置の数を求めてください。
思考プロセス
(N \times N) のマトリックスから (K) 個を選ぶ方法は最大で (C_{64}^8) 通りあります。全探索を考えます。
全探索には少し工夫が必要です。通常の全探索は赤いセルから周囲を探索しますが、方向の列挙によって答えが常に正しくならない可能性があります。代わりに、マップを走査して空白のセルから周囲の赤いセルを探すように考え直します。
コード
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<string> grid(n);
for (auto &row : grid)
cin >> row;
int answer = 0;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
function<void(int)> solve = [&](int num) {
if (num == k) {
answer++;
return;
}
vector<pair<int, int>> locations;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
for (int d = 0; d < 4; d++) {
if (grid[i][j] == '.') {
int nx = i + dx[d];
int ny = j + dy[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 'r') {
grid[i][j] = 'r';
solve(num + 1);
grid[i][j] = '#';
locations.push_back({i, j});
}
}
}
}
for (auto [x, y] : locations)
grid[x][y] = '.';
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '.') {
grid[i][j] = 'r';
solve(1);
grid[i][j] = '#';
}
}
}
cout << answer << '\n';
return 0;
}
強い高橋君
問題文
町は (H) 行 (W) 列のセルグリッドに分割されています。
(S_{i,j}) が . ならば道路、# ならば障害物です。
高橋君は家から魚市場まで行きます。家は左上のセル、魚市場は右下のセルにあります。
高橋君は上下左右に移動して通過可能なセルに移動できます。町の外に出ることはできず、ブロックに入ることもできません。
しかし、彼は一度に2×2の正方形領域のすべての障害物を破壊して通過可能にすることができますが、1点のエネルギーを消費します。
高橋君が魚市場に到達するために必要な最小のエネルギーを求めてください。
思考プロセス
エネルギーを使用しない場合、移動コストは0です。エネルギーを使用する場合、コストは1です。これは典型的な01-BFSであり、双方向キューを使用してBFSを実行します。
コード
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, w;
cin >> h >> w;
vector<string> grid(h);
for (auto &row : grid)
cin >> row;
vector<vector<ll>> dist(h, vector<ll>(w, INT_MAX));
deque<pair<int, int>> dq;
dq.push_front({0, 0});
dist[0][0] = 0;
while (!dq.empty()) {
auto [x, y] = dq.front();
dq.pop_front();
int dir1[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
for (int i = 0; i < 4; i++) {
int nx = x + dir1[i][0], ny = y + dir1[i][1];
if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == '.') {
if (dist[nx][ny] > dist[x][y]) {
dist[nx][ny] = dist[x][y];
dq.push_front({nx, ny});
}
}
}
int dir2[16][2] = {{-1, -1}, {1, 1}, {-1, 1}, {1, -1},
{2, -1}, {2, 1}, {1, 2}, {1, -2}, {-2, 1}, {-2, -1},
{-1, -2}, {-1, 2}, {2, 0}, {0, 2}, {-2, 0}, {0, -2}};
for (int i = 0; i < 16; i++) {
int nx = x + dir2[i][0], ny = y + dir2[i][1];
if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
if (dist[nx][ny] > dist[x][y] + 1) {
dist[nx][ny] = dist[x][y] + 1;
dq.push_back({nx, ny});
}
}
}
}
cout << dist[h - 1][w - 1] << '\n';
return 0;
}
好み
問題文
長さ (N) の数列 (A) があります。
隣接する2つの数を選んで削除し、その和を元の位置に置く操作を最大 (N-1) 回行うことができます。
可能な数列の個数を求めてください。
思考プロセス
DPを考えます。
この配列に対して前処理を行い、(num_i) を (i) 番目の数とします。すると (a_i = \sum_{j=1}^i num_j) となります。(i) と (i+1) をマージする操作は、(i) と (i+1) の数をマージしてから前処理を行う操作であり、実際には (a_i) を削除することに相当します。(i) と (i+1) をマージする操作では、(i) は最大 (n-1) まで取ることができ、つまり (i < n) となります。削除操作では、(a_n) は必ず保持される必要があります。各前処理は一つの数に対応するため、問題は簡略化され、与えられた (n) 個の数に対して前処理を行い、各回任意の (a_i (i < n)) を削除し、異なる数列の個数を求めることになります。前処理配列 (a_1 \sim a_{n-1}) の異なる部分列の個数を求めることと同じです。
- この数が以前に現れた場合、(dp_i = dp_{i-1} \times 2 - dp_{last-1}) となります。これは、前のすべてのものを接続すると前のものと重複するためです。
- そうでない場合、(dp_i = dp_{i-1} \times 2 + 1) となります。まず前のすべてを接続し、それに自分を加えます。
最後に (dp_{n-1} + 1) を出力します。（空の部分列を加えます）。
コード
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
const int mod = 998244353;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
map<ll, int> lastOccurrence;
vector<ll> dp(n + 1);
dp[1] = 1;
lastOccurrence[a[1]] = 1;
for (int i = 2; i <= n; i++) {
int last = lastOccurrence[a[i]];
if (!last) dp[i] = (dp[i - 1] * 2 + 1) % mod;
else dp[i] = (dp[i - 1] * 2 % mod - dp[last - 1] + mod) % mod;
lastOccurrence[a[i]] = i;
}
cout << dp[n - 1] + 1 << '\n';
return 0;
}