AtCoder Beginner Contest 366
A,B,C,Dの4完。
レートは863→898の+35となり、先週と先々週でのレートダウンを取り返し、トップタイのレートに戻すことができた。
Cはデータ構造、Dは累積和の基礎を理解しているかを問われている感じがして、鉄則本をちゃんと1周しておいてよかったと感じる。
分野別 初中級者が解くべき過去問精選 100 問を終わらせたら、もう一回ちゃんと鉄則本の復習も行いたい。
A - Election 2
総有効票が $N$ 票の選挙がある。2人の候補者にそれぞれ $T$ 票、$A$ 票が入った時、すでに勝敗が決まっているか判定せよ、という問題。
どちらかが過半数を超えているかを判定すればOK。
ll N, T, A;
int main()
{
cin >> N >> T >> A;
if (T > N / 2 || A > N / 2) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
B - Vertical Writing
横書きの文字列が $N$ 個与えられる。これを縦書きに変換せよ。ただし、縦書きで出力する際に、一番長い文字列に文字数を合わせるようにアスタリスクを挿入するが、横方向に見て末端にはアスタリスクを挿入しないようにせよ、という問題。
以下の2ステップに分けて解いていく。
- まず、一番長い文字列に合わせて、アスタリスクを挿入しながら縦横変換する。
- 末尾のアスタリスクを削除する。
ll N;
string S[109];
string S_ans[109];
int main()
{
cin >> N;
ll M = 0;
for (int i = 0; i < N; i++)
{
cin >> S[i];
M = max(M, (ll)S[i].size());
}
for (int i = 0; i < M; i++)
{
S_ans[i] = ""; // 初期化
for (int j = 0; j < N; j++)
{
if (i >= S[N - j - 1].size()) S_ans[i] += "*";
else S_ans[i] += S[N - j - 1][i];
}
// 末尾のアスタリスクを削除
while (!S_ans[i].empty() && S_ans[i].back() == '*') {
S_ans[i].pop_back();
}
}
for (int i = 0; i < M; i++)
{
cout << S_ans[i] << endl;
}
return 0;
}
C - Balls and Bag Query
空の袋があります。クエリが ( Q ) 個与えられるので、順番に処理してください、という問題。
クエリは次の3種類がある。
-
1 x: 整数 ( x ) が書かれたボールを1つ袋に入れる。 -
2 x: 整数 ( x ) が書かれたボールを1つ袋の中から取り出して外に捨てる。このクエリが与えられるとき、袋の中に整数 ( x ) が書かれたボールが存在することが保証される。 -
3: 袋の中にあるボールに書かれている整数の種類数を出力する。
今回は $Q$が$ 1 \leq Q \leq 2 \times 10^5 $という制約があり、整数の種類数を探索する部分に$O(Q)$をかけていると全体の処理は $O(Q^2)$ となりTLEとなるが、setを使って$O(QlogQ)$で処理すると実行時間に間に合う。
ll Q;
ll A[1000009];
string S;
vector<vector<ll>> dp;
set<ll> st;
int main()
{
cin >> Q;
for (int i = 0; i < Q; i++)
{
ll query;
ll num;
cin >> query;
if (query == 1)
{
cin >> num;
A[num]++;
if (A[num] == 1)
{
st.insert(num);
}
}
else if (query == 2)
{
cin >> num;
A[num]--;
if (A[num] == 0)
{
st.erase(num);
}
}
else
{
cout << st.size() << endl;
}
}
return 0;
}
D - Cuboid Sum Query
正整数 $N$ と、 $1 \leq x, y, z \leq N$ を満たす整数の組 $(x, y, z)$ に対して、整数 $A_{x,y,z}$ が与えられます。
次の形式の $Q$ 個のクエリが与えられるので、それぞれに答えてください。
$i$ 個目 $(1 \leq i \leq Q)$ のクエリでは $1 \leq Lx_i \leq Rx_i \leq N$ 、 $1 \leq Ly_i \leq Ry_i \leq N$ 、 $1 \leq Lz_i \leq Rz_i \leq N$ をすべて満たす整数の組 $(Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i)$ が与えられるので、
$$
\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}
$$
を求めよ、という問題。
累積和を3次元に拡張して考える。
ll N, Q;
ll A[109][109][109];
ll S[110][110][110]; // 累積和を保持する配列
int main()
{
// 入力の読み込み
cin >> N;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
for (int k = 1; k <= N; k++)
{
cin >> A[i][j][k];
}
}
}
// 累積和の計算
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
for (int k = 1; k <= N; k++)
{
S[i][j][k] = A[i][j][k]
+ S[i-1][j][k]
+ S[i][j-1][k]
+ S[i][j][k-1]
- S[i-1][j-1][k]
- S[i-1][j][k-1]
- S[i][j-1][k-1]
+ S[i-1][j-1][k-1];
}
}
}
// クエリ処理
cin >> Q;
for (int i = 0; i < Q; i++)
{
ll Lx, Rx, Ly, Ry, Lz, Rz;
cin >> Lx >> Rx >> Ly >> Ry >> Lz >> Rz;
ll result = S[Rx][Ry][Rz]
- S[Lx-1][Ry][Rz]
- S[Rx][Ly-1][Rz]
- S[Rx][Ry][Lz-1]
+ S[Lx-1][Ly-1][Rz]
+ S[Lx-1][Ry][Lz-1]
+ S[Rx][Ly-1][Lz-1]
- S[Lx-1][Ly-1][Lz-1];
cout << result << endl;
}
return 0;
}
E - Manhattan Multifocal Ellipse
E問題は解説のPythonのコードをcppに変換した。
2次元平面上の $N$ 個の点 $(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)$
と、非負整数 $D$ が与えられます。
整数の組 $(x, y)$ であって、
$$
\sum_{i=1}^{N} \left( |x - x_i| + |y - y_i| \right) \leq D
$$
を満たすものの個数を求めよ、という問題。
しゃくとり法を用いて、$\sum_{i=1}^{N} |x - x_i|$と$\sum_{i=1}^{N} |y - y_i|$をそれぞれ計算し、それらの和が$D$以下となる組み合わせを求める。
頭ではわかっていても、コンテスト中に実装に落とし込めなかったので悔しい問題。ちゃんと復習して定着させたい。
ll N, D;
const ll M = 2000000;
vector<ll> calc(vector<ll>& xs) {
vector<ll> xsum(2 * M + 2, 0);
sort(xs.begin(), xs.end());
ll i = 0;
xsum[0] = accumulate(xs.begin(), xs.end(), 0) + N * M;
for (ll x = 1; x <= 2 * M + 1; x++) {
while (i < N && xs[i] < x - M) {
i++;
}
xsum[x] = xsum[x - 1] + 2 * i - N;
}
return xsum;
}
int main() {
cin >> N >> D;
vector<ll> x(N), y(N);
for (ll i = 0; i < N; i++) cin >> x[i] >> y[i];
vector<ll> xsum = calc(x);
vector<ll> ysum = calc(y);
sort(xsum.begin(), xsum.end());
sort(ysum.begin(), ysum.end());
ll ans = 0;
ll j = 2 * M;
for (ll i = 0; i <= 2 * M; i++) {
while (j >= 0 && xsum[i] + ysum[j] > D) {
j--;
}
ans += j + 1;
}
cout << ans << endl;
return 0;
}