概要
本稿では、Codeforces Round 1027（Div. 3）の問題AからEまでの解法を示す。
問題A：数値構築
問題内容
4桁の整数cが与えられる。整数a（0以上99以下）とb（0以上99以下）を用いて、(a+b)² = c を成立させられるか判定する。
解法
0から√nまでの範囲で遍历し、平方数になるかを判定すればよい。a+b = √c が成立する必要があり、a=0, b=√c で試すだけで十分である。
void solve(){
int c;
cin >> c;
int root = sqrt(c);
if (root * root == c) {
cout << 0 << " " << root << endl;
return;
}
for (int i = 1; i * i <= c; i++) {
if (c % i == 0) {
int d = c / (i * i);
if (d > i) break;
if (d * d + i * i == c) {
cout << i << " " << d << endl;
return;
}
}
}
cout << -1 << endl;
}問題B：文字列とインデックス対
問題内容
長さn（偶数）の01文字列が与えられる。文字列中の文字を適切に並べ替えたとき、ちょうどk個の「良いインデックス対」を作れるか判定する。nは偶数であり、0 ≤ k ≤ n/2 である。
インデックス対の定義： 1 ≤ i ≤ n-i+1 のとき、s[i] == s[n-i+1] であれば (i, n-i+1) はインデックス対である。
解法
文字列をn = 2*k + (n-2*k) に分解する。2*kは条件を満たすインデックス対用、残りの部分是0と1が相殺する部分である。
文字列中の1の個数をcnt1、0の個数をcnt0とする。各自から (n-2*k)/2 を引いた値が負であれば不可。最終的に cnt1/2 + cnt0/2 == k なら可能。
void solve(){
int n, k;
cin >> n >> k;
string s;
cin >> s;
int cnt1 = 0, cnt0 = 0;
for (char ch : s) {
if (ch == '1') cnt1++;
else cnt0++;
}
int offset = (n - 2 * k) / 2;
if (cnt0 < offset || cnt1 < offset) {
cout << "NO\n";
return;
}
cnt0 -= offset;
cnt1 -= offset;
if (cnt0 / 2 + cnt1 / 2 == k) cout << "YES\n";
else cout << "NO\n";
}問題C：配列の分割
問題内容
長さnの非減少数列aが与えられる。要素を削除して、連続しない数列b（b[i] + 1 < b[i+1]）を作成する。可能な最大長を求めよ。
解法
連続する要素が取れないため、交互に要素を選択する 전략が有効である。等しい値드는 重複して選べないので、mapを使用して重複を除去する。
各要素について、前回の値が連続している場合はスキップし、連続していない場合は選択する。
void solve(){
int n;
cin >> n;
map exists;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
exists[x] = true;
}
int result = 0;
int selected = 0;
for (auto it = exists.begin(); it != exists.end(); ++it) {
int val = it->first;
if (!selected || exists.find(val - 1) == exists.end()) {
result++;
selected = 1;
} else {
selected = 0;
}
}
cout << result << endl;
} 問題D：最小囲み矩形
問題内容
1e9 × 1e9の格子上にn個の点が与えられる（座標は重複しない）。1つの点を任意の位置に最大1回移動できる。移動後、すべての点を含む矩形の面積の最小値を求めよ。
解法
移動は実質的に1点を削除する動作と同じ。ただし、すべての点が同一線上にある場合は特別に処理が必要である。
削除すべき点は境界にある点だけである。以下の8点を列挙する：
- x座標最小の2点
- x座標最大の2点
- y座標最小の2点
- y座標最大の2点
各点を削除しながら矩形の面積を計算し、最小値を探す。線上の配置の場合は面積に min(幅, 高さ) を加算する。
struct Point {
int x, y;
};
void solve(){
int n;
cin >> n;
vector<Point> points(n);
Point minX[2] = {{INF, INF}, {INF, INF}};
Point maxX[2] = {{-INF, -INF}, {-INF, -INF}};
Point minY[2] = {{INF, INF}, {INF, INF}};
Point maxY[2] = {{-INF, -INF}, {-INF, -INF}};
for (int i = 0; i < n; i++) {
cin >> points[i].x >> points[i].y;
// 境界点の更新
}
if (n == 1) {
cout << 1 << endl;
return;
}
long long answer = INF;
vector<Point> candidates;
// 8個の候補点を追加
for (Point del : candidates) {
int left = INF, right = INF, top = -INF, bottom = -INF;
for (Point p : points) {
if (p.x == del.x && p.y == del.y) continue;
left = min(left, p.x);
right = min(right, p.y);
top = max(top, p.x);
bottom = max(bottom, p.y);
}
long long area = 1LL * (top - left + 1) * (bottom - right + 1);
if (area < n) area += min(top - left + 1, bottom - right + 1);
answer = min(answer, area);
}
cout << answer << endl;
}問題E：木の最大交互和
問題内容
n個のノードを持つ木が与えられる（根はノード1）。各ノードiには値a[i]が割り当てられている。各ノードについて、根からそのノードまでのパス上の「最大交互和」を求めよ。
交互和とは、符号を交互に変えつつ選択した値の合計の最大値である。
解法
木形DPを使用して解決する。各ノードについて2つの状態を保持する：
- dp[i][0]: ノードiから根までの最大交互和
- dp[i][1]: ノードiから根までの最小交互和
遷移式：
dp[i][0] = max(a[i], a[i] - dp[parent[i]][1]) dp[i][1] = max(a[i], a[i] - dp[parent[i]][0])
根では dp[1][0] = 0, dp[1][1] = a[1] とする。DFSで全ノードを巡回しながら計算する。
const long long NEG_INF = -4e18;
void dfs(int u, int parent) {
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v == parent) continue;
dp[v][0] = min(a[v] - dp[u][1], (long long)a[v]);
dp[v][1] = max(a[v] - dp[u][0], (long long)a[v]);
dfs(v, u);
}
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
dp[i][0] = dp[i][1] = NEG_INF;
head[i] = -1;
}
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
dp[1][0] = 0;
dp[1][1] = a[1];
dfs(1, 0);
for (int i = 1; i <= n; i++) {
cout << max(dp[i][0], dp[i][1]) << " ";
}
cout << endl;
}