AtCoder Talent Quest 〜今から28卒には脱出してもらいます〜予選 #2（AtCoder Beginner Contest 480）コンテストまとめ

2026-10-20

謎の脱出ゲーム予選2回目。

また、今回からアルゴ部門における競技ルールに変更があったらしい。

AtCoder生成AI対策ルール - 20261014版 - AtCoderInfo

はじめにこのルールは、AtCoder Beginner Contest（以下、ABCとする）、（Division によらず）AtCoder Regular Contest（以下、ARCとする）およびAtCoder Grand Contest（以下、AGCとする）の開催中にのみ適用されるルールです。 AtCoder Heuristic Contestはこのルールの対象外であり、代わりにこちらのルールが適用されます。また、過去問を練習している際には適用されません。ABC,ARC,AGCの開催中においては、Unrated参加者にも適用されます。今回発表するルールは、2026年10月現在の生成AIの…

AtCoderInfo

コンテスト開始前にあらかじめ生成AIを用いて作成しておいたコードの使用は、上記の事前公開および参照URLの添付に関する条件を満たす場合に許容されます。

コンテスト情報

AtCoder Beginner Contest 480 - AtCoder

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

AtCoder

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

A 問題

Difficulty: 35 / NoviSteps: 6Q / 解答時間: 3:44

問題概要

$2 \times 2$ のグリッドがある。グリッドの各マスにはA, B, C, Dのいずれかがちょうど $1$ つ書かれており、 $4$ マスに書かれている文字は相異なる。

Aが書かれたマスとDが書かれたマスが隣接しているかどうかを判定せよ。

解答方針

以下の場合は条件を満たさないのでNoを出力する。それ以外はYesを出力すればよい。
- 左上がAで右下がD
- 右上がAで左下がD
- 左上がDで右下がA
- 右上がDで左下がA

A問題の癖にちょっと頭を使う必要がある。

ABC 480 A - ADjacent

ABC 480 A - ADjacent の考察記事です。

Yuulis I/O

B 問題

Difficulty: 201 / NoviSteps: 5Q / 解答時間: 9:22

問題概要

選挙に $N$ 人の候補者が立候補している。各候補者の名前は英小文字からなり、互いに異なる。

$M$ 枚の投票用紙が投じられ、投票用紙 $j$ には英小文字からなる文字列 $T_j$ が書かれていた。

$T_j$ が名前に完全に一致している候補者がいる場合、その候補者に $1$ 票が入る。そうでなく、 $T_j$ を $1$ 文字書き換えて名前が一致するような候補者がちょうど $1$ 人いる場合、その候補者に $1$ 票が入る。そうでない場合、それは無効票となる。

$i=1,2,\dots,N$ について、候補者 $i$ に何票入るかを求めよ。

解答方針

基本的には言われたことをやるだけだが、B問題にしては重めな実装が要求される。

ABC 480 B - Invalid Vote

ABC 480 B - Invalid Vote の考察記事です。

Yuulis I/O

C 問題

Difficulty: 625 / NoviSteps: 2Q / 解答時間: 8:38

問題概要

あるシャワーでは、時刻 $t$ にボタンを押すと時刻 $t$ から時刻 $t+K$ までの $K$ 秒間お湯が出る。お湯が出ているときに再びボタンを押した場合も、最後にボタンを押した時刻から $K$ 秒間お湯が出る。

$N$ 人の青木君がいて、 $i$ 人目の青木君は時刻 $A_i$ にボタンを $1$ 回押す。

時刻 $0$ から時刻 $T$ までの間に常にお湯が出ているようにするために、高橋君は最小で何回ボタンを押す必要があるかを求めよ。

解答方針

お湯が出ている時間を区間として考え、重なる区間をmergeする。
その後、区間 $[0, T]$ でまだ覆われていない区間の長さをそれぞれ $d$ とすれば、その区間に対して $\left\lceil \frac{d}{K} \right\rceil$ 回ボタンを押す必要がある。
これをすべての区間に対して行い、合計すればよい。
$A_i$ の昇順にソートし、左から順に処理していく。

サンプルケースでは、 $A_i$ がソートされていないケースや、 $\max A_i > T$ のケースがなくて優しくない。

ABC 480 C - Self-Stopping Shower

ABC 480 C - Self-Stopping Shower の考察記事です。

Yuulis I/O

D 問題

Difficulty: 864 / NoviSteps: 1Q / 解答時間: 30:41 + WA x1

問題概要

長さ $N$ の整数列 $(A_1,\dots,A_N)$ が与えられる。

以下の手順で長さ $\frac{N(N+1)}{2}$ の数列 $B$ を作る。

最初、 $B$ を空列とする。
$i=1,2,\dots,N$ の順に、 $B$ の末尾に $(A_1,\dots,A_i)$ を連結する。

以下の形式のクエリが $Q$ 個与えられるので、それぞれ処理せよ。

$L,R$ が与えられる。 $B_L+B_{L+1}+\dots+B_R$ を求めよ。

解答方針

$G_i = (A_1, A_2, \dots, A_i)$ とすると、 $G_i$ の末尾の項は $B$ の $C_i = \frac{i(i+1)}{2}$ 番目に現れる。
$f(x) = \sum_{i=1}^{x} B_i$ とおけば、各クエリでは $f(R) - f(L-1)$ を計算すればよい。
$x$ が $G_k$ に含まれる要素であるとすると、 $k = \min\{i \mid C_i \geq x\}$ と定義できるから、これは二分探索で求めることができる。
すると、 $G_k$ より前にある要素の個数は $C_{k-1}$ 個なので、要素 $x$ の $G_k$ の中での位置は $x - C_{k-1}$ と表せる。
したがって、 $f(x) = T_{k-1} + S_{x - C_{k-1}}$ $f (x) = T_{k - 1} + S_{x - C_{k - 1}}$ と書くことができる。ただし、
- $S_i = \sum_{j=1}^{i} A_j, \quad T_i = \sum_{j=1}^{i} S_j$

ABC 480 D - Concatenation of Prefixes

ABC 480 D - Concatenation of Prefixes の考察記事です。

Yuulis I/O

E 問題

Difficulty: 1355 / NoviSteps: 1D / 解答時間: 37:54

問題概要

以下の条件を全て満たす正整数列 $A=(A_1,\dots,A_{|A|})$ を良い数列と定める。

$|A|\geq 3$
$A$ は等差数列である。
$A_2-A_1 > 0$

良い数列のうち、要素の総積が $N$ 以下であるものの個数を求めよ。

解答方針

長さ $k$ の数列に対して、初項 $a$ の探索範囲は $1 \leq a \leq \sqrt[k]{N}$ であり、 $a$ を固定すれば二分探索で条件を満たす最大の公差 $d$ を求めることができる。
また、初項・公差がともに 1 の場合が積を最小にするので、 $k! \leq N$ $k! \leq N$ を満たす $k$ $k$ だけ調べれば十分。
- $20! \approx 2.43 \times 10^{18}$ なので、 $k < 20$ まで調べればよい。
長さ $k$ の数列について、初項は高々 $N^{\frac{1}{k}}$ 通り、二分探索は $O(\log N)$ 回、それぞれの判定に $O(k)$ 時間がかかるから、全体としては、 $O\left(\sum_{k=3}^{20}kN^{\frac{1}{k}}\log N\right) = O(N^{\frac{1}{3}}\log N)$ の計算量となる。