C++でABC218のA~D問題を解説します。
本番ではA、Bしか解けませんでした。C問題は一つだけWAで、コンテスト終了後に重大なミスをしていることに気づきました。私のミスを踏まえて解説します。
A – Weather Forecast
問題概要
\(\circ,\times\)で構成される長さ7の文字列\(S\)が与えられる。\(N\)番目の文字が\(\circ\)ならYesを、\(\times\)ならNoを出力してください。
解説
配列のインデックスは\(0\)始まりであることに気を付けて問題文の通り実装します。
#include <bits/stdc++.h>
int main() {
int n; std::cin >> n;
std::string s; std::cin >> s;
if (s[n-1] == 'o')
std::cout << "Yes" << std::endl;
else
std::cout << "No" << std::endl;
return 0;
}
B – qwerty
問題概要
長さ26の数列\(P = (P_1 ,P_2, \ldots,P_{26})\)が与えられる。\(i\)文字目が辞書順で小さいほうから\(P_i\)番目の英小文字であるような文字列を出力してください。
- \(1 \le P_i \le 26\)
- \(P_i \neq P_j(i \neq j)\)
- 入力はすべて整数
解説
英小文字のアルファベットが文字コード上で連続していることを利用します。’a’が最も小さく’z’が最も大きいです。例えば
(char)('a'+1); // 'b'
とすると’b’になります。’a’+1とすることで’a’の一つあと、つまり’b’の文字コードになります。charとintの演算ではintになってしまうので、それをchar型にキャストすることで’b’とすることが出来ます。
これを踏まえて実装します。
#include <bits/stdc++.h>
int main() {
for (int i = 0; i < 26; ++i) {
int p; std::cin >> p;
std::cout << (char)('a'+p-1);
}
return 0;
}
C – Shapes
問題概要
正方形の\(2\)次元グリッド上に\(2\)つの図形\(S\)と\(T\)がある。\(S,T\)はそれぞれ\(S_{i,j},T_{i,j}\)が#であるようなマス全体からなる。\(S\)と\(T\)を\(90\)度回転、平行移動の繰り返しで一致させることが出来るか判定してください。
- \(1 \le N \le 200\)
- \(S,T\)は#と.のみからなる
- \(S,T\)は\(1\)つ以上#を含む
解説
\(S\)を\(0,90,180,270\)度回転させ、それぞれの場合で平行移動して\(T\)に一致させることが出来るかを判定します。平行移動して一致するかどうかは\(S\)と\(T\)の左上の#を基準に考えることで判定できます。後ほど詳しく解説します。
\(90\)度回転
ここでは時計回りに\(90\)度回転させることを考えます。
\(90\)度回転が出来れば\(180\)度回転は\(90\)度回転を\(2\)回、\(270\)度回転は\(90\)度回転を\(3\)回すれば達成できます。
\(2\)次元の配列を走査するときは左の画像のように上から下に、左から右に見ていきます。時計回りに\(90\)度回転させたような出力を得るには、右の画像のように左から右に、下から上に見ればいいことがわかります。
上で説明した2次元配列を時計回りに\(90\)度回転を関数で実装するときには、回転させる二次元配列を参照として受け取り、直接中身を書き換えるようにします。
#include <bit/stdc++.h>
void rotate90(std::vector<std::string>& grid) {
/* gridを時計回りに90度回転させる */
int n = grid.size(); // 正方形なので縦幅か横幅のどちらかを取得
std::vector<std::string> grid90(n, std::string(n, '.'));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
grid90[i][j] = grid[n-1-j][i]; // 90度回転したものをgrid90に格納
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
grid[i][j] = grid90[i][j]; // grid90をgridにコピー
}
平行移動で一致するか判定
\(S\)と\(T\)の#の数が一致するかどうかを判定してから、平行移動して一致させることが出来るかどうかを判定します。
まずはソースコードを見てください。
#include <bits/stdc++.h>
bool is_same(const std::vector<std::string>& s, const std::vector<std::string>& t) {
/* sを平行移動してtに一致させることができるか判定 */
// '#'の数が異なれば一致させることはできない
int count_s = count(s);
int count_t = count(t);
if (count_s != count_t)
return false;
int n = s.size();
// 基準となる左上の'#'の座標取得
std::pair<int,int> ref_s = ref_point(s);
std::pair<int,int> ref_t = ref_point(t);
// sをtに一致させる移動量を計算
int y_translate = ref_t.first - ref_s.first;
int x_translate = ref_t.second - ref_s.second;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int y = i + y_translate;
int x = j + x_translate;
if ((y >= 0 && y < n) && (x >= 0 && x < n)) {
if (s[i][j] != t[y][x])
return false;
}
else {
// '#'であるべきマス目t[y][x]がTのグリッド上にない
if (s[i][j] == '#')
return false;
}
}
}
return true;
}
std::pair<int,int> ref_point(const std::vector<std::string>& grid) {
/* 左上の'#'のpair(row,col) の値を返す */
int n = grid.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == '#')
return std::pair<int,int>(i,j);
}
int count(const std::vector<std::string>& grid) {
/* '#'の数を返す */
int n = grid.size();
int cnt = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == '#')
++cnt;
return cnt;
}
#の数が一致するかどうかを判定しないと、平行移動したときに一致するか否かの判定をミスります。(本番中の私はそうでした)
例えば下のような入力データをは一致できると判定してしまいます。
この場合、平行移動量は\((y,x)=(-1,-1)\)となります。for文で\((i,j) = (0,0),(0,1),(1,0)\)の時はt[x][y]が範囲外になるので比較が行われないです。\((i,j)=(1,1)\)の時のみs[i][j]とt[y][x]の比較が行われ両方とも’#’で等しいと判定され、一致させられると誤った判定がされます。
このようなデータに対してもきちんと判定できるように’#’の数が一致するかどうかを判定する必要があります。
2 .. .# ## ##
D – Rectangles
問題概要
\(2\)次元平面上の\(N\)個の相違なる点の内4つを頂点とし、すべての辺が\(x\)軸または\(y\)軸に並行であるような長方形はいくつありますか。
- \(4 \le N \le 2000\)
- \(0 \le x_i, y_i \le 10^9\)
- \( (x_i,y_i) \neq (x_j,y_j)~(i \neq j)\)
- 入力はすべて整数である。
解説
条件を満たす長方形を見つけるために\(4\)個の頂点を全探索すると\(O(N^4)\)となり間に合いません。
この問題の解説に関しては公式の解説がとても分かりやすかったのでそちらにお譲りします。
#include <bits/stdc++.h>
int main() {
int n; std::cin >> n;
std::vector<std::pair<int, int>> v(n);
for (int i = 0; i < n; ++i) std::cin >> v[i].first >> v[i].second;
std::sort(v.begin(), v.end()); // firstを昇順に、secondを昇順に
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
std::pair<int,int>& lower_left = v[i]; // 左下
std::pair<int,int>& upper_right = v[j]; // 右上
if (!(lower_left.first < upper_right.first)) continue;
if (!(lower_left.second < upper_right.second)) continue;
// lower_leftとupper_rightに対応する点があるかどうか
std::pair<int,int> upper_left = std::make_pair(lower_left.first, upper_right.second); // 左上
std::pair<int,int> lower_right = std::make_pair(upper_right.first, lower_left.second); // 右上
if (!std::binary_search(v.begin(), v.end(), upper_left)) continue;
if (!std::binary_search(v.begin(), v.end(), lower_right)) continue;
cnt++;
}
}
std::cout << cnt << std::endl;
return 0;
}