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

2026-07-07

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

A 問題

Difficulty: 12 / NoviSteps: 8Q / 解答時間: 1:01

問題概要

正の整数 $A,B$ が与えられるので、 $\displaystyle A > B \times \frac{2}{3}$ であればYesを、そうでなければNoを出力せよ。

解答方針

$\displaystyle A > B \times \frac{2}{3} \iff 3A > 2B$ なので、これを満たすならYes、そうでなければNoを出力すればよい。

ABC 465 A - Supermajority

ABC 465 A - Supermajority の考察記事です。

Yuulis I/O

B 問題

Difficulty: 56 / NoviSteps: 6Q / 解答時間: 10:34 + WA x1

問題概要

ある駐車場に駐車するときの料金は以下の通りである。

$L$ 時ちょうどから $R$ 時ちょうどまでのあいだは、 $1$ 時間停めるごとに $X$ の料金がかかる
上に該当しない時間のあいだは、 $1$ 時間停めるごとに $Y$ の料金がかかる

この駐車場に、日をまたぐことなく車を $A$ 時ちょうどから $B$ 時ちょうどまで停めたとき、料金はいくらになるか求めよ。

解答方針

駐車時間のうち、1時間当たりの駐車料金が $X$ になる時間は、 $\max(0, \min(B, R) - \max(A, L))$ で計算できる。
また、1時間当たりの駐車料金が $Y$ になる時間は、駐車時間から上記の時間を除いたものとなる。

最初はご丁寧に場合分けを始めてしまったが、 $A = L$ や $B = R$ の場合を考慮し忘れて1ペナ。

ABC 465 B - Parking 2

ABC 465 B - Parking 2 の考察記事です。

Yuulis I/O

C 問題

Difficulty: 443 / NoviSteps: 2Q / 解答時間: 10:12

問題概要

整数 $N$ とo、xからなる長さ $N$ の文字列 $S$ が与えられる。長さ $N$ の整数列 $A=(1,2,\ldots,N)$ に対して、 $k=1,2,\ldots,N$ の順に以下の操作を行う:

$S_k=$ oである場合、 $A$ の先頭 $k$ 項を反転する。
$S_k=$ x である場合、何もしない。

全ての操作を終えた後の $A$ を求めよ。

解答方針

「空配列に対して、 $k=1,2,\ldots,N$ の順に、 $S_k$ がoなら先頭に $k$ を追加し、 $S_k$ がxなら末尾に $k$ を追加する」と操作を言い換える。
あとはこの配列をdequeで管理すればよい。
サンプルケースから何となくエスパーできるかもしれない。

ABC 465 C - Reverse Permutation

ABC 465 C - Reverse Permutation の考察記事です。

Yuulis I/O

D 問題

Difficulty: 839 / NoviSteps: 1Q / 解答時間: 19:22

問題概要

整数 $X,Y$ と $2$ 以上の整数 $K$ が与えられる。

変数 $x$ があり、はじめ $x=X$ である。これから、 $x$ に対して以下の操作を $0$ 回以上何回でも行うことを考える。

$\displaystyle \left\lfloor \frac{x}{K} \right\rfloor=y$ または $\displaystyle \left\lfloor \frac{y}{K} \right\rfloor=x$ を満たす整数 $y$ を選び、 $x$ の値を $y$ に置き換える。

$x=Y$ とするために必要な操作回数の最小値を求めよ。

解答方針

$x, y$ $x, y$ ともに $K$ $K$ で割るのは変わらないので、とりあえず $X, Y$ $X, Y$ をそれぞれ $K$ $K$ で割り続けてみる。
- 例えばサンプルケース1の3番目のテストケースなら、

\begin{align*} 842 & \to 120 \to 17 \to 2 \to 0 \\ 180 & \to 25 \to 3 \to 0 \end{align*}

したがって、 $X = Y$ となるまで「両者の大きい方を $K$ で割った商に置き換える」操作を繰り返し、その回数を記録すればよい。

ABC 465 D - X to Y

ABC 465 D - X to Y の考察記事です。

Yuulis I/O

E 問題

Difficulty: 1417 / NoviSteps: 1D / 解答時間: 55:06

問題概要

$1$ 以上 $N$ 以下の整数 $x$ であって、以下の $3$ つの条件のうちちょうど1つだけを満たすものの個数を $998244353$ で割った余りを求めよ。

$x$ は $3$ の倍数である
$x$ の十進表記には $3$ が含まれる
$x$ の十進表記にはちょうど $3$ 種類の数字が使われる

解答方針

以下のDPテーブルを考えて、桁DPを行う。
- $\mathrm{dp}[i][\mathrm{smaller}][\mathrm{leading}][\mathrm{mod}][\mathrm{has3}][\mathrm{bit}]$
遷移はそこまで複雑ではないが、 $\mathrm{leading} = 1$ の間は $\mathrm{bit}$ を更新しないことに注意。
$N$ $N$ の桁数を $l$ $l$ として、 $l$ $l$ 桁目までの更新が終わったら、 $\mathrm{dp}[l][\mathrm{smaller}][0][\mathrm{mod}][\mathrm{has3}][\mathrm{bit}]$ $dp [l] [smaller] [0] [mod] [has3] [bit]$ の各状態について、以下の条件のうちちょうど一つだけを満たす場合に限り、答えにその状態の値を加算する。
- $\mathrm{mod} = 0$
- $\mathrm{has3} = 1$
- $\mathrm{popcount}(\mathrm{bit}) = 3$