AtCoder Beginner Contest 430 コンテストまとめ

2025-11-32025-11-7

AtCoder/ABC/ABCまとめ競技プログラミング

コンテスト情報

https://atcoder.jp/contests/abc430

コンテスト時間: 2025-11-01(土) 21:00 ~ 2025-11-01(土) 22:40 (100 分)

新ジャッジシステムの運用後初の ABC であった。

また、今回から AtCoder 初参加者の内部レートが上方修正されたらしい。

https://atcoder.jp/posts/1591

A 問題

Difficulty: 18 / NoviSteps: 7Q / 解答時間: 3:57 + WA x1

問題概要

「飴を $A$ 個以上所持している人はクッキーを $B$ 個以上所持していなければならない」という法律がある。

高橋君は飴を $C$ 個、クッキーを $D$ 個所持している。高橋君がこの法律に違反しているかどうか判定せよ。

解答方針

$C \geq A \land D > B$ であるならYes、そうでなければNoを出力する。

最初、「クッキーを $B$ 個以上所持してはならない」と誤読したし、 $D \geq B$ と typo して 1 ペナ。何をやっているんだ？

ABC 430 A - Candy Cookie Law

ABC 430 A - Candy Cookie Law

ABC 430 A - Candy Cookie Law の考察記事です。

B 問題

Difficulty: 141 / NoviSteps: 4Q / 解答時間: 5:23

問題概要

$N$ 行 $N$ 列からなるグリッドがあり、グリッドの上から $i$ 行目左から $j$ 列目のマスは、 $S_{i,j}$ が#のとき黒く、.のとき白く塗られている。

このグリッドから縦 $M$ 行横 $M$ 列の領域を取り出して得られるマスの塗られ方は何種類あるか。

解答方針

$M \times M$ の領域を取ってきて、それをvector<string>などで保存し、setに入れていく。
最後にsetのサイズを出力すればよい。

ABC 430 B - Count Subgrid

ABC 430 B - Count Subgrid

ABC 430 B - Count Subgrid の考察記事です。

C 問題

Difficulty: 750 / NoviSteps: 2Q / 解答時間: 9:55

問題概要

a, bからなる長さ $N$ の文字列 $S$ と正整数 $A,B$ が与えられる。以下の条件を全て満たす整数組 $(l,r)$ の個数を求めよ。

$1\leq l \leq r \leq N$
$S$ の $l$ 文字目から $r$ 文字目までに含まれるaの個数が $A$ 以上
$S$ の $l$ 文字目から $r$ 文字目までに含まれるbの個数が $B$ 未満

解答方針

$l$ を固定して、条件を満たす $r$ の個数を数える。
$S$ $S$ の各文字までのaとbの個数の累積和 $a_i, b_i$ $a_{i}, b_{i}$ を取り、 $l$ $l$ を固定したときに以下の 2 条件を満たす $r$ $r$ をそれぞれ二分探索で求める。
- $a_{r+1} \geq a_{l} + A$
- $b_{r+1} < b_{l} + B$
これらの差が、条件を満たす $r$ の個数となる。

ABC 430 C - Truck Driver

ABC 430 C - Truck Driver

ABC 430 C - Truck Driver の考察記事です。

D 問題

Difficulty: 982 / NoviSteps: 1Q / 解答時間: 36:23

問題概要

数直線があり、最初は座標 $0$ に人 $0$ がひとりで立っている。

これから、人 $1,2,\dots,N$ がこの順に到着し、人 $i$ は座標 $X_i$ に立っていく。人が到着するたびに、以下の問いに答えよ。

現在数直線に人 $0,1,\dots,r$ の $r+1$ 人が立っているとする。
このとき、 $d_i$ を「人 $i$ に最も近い別の人までの距離」と定義する。
$\sum_{i=0}^r d_i$ を求めよ。

解答方針

新たに人が到着したときに、 $d_i$ の値に影響を受けるのは、新たに到着した人と(もし存在すれば)その左右の人だけである。
したがって、 $\sum d_i$ の差分として、新たに到着した人とその左右の人に関する $d_i$ の和の差分だけを考えればよい。
人の位置を管理するためにsetを用いることで、二分探索によって新たに到着した人の左右の人を高速に求めることができる。

ABC 430 D - Neighbor Distance

ABC 430 D - Neighbor Distance

ABC 430 D - Neighbor Distance の考察記事です。

E 問題

Difficulty: 1109 / NoviSteps: 1D / 解答時間: 21:42

問題概要

0, 1からなる長さの等しい文字列 $A,B$ が与えられる。

$A$ に対して以下の操作を $0$ 回以上行うとき、 $A=B$ とするために必要な最小の操作回数を求めよ。

$A$ の先頭の文字を末尾に移動させる。

解答方針

文字列 $A$ の左シフトを行うということで、これは $A + A$ という文字列から連続部分文字列 $B$ を探す問題に帰着できる。
これには色々な解き方があると思うが、私は KMP 法を用いて計算量 $O(\sum |A|)$ で解いた。

Z-algorithm なら実装が ACL にあるので瞬殺できるらしい。

ABC 430 E - Shift String

ABC 430 E - Shift String

ABC 430 E - Shift String の考察記事です。

成績

Contest Result - AtCoder

Contest Result - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

順位: 997th / 9766
Performance: 1370
Rating: 1202 → 1220 (+18) Highest 更新！

A ~ E まで割とスムーズに解くことができた。

今回参加者少なくね？