CodeQUEEN 2026 予選 (AtCoder Beginner Contest 462) コンテストまとめ

2026-06-14

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

コンテスト情報

CodeQUEEN 2026 -qual- (AtCoder Beginner Contest 462) - AtCoder

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

AtCoder

コンテスト時間: 2026-06-13(土) 21:00 ~ 2026-06-13(土) 22:40 (100分)

A 問題

Difficulty: 13 / NoviSteps: 7Q / 解答時間: 1:41

問題概要

英小文字と数字のみからなる文字列 $S$ が与えられるので、 $S$ から数字である文字だけを取り出し、元の順序のまま並べた文字列を出力せよ。

解答方針

char型の文字が数字であるかは、isdigit関数を使うと簡単に判定できる。

ABC 462 A - Secret Numbers

ABC 462 A - Secret Numbers の考察記事です。

Yuulis I/O

B 問題

Difficulty: 70 / NoviSteps: 5Q / 解答時間: 2:41

問題概要

$N$ 人がギフトを送り合っており、人 $i$ は人 $A_{i,1},A_{i,2},\ldots,A_{i,K_i}$ の $K_i$ 人にギフトを送った。

$i=1,2,\ldots,N$ に対し、人 $i$ にギフトを送った人を全て求めよ。

解答方針

$B_{ij}$ を「人 $i$ が人 $j$ からギフトを受け取った」ことを表す二次元配列とすると、 $1 \leq i \leq N, \, 1 \leq j \leq K_i$ に対して, 1次元配列 $B_{A_{i,j}}$ に $i$ を追加していけばよい。

サークルの新入生が二次元配列を知らない状態でこの問題をACしていたが、コードを見たら一次元配列を0で区切ることにより擬似的に二次元配列を実装していて、とても興味深かった。

ABC 462 B - Gift

ABC 462 B - Gift の考察記事です。

Yuulis I/O

C 問題

Difficulty: 298 / NoviSteps: 2Q / 解答時間: 7:51

問題概要

$2$ 次元平面上に $N$ 個の点があり、点 $i$ の座標は $(X_i,Y_i)$ である。ここで、 $X,Y$ はそれぞれ $(1,2,\ldots,N)$ の順列であることが保証される。

左下の頂点を $(0,0)$ 、右上の頂点を $(X_i,Y_i)$ とする $x$ 軸に平行な辺と $y$ 軸に平行な辺のみからなる長方形の内部(辺上を含まない)に、 $N$ 個の点をどれも含まないような $i$ の個数を求めよ。

解答方針

$i \: (1 \leq i \leq N)$ $i (1 \leq i \leq N)$ が条件を満たさない条件は
- $X_j < X_i$ かつ $Y_j < Y_i$ を満たす $j \: (1 \leq j \leq N, j \neq i)$ が存在すること
つまり、 $x$ 座標が小さい点の中に自身より $y$ 座標も小さい点があるかを判定すればよい。
$x$ 座標の値は順列であることを利用すると、 $x = 1, 2, \cdots, N$ の順に見ていき、その時点までの最小の $y$ を持っておけばよい。

ABC 462 C - Not Covered Points

ABC 462 C - Not Covered Points の考察記事です。

Yuulis I/O

D 問題

Difficulty: 798 / NoviSteps: 1Q / 解答時間: 14:32

問題概要

とある館で起きた殺人事件の犯人の候補が $N$ 人いる。人 $i$ は時刻 $S_i$ に館に入り、時刻 $T_i$ に館を出て、ほかの時刻には出入りしなかった。

犯行について以下のことが分かっている。

犯人はちょうど $2$ 人いる。
犯行はある整数時刻 $x$ に開始し、 $D$ 単位時間かけて行われ、時刻 $x + D$ に完了した。
犯人は $2$ 人とも犯行開始から犯行完了まで常に館にいた(犯行開始と同時に館に入ったり、犯行完了と同時に館を出たりした可能性もある)。

$N$ 人の犯人候補の中に犯人が $2$ 人ともいると仮定したとき、 $2$ 人の犯人の組み合わせと犯行開始時刻の組としてありうるものは何通りあるか求めよ。

解答方針

人 $i$ $i$ が時刻 $t$ $t$ に犯行可能である条件は以下の通り。
- $S_i \leq t \leq T_i - D$
ある時刻 $t$ に犯行可能な人の数を $c_t$ とすると、 $c_t$ 人の中から犯人を $2$ 人選ぶ方法は $\frac{c_t(c_t - 1)}{2}$ 通りあるので、全ての時刻 $t$ についてこれを足し合わせたものが求める答えとなる。
今回は時刻の上限が $10^6$ なので、長さ $10^6$ の配列を用意して、imos法の要領で $[S_i, T_i - D]$ を区間加算していくことで $c_t$ を求めることができる。

ABC 462 D - Accomplice

ABC 462 D - Accomplice の考察記事です。

Yuulis I/O

E 問題

Difficulty: 1226 / NoviSteps: 1Q / 解答時間: 38:50 + WA x1

問題概要

二次元平面上にコマが置かれており、はじめコマは座標 $(0,0)$ にある。「コマを上下左右に1マス移動させる」操作を $0$ 回以上行って、コマを座標 $(X,Y)$ に移動させるために必要なコストの総和の最小値を求めよ。

ただし、 $k$ 回目に行う操作にかかるコストは $k$ の偶奇によって異なり、それぞれ以下の通りである。

$k$ が奇数のとき：左右に移動させる場合のコストは $A$ 、上下に移動させる場合のコストは $B$ である。
$k$ が偶数のとき：左右に移動させる場合のコストは $B$ 、上下に移動させる場合のコストは $A$ である。

解答方針

対称性より、 $x = |X|, \, y = |Y|$ として考えてよい。
2手で斜め方向に1マス進むときの最小コストは $2 \min(A, B)$ であり、この移動方法は $\min(x, y)$ 回使える。
縦 or 横方向に2マス進むときの最小コストは $\min(A + B, 4 \min(A, B))$ であり、この移動方法は $\left\lfloor \frac{|x - y|}{2} \right\rfloor$ 回使える。
$|x - y|$ $∣ x - y ∣$ が奇数のときは、最後に1マス進む必要があるが、そのときのコストは単に1回移動するときと3回移動して遠回りする場合を比較する必要がある。
- $x > y$ なら横に1マス進む場合のコストは $\min(A, 3B)$ である。
- $x < y$ なら縦に1マス進む場合のコストは $\min(3A, B)$ である。