A. Dr. TC
Dr. TC は患者の知能をテストするために、以下のような問題を設計しました。
- 長さが \(n\) の二進数文字列 \(s\) を作成します。
- この文字列 \(s\) を元に、\(n\) 個の二進数文字列 \(a_1, a_2, \dots, a_n\) を生成します。具体的には、\(a_i\) は \(s\) の第 \(i\) 文字を反転（1 なら 0 に、0 なら 1 に）したものです。
- これらの文字列を \(n \times n\) のグリッドに並べます。
例えば、\(s = 101\) なら、\(a = [001, 111, 100]\) となります。
患者のタスクは、このグリッド内の '1' の数を一秒以内に数えることです。
各文字について、'1' なら \(n-1\) 、'0' なら 1 という貢献度を持ちます。
コード
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
string s;
cin >> s;
long long res = 0;
for (char c : s) {
res += (c == '1') ? n - 1 : 1;
}
cout << res << endl;
}
return 0;
}
B. St. Chroma
長さが \(n\) の順列 \(p\) が与えられます。この順列は 0 から \(n-1\) までの全ての整数を含んでいます。
St. Chroma は、以下の方法で各セルを色付けします：
- 第 \(i\) セルは、\(p_1, p_2, \dots, p_i\) の最小未出現非負整数（MEX）で色付けされます。
例えば、\(p = [1, 0, 3, 2]\) なら、各セルの色は [0, 2, 2, 4] になります。
今、整数 \(n\) と \(x\) が与えられ、St. Chroma は色 \(x\) を最も多く使用するように順列 \(p\) を構築したいです。
この問題では、0 から \(x-1\) までの数字を最初に配置し、\(x\) を最後に配置することで解決できます。
コード
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> w(n);
for (int i = 0; i < n; ++i) w[i] = i;
if (m < n) swap(w[n-1], w[m]);
for (int i = 0; i < n; ++i) cout << w[i] << " ";
cout << endl;
}
return 0;
}
C. Cherry Bomb
長さが \(n\) の整数配列 \(a\) と \(b\) が与えられます。ある整数 \(x\) が存在して、すべての \(1 \leq i \leq n\) に対して \(a_i + b_i = x\) となるとき、これらは「互いに補完する」と言います。
配列 \(b\) にはいくつかの要素が欠けていることがあります（欠けている要素は -1 で表されます）。あなたのタスクは、以下の条件を満たすような配列 \(b\) の種類数を計算することです：
- \(a\) と \(b\) は互いに補完する。
- 欠けている要素は 0 以上 \(k\) 以下の整数で置き換えることができる。
全ての要素が -1 である場合、最大値と最小値の差を考慮して解を求めることができます。
コード
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int c = 0;
for (int i = 0; i < n; ++i) {
cin >> b[i];
c += (b[i] != -1);
}
if (c == 0) {
sort(a.begin(), a.end());
cout << max(0, m - (a[n-1] - a[0]) + 1) << endl;
} else {
bool flag = false;
int v = 0;
for (int i = 0; i < n; ++i) {
if (b[i] != -1) {
v = a[i] + b[i];
break;
}
}
for (int i = 0; i < n; ++i) {
if (b[i] == -1) flag |= (v - a[i] < 0 || v - a[i] > m);
else flag |= (a[i] + b[i] != v);
}
cout << (flag ? "0" : "1") << endl;
}
}
return 0;
}
D. Flower Boy
Flower Boy は長さが \(n\) の花の美しさを表す整数配列 \(a_1, a_2, \dots, a_n\) があります。Igor はちょうど \(m\) 本の花を摘みたいと考えています。
Igor は左から右に花を観察し、それぞれの花の美しさが \(b_i\) 以上であればその花を摘むことができます。
しかし、必要な美しさを持つ花が見つからない場合、Igor は魔法を使って新しい花を追加することができます。この操作は一度だけ可能です。
あなたのタスクは、Igor が \(m\) 本の花を摘むために必要な最小の美しさ \(k\) を出力することです。
この問題では、前後の部分配列の最長一致を管理することで解を求めることができます。
コード
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
vector<int> l(n+1, 0), r(n+2, m+1);
for (int i = 1; i <= n; ++i) l[i] = l[i-1] + (l[i-1] < m && a[i-1] >= b[l[i-1]]);
for (int i = n; i > 0; --i) r[i] = r[i+1] - (r[i+1] > 1 && a[i-1] >= b[r[i+1]-1]);
int res = INT_MAX;
if (l[n] == m) res = 0;
if (l[n] == m-1) res = min(b[m-1], res);
for (int i = 1; i <= n; ++i)
if (r[i] - l[i-1] == 2)
res = min(res, b[l[i-1]]);
cout << (res == INT_MAX ? -1 : res) << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
E. Wolf
Wolf は美味しさを表す長さが \(n\) の順列 \(p_1, p_2, \dots, p_n\) を持っています。Wolf は二分探索を使って美味しさが \(k\) の羊を見つけたいと考えています。
区間 \([l, r]\) 上の \(k\) に対する二分探索が成功するかどうかは、関数 \(f(l, r, k)\) で定義されます。
牛の Nerd は Wolf を助けたいと思っています。彼は \(q\) 個のクエリを受け取り、それぞれのクエリで \(l\), \(r\), \(k\) が与えられます。
Nerd は、\(d\) 個の位置を選択し、これらの位置の要素を任意に並び替えることができます。Nerd が \(f(l, r, k)\) が必ず成功するようにするための最小の \(d\) を求めます。
この問題では、二分探索の過程をシミュレートし、必要に応じて要素を交換することで解を求めることができます。
コード
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> w(n+1), id(n+1);
for (int i = 1; i <= n; ++i) {
cin >> w[i];
id[w[i]] = i;
}
while (m--) {
int pl, pr, x;
cin >> pl >> pr >> x;
if (id[x] > pr || id[x] < pl) {
cout << "-1 ";
continue;
}
int l = pl, r = pr, c = 0;
int maxc = 0, minc = 0, a = 0, b = 0;
while (l < r) {
int mid = (l + r) / 2;
if (w[mid] == x) break;
else if (w[mid] < x) {
if (id[x] < mid) maxc++, r = mid - 1;
else l = mid + 1, a++;
} else {
if (id[x] > mid) l = mid + 1, minc++;
else r = mid - 1, b++;
}
}
if (maxc + b <= n - x && minc + a <= x - 1) cout << max(maxc, minc) * 2 << " ";
else cout << "-1 ";
}
cout << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
F. Goblin
TC 博士は新しい患者である Goblin の IQ をテストしたいと考えています。博士は長さが \(n\) の二進数文字列 \(s\) を作成し、それから \(n\) 個の二進数文字列 \(a_1, a_2, \dots, a_n\) を生成します。\(a_i\) は \(s\) の第 \(i\) 文字を反転したもので、これらの文字列を \(n \times n\) のグリッドに並べます。
良い集合 \(S\) とは、以下の条件を満たすもののことです：
- すべての \(1 \le i \le k\) に対して、\(1 \le x_i, y_i \le n\) であり、\(g_{x_i, y_i} = 0\) である。
- 任意の \(i, j\) に対して、\((x_i, y_i)\) と \((x_j, y_j)\) は 0 で接続されている。
Goblin のタスクは、最大の良い集合 \(S\) のサイズを見つけることです。
この問題では、上半分と下半分の 0 の数を管理することで解を求めることができます。
コード
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
long long res = 0, t = 0, d = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') t = d, d = 0, t++;
else t += i, d += n - 1 - i;
res = max({res, t, d});
}
cout << res << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
G1. Baudelaire (easy version)
これは問題の簡単なバージョンです。このバージョンでは、各ノードがノード 1 と隣接していることが保証されています。
この問題は対話型の問題です。Baudelaire は大きさが \(n\) の木を持っています。この木の各ノードの値は 1 または -1 です。
Cow the Nerd はこの木を手に入れたいと思っています。そのためには、以下のクエリを用いて木の情報を得なければなりません：
- `1 k u₁ u₂ ... uₖ`：根からノード \(u\) までのパス上の値の和を取得します。
- `2 u`：ノード \(u\) の値を反転します。
Cow the Nerd は、最大 \(n+200\) 回のクエリで全てのノードの最終的な値を正しく推測しなければなりません。
この問題では、ノード 1 に関する情報を基に、他のノードの値を推測することができます。
コード
#include <bits/stdc++.h>
using namespace std;
int ask1(vector<int>& v) {
cout << "? 1 " << v.size() << " ";
for (int u : v) cout << u << " ";
cout << endl;
fflush(stdout);
int res;
cin >> res;
return res;
}
int ask1(int x) {
cout << "? 1 1 " << x << endl;
fflush(stdout);
int res;
cin >> res;
return res;
}
void ask2(int x) {
cout << "? 2 " << x << endl;
fflush(stdout);
}
void solve() {
int n;
cin >> n;
vector<int> w(n+1);
int v1 = ask1(1);
if (abs(v1) == 1) {
w[1] = v1;
for (int i = 2; i <= n; ++i) w[i] = ask1(i) - w[1];
} else if (v1) {
if (v1 == 2) w[1] = -1;
else w[1] = 1;
ask2(1);
for (int i = 2; i <= n; ++i) w[i] = ask1(i);
} else {
ask2(1);
int x = ask1(1);
if (x == 2) w[1] = -1;
else w[1] = 1;
ask2(1);
for (int i = 2; i <= n; ++i) w[i] = ask1(i);
}
cout << "! ";
for (int i = 1; i <= n; ++i) cout << w[i] << " ";
cout << endl;
fflush(stdout);
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}