C++でABC203のA~Dを解説します。
本番ではA~CまでAC出来ました。D問題については公式の解説や、解説動画を読み込むことで理解できました。
では解説していきます。
A – Chinchirorin
問題概要
\(3\)つサイコロの目\( ~ a,b,c ~ \)について、\(3 ~ \)つの内\( ~ 2 ~ \)つが同じときは残りの\( ~ 1 ~ \)つの目を、同じものがないときは\(0\)を出力してください。
解説
問題文の通り実装することで答えを求めます。
#include <bits/stdc++.h>
int main() {
int a, b, c; std::cin >> a >> b >> c;
int ans;
if (a == b) ans = c;
else if (b == c) ans = a;
else if (c == a) ans = b;
else ans = 0;
std::cout << ans << std::endl;
return 0;
}B – AtCoder Condominium
問題概要
\(N\)階建で各階に\(K\)室の部屋があるマンションがある。\(i\)階の\(j\)号室の部屋番号が\(i0j\)と表されるとき、各部屋の部屋番号を\(3\)桁の整数とみなすとすべての部屋番号の合計値はいくらになるか。
- \( 1 \le N,K \le 9 \)
- \(N,K\)は整数
解説
階を表す数字に\(100\)を掛けて、号室を表す数字と足し合わせることで\(3\)桁の数字とすることが出来ます。2重のfor文ですべての部屋番号を\(3\)桁の数字にしたものを足し合わせることで答えを求めます。
for文は1から始まっていることに注意してください。
#include <bits/stdc++.h>
int main() {
int n, k; std::cin >> n >> k;
int sum = 0;
for (int floor = 1; floor <= n; ++floor)
for (int room_num = 1; room_num <= k; ++room_num)
sum += floor * 100 + room_num;
std::cout << sum << std::endl;
return 0;
}C – Friends and Travel costs
問題概要
\(10^{100}+1\)個の村がありそれぞれ村\(0,~\)村\(1 \ldots ,~\)村\(10^{100}\)と番号がついている。村\(i\) で\(1\)円払うことで\((i+1)\)に移動することが出来る。
太郎君は\(K\)円を持った状態で村\(0\)におり、可能な限り番号の大きな村まで進もうとする。太郎君には\(N\)人の友達がいて、\(i\)人目の友達は村\(A_i\)におり、その村に着くとその友達から\(B_i\)円もらうことが出来る。最終的にたどりつく村の番号を求めてください。
- \(1 \le N \le 2 \times 10^5\)
- \( 1 \le K \le 10^9 \)
- \( 1 \le A_i \le 10^{18}\)
- \( 1 \le B_i \le 10^9\)
- 入力はすべて整数
解説
太郎君が到達できる村は最大で\( K + B_1 + B_2 + \ldots + B_N \le 10^9 + 2 \times 10^5 \times 10^9 \le 10^{15}\)であるので、long longに収まります。
方針は、現在地から最も近い村で友達が居る村に移動を試み、そこに移動できれば(所持金が移動コスト以上の場合)その村に移動し所持金を更新し、同様のことを繰り返し行います。もしその村に移動できなければ現在の所持金で移動できる村まで移動して終了です。
あらかじめ\(A_i\)と\(B_i\)をpairにしてvectorの要素とし、\(A_i\)について昇順にソートして、現在地から近い順に村を移動する実装を行います。
#include <bits/stdc++.h>
int main() {
long long n, k; std::cin >> n >> k;
std::vector<std::pair<long long, long long>> ab;
for (int i = 0; i < n; ++i) {
long long a, b; std::cin >> a >> b;
ab.push_back({a,b});
}
std::sort(ab.begin(), ab.end()); // A_iについて昇順にソート
long long pos = 0; // 太郎君の位置
for (int i = 0; i < n; ++i) {
long long cost = ab[i].first - pos;
if (k >= cost) {
k -= cost; // コスト支払
k += ab[i].second; // i番目の友達からお金受け取り
pos = ab[i].first; // 位置をA_iに更新 (pos += costでも同じ)
}
}
pos += k; // 残金で移動
std::cout << pos << std::endl;
return 0;
}D – Pond
問題概要
\(N \times N\)のマス目があり、北から\(i\)番目かつ西から\(j\)番目のマスの高さは\( A_{i,j}\)で与えられる。\(N \times N\)のマス目に完全に含められる\(K \times K\)の区画であってその区画に含まれるマスの高さの中央値が最も低いような区画の中央値を求めてください。\( K \times K\)の区画に含まれるマスの高さの中央値は\( \lfloor \frac{K^2}{2} \rfloor + 1 \)番目に高いマスを指します。
- \( 1 \le K \le N \le 800 \)
- \( 0 \le A_{i,j} \le 10^9 \)
- 入力はすべて整数である。
解説
この問題では二分探索と二次元累積和を使います。
とか言っていますが、解説を見て初めて使うことがわかりました。公式の解説以外にもいろいろな解説を見ていましたが、どうやら最大値や最小値を求める問題では二分探索は定番らしいです。（二分探索のわかりやすい記事はこちら、二次元累積和のわかりやすい記事こちら）
この問題の答えは「\(K \times K\)の区画で中央値がある値\(m\)以下になる区画が\(1\)つ以上ある」という条件で二分探索を行い、二分探索終了時点での条件を満たす最小の\(m\)です。
0,1で置き換える
「\(K \times K\)の区画の中央値がある値\(m\)以下」は「\(K \times K\)個のマス目の内半分以上が\(m\)以下」と言い換えることが出来ます。
なぜなら、\(m\)以下の値が半分以上存在すると、中央値、上から数えて\( \lfloor \frac{K^2}{2} \rfloor \)番目の値、が\(m\)以下になるからです。以下具体例で見てみます。
例えば\(K \times K\)の区画の値が以下のような場合を考えます。(\(K=3\))
1 2 2 2 3 4 7 8 9
- 「中央値は\(4\)以下ですか」を考えます。\(4\)以下の数字は\(6\)個あり半分以上を占めており中央値は\(4\)以下だと判定できます。実際\( \lfloor \frac{K^2}{2} \rfloor \)番目に高いマスの値は\(3\)で、中央値が\(4\)以下は正しいです。
- では次に「中央値は\(3\)以下ですか」を考えます。\(3\)以下の数字は\(5\)つで半分以上を占めており中央値は\(3\)以下と判定できます。
- 次に「中央値は2以下ですか」を考えます。\(2\)以下の数字は\(4\)つで半分未満なので、中央値は\(2\)以下ではないと判定できます。
もう一つ例を見てみます。(\(K=2\))
1 2 2 3
- 「中央値は\(2\)以下ですか」を考えると、\(2\)以下の数は\(3\)つで半分以上なので中央値は\(2\)以下です。
- 「中央値は\(1\)以下ですか」を考えると、\(1\)以下の数は\(1\)つで半分未満で、中央値は\(1\)以下ではないです。
この判定方法で重要なのは具体的な値ではなく「中央値が\(m\)以下ですか」の問いに対して、\(m\)以下の数字がいくつあるのかです。実際にある区画の中央値の判定をするときは、その区画の値を、\(m\)以下なら\(1\)、\(m\)より大きいなら\(0\)に置き換えたものを用意して、その区画の合計値、言い換えると\( m \)以下の数字の個数で中央値が\(m\)以下かどうかを判定します。
一つ目のデータ例で「中央値が3以下ですか」を考えるときは、下のように\(3\)以下なら\(1\)、そうでなければ\(0\)で置き換えた二次元配列を用意します。その区画の合計値が\(5\)で、区画のマス目の半分以上を占めているので中央値は\(3\)以下と判定できます。
二次元累積和を使って中央値が\(m\)以下かどうかを判定
\(K \times K\)の区画の値を\(0,1\)に置き換えてから、毎回for文でその合計を計算していては間に合いません。ここで二次元累積和を使います。前処理に\(O(N^N)\)かかりますが、二次元配列のある座標からある座標までの合計値は\( O(1) \)で求められます。(二次元累積和のわかりやすい記事)
具体的には「中央値が\(m\)以下」かどうかを判定するときは、\(N \times N\)の区画の値を\(m\)以下なら\(1\)、そうでなければ\(0\)に置き換えた二次元配列を用意します。その配列について横方向と縦方向に累積和をとり、二次元累積和を作ります。あとは\(K \times K\)の区画ごとに合計値を\(O(1)\)で計算し、中央値が\(m\)以下かどうかを判定します。
ここまで準備が出来れば、この章の冒頭の「\(K \times K\)の区画で中央値がある値\(m\)以下になる区画が\(1\)つ以上ある」という条件で二分探索を行い、二分探索終了時点での条件を満たす最小の値がこの問題の答えになります。
#include <bits/stdc++.h>
bool check(const std::vector<std::vector<int>>& a,
int m,
const int& n,
const int& k);
int main() {
int n, k; std::cin >> n >> k;
std::vector<std::vector<int>> a(n, std::vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
std::cin >> a[i][j];
// ng: 中央値未満の最大値
// ok: 中央値の最小値
int ng = -1, ok = 1e9;
while (ok-ng > 1) {
int m = (ng + ok) / 2;
if (check(a, m, n, k)) ok = m;
else ng = m;
}
std::cout << ok << std::endl;
return 0;
}
bool check(const std::vector<std::vector<int>>& a, int m, const int& n, const int& k) {
/* 中央値がm以下になる区画の個数を返す */
// m以下->1 そうでない->0
std::vector<std::vector<int>> field(n, std::vector<int>(n, 0));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (a[i][j] <= m) field[i][j] = 1;
// 2重累積和
std::vector<std::vector<int>> cumulative_sum2d(n+1, std::vector<int>(n+1, 0));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cumulative_sum2d[i+1][j+1] =
cumulative_sum2d[i+1][j]
+ cumulative_sum2d[i][j+1]
- cumulative_sum2d[i][j]
+ field[i][j];
/* kxkの区画にm以下がceil(k*k/2)個以上あれば
* その区画の中央値はm以下になる
*/
for (int i = 0; i < n-k+1; ++i) {
for (int j = 0; j < n-k+1; ++j) {
int cnt =
cumulative_sum2d[i+k][j+k]
- cumulative_sum2d[i+k][j]
- cumulative_sum2d[i][j+k]
+ cumulative_sum2d[i][j];
if (cnt >= (k*k+2-1)/2)
return true;
}
}
return false;
}