概要
問題の解き方をまとめました。
- 2025.9.24 A-D
A Product #ABC086-A
問題
$a$ と $b$ の積が偶数か奇数か判定する。
- $1 \leq a, b \leq 10000$
- $a$ と $b$ は整数
解法
- $a$ と $b$ がそれぞれ奇数か偶数かを調べて、両方奇数だったら積も奇数になる。それ以外は偶数になる。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
cin >> a >> b;
cout << ((a % 2) && (b % 2) ? "Odd" : "Even") << endl;
return 0;
}
B 1 21 #ABC086-B
問題
整数 $a$ と $b$ をこの順に繋げて読んだものが平方数かどうか判定する。
- $1 \leq a, b \leq 100$
- $a$ と $b$ は整数
解法
- $a$ と $b$ を文字列として受け取って連結し、整数 $n$ に変換する。
- $n$ の平方根を求め、小数点以下を切り捨てる。それを二乗した値が $n$ に等しかったら、$n$ は平方数になる。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
string a, b;
int main() {
cin >> a >> b;
int n = stoi(a + b); //a と b を連結して整数に変換する
int ans = sqrt(n); //n の平方根、小数点以下切り捨て
cout << (ans*ans == n ? "Yes" : "No") << endl;
return 0;
}
C Traveling #ABC086-C
問題
時刻 $0$ に点 $( 0, 0 )$ を出発し、時刻 $t_i$ に点 $( x_i, y_i )$ に訪れる。点 $( x, y )$ からは上下左右に移動できるが、その場にとどまることはできない。旅行プランが実行可能かどうか判定する。
- $1 \leq N \leq 10^5$
- $0 \leq x_i \leq 10^5$
- $0 \leq y_i \leq 10^5$
- $1 \leq t_i \leq 10^5$
- $t_i < t_{i+1}$
- 入力は全て整数
解法
- 時間内に次の点に到達できるかどうかと、次の点に到達した後余った時間が偶数かどうかで、時間 $t_i$ に目標点に到達できるかどうかを判定する。そうでなかったら旅行プランは実行不可能。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
int N;
int main() {
cin >> N;
bool ans = true;
int nt = 0, nx = 0, ny = 0, t, x, y; //現在の点と次の点
rep(i, N) {
cin >> t >> x >> y;
int d = (t - nt) - (abs(x-nx) + abs(y-ny)); //次の点まで移動した後の余った時間
if (d < 0 || d % 2 == 1) { ans = false; break; } //d が負 ( 時間が足りなかった ) か、奇数 ( 隣のマスに行って戻って来れない ) の場合、実行不可能
nt = t; nx = x; ny = y; //次の点に移動
}
cout << (ans ? "Yes" : "No") << endl;
return 0;
}
D Checker #ABC086-D
問題
一辺が $K$ の市松模様になっている無限に広がる二次元グリッドがある。市松模様とは白か黒に塗られていること。座標 $( x_i, y_i )$ を $c_i$ で塗るという $N$ 個の希望のうち、最大でいくつ叶えることができるかを求める。
- $1 \leq N \leq 10^5$
- $1 \leq K \leq 1000$
- $0 \leq x_i \leq 10^9$
- $0 \leq y_i \leq 10^9$
- $i \neq j$ なら $( x_i, y_i ) \neq ( x_j, y_j )$
- $c_i$ は「 B 」または「 W 」
- $N$ 、$K$ 、$x_i$ 、$y_i$ は整数
解法
二次元累積和
- 市松模様は全部で $2K \times 2K$ のパターンしかないので、座標をそれぞれ $2K$ で割った余りの座標に希望の個数を増やす。白の時と黒の時とで分ける。
- 計算を簡単にするために、$4K * 4K$ の範囲に希望の個数をコピーする。
- 希望の個数をもとに、二次元累積和を作成する。
- $K \times K$ の範囲における黒のパターンと白のパターンを全探索して、叶える希望の個数が最も多いものを求める。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repu(i, s, t) for (int i = (int)s; i < (int)t; i++)
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
int N, K, K2, K4;
void copy(vector<vector<int>> &S) { //2K * 2K の値を 4K * 4K の範囲の三箇所にコピーする
rep(i, K2) rep(j, K2) {
S.at(i+K2).at(j) = S.at(i).at(j);
S.at(i).at(j+K2) = S.at(i).at(j);
S.at(i+K2).at(j+K2) = S.at(i).at(j);
}
}
void sum_count(vector<vector<int>> &S) { //二次元累積和を作る
rep(i, K4-1) S.at(i+1).at(0) += S.at(i).at(0); //j == 0 の時
rep(j, K4-1) S.at(0).at(j+1) += S.at(0).at(j); //i == 0 の時
repu(i, 1, K4) repu(j, 1, K4) { //それ以外
S.at(i).at(j) += S.at(i-1).at(j) + S.at(i).at(j-1) - S.at(i-1).at(j-1);
}
}
int max_count(vector<vector<int>> &S, vector<vector<int>> &T) { //叶える希望の個数の最大値を求める
int ans = 0; //希望の個数の最大値
rep(i, K) rep(j, K) {
int count = 0; //範囲内にある希望の個数
count += S.at(i).at(j) + S.at(i+K).at(j+K)*2 + S.at(i+K2).at(j+K2);
count -= S.at(i).at(j+K) + S.at(i+K).at(j);
count -= S.at(i+K).at(j+K2) + S.at(i+K2).at(j+K);
//市松模様の左上と右下の範囲の希望の個数
count += T.at(i).at(j+K) + T.at(i+K).at(j);
count += T.at(i+K).at(j+K2) + T.at(i+K2).at(j+K);
count -= T.at(i+K).at(j+K)*2 + T.at(i).at(j+K2) + T.at(i+K2).at(j);
//市松模様の右上と左下の範囲の希望の個数
chmax(ans, count);
}
return ans;
}
int main() {
cin >> N >> K;
K2 = K * 2; K4 = K * 4;
vector<vector<int>> B(K4, vector<int>(K4, 0)), W(K4, vector<int>(K4, 0)); //黒と白のそれぞれの座標における希望の個数
int x, y; char c;
rep(i, N) {
cin >> x >> y >> c;
int nx = x % K2, ny = y % K2; //2K * 2K パターンしかないので、その範囲で考える
if (c == 'B') B.at(nx).at(ny)++; //黒の希望に加算
else W.at(nx).at(ny)++; //白の希望に加算
}
copy(B); copy(W); sum_count(B); sum_count(W);
//4K * 4K に拡張、二次元累積和の表を作る
int ans = 0; chmax(ans, max_count(B, W)); chmax(ans, max_count(W, B));
//叶えることができる希望の最大個数
cout << ans << endl;
return 0;
}