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

2026-07-14

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

コンテスト情報

AtCoder Beginner Contest 466 - AtCoder

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

AtCoder

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

A 問題

Difficulty: 16 / NoviSteps: 7Q / 解答時間: 1:47

問題概要

$N$ 個の選択肢があり、 $i$ 番目の選択肢を選んだときの嬉しさは $X_i$ である。どの選択肢を選んでも嬉しさが負になる場合はYesを、そうでない場合はNoを出力せよ。

解答方針

全ての $i$ について $X_i < 0$ が成り立つかどうかを判定すればよい。

ABC 466 A - Compromise

ABC 466 A - Compromise の考察記事です。

Yuulis I/O

B 問題

Difficulty: 37 / NoviSteps: 6Q / 解答時間: 2:12

問題概要

$N$ 個のボールがあり、 $i$ 番目のボールの色は $C_i$ 、大きさは $S_i$ である。 $k = 1, 2, \ldots, M$ について、色 $k$ のボールの大きさの最大値を出力せよ。

解答方針

ボールの色ごとにsetを用意して、その大きさを格納していく。
その後、各 $k$ について、対応するsetの末尾の値(最大値)を出力すればよい。

ABC 466 B - Representative Balls

ABC 466 B - Representative Balls の考察記事です。

Yuulis I/O

C 問題

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

問題概要

最初、あなたには整数 $N$ のみが与えられる。その後、あなたはジャッジに以下の質問を $2N$ 回まで行うことができる。

? i j: $1 \leq i < j \leq N$ を満たす整数 $i,j$ を選び、点 $i$ と点 $j$ の距離が $1$ 以下であるか質問する。

距離が $1$ 以下の $2$ 点組の個数 $X$ を出力せよ。

解答方針

点 $i$ に対して、自身よりも右側にあって、距離が $1$ 以下のもので最大の番号の点を $r_i$ とすると、点 $i$ と組にできる点の個数は $r_i - i$ 個であるから、これを全ての $i$ について求めて足し合わせればよい。
ここで、組 $(i, r_i)$ の距離が $1$ 以下であるなら組 $(i+1, r_i)$ の距離も $1$ 以下であることから、尺取り法の要領で $r_i$ を単調増加に求めることができる。
質問回数は最大でも $2(N-1)$ 回で済む。

ABCでは超久々のインタラクティブ問題でビビった。
...ただ、よく見たら単なる尺取り法だったので一安心。
インタラクティブ問題が忌避され過ぎて、D問題と Diff が逆転してしまっている。

ABC 466 C - Count Close Pairs

ABC 466 C - Count Close Pairs の考察記事です。

Yuulis I/O

D 問題

Difficulty: 494 / NoviSteps: 2Q / 解答時間: 17:15 + WA x1

問題概要

$N \times N$ のマス目があり、最初、マス目の上には何も置かれていない。

マス目に対して、以下の操作を $M$ 回行う。

上から $R_i$ 行目のマスに置かれているコマをすべて取り除く。
次に、左から $C_i$ 列目のマスに置かれているコマをすべて取り除く。
最後に、上から $R_i$ 行目かつ左から $C_i$ 列目のマスにコマを置く。

$M$ 回の操作の後でマス目に置かれているコマの個数を出力せよ。

解答方針

$i$ $i$ 回目の操作で駒がマス $(R_i, C_i)$ $(R_{i}, C_{i})$ に置かれたとすると、最終的にマス $(R_i, C_i)$ $(R_{i}, C_{i})$ に駒が残るためには、以下の両方の条件を満たす必要がある。
- 行 $R_i$ に対して最後に行われた操作が $i$ 回目の操作であること
- 列 $C_i$ に対して最後に行われた操作が $i$ 回目の操作であること
この条件を満たす $i$ の個数を数えればよい。

行・列の最後の操作回を記録する配列の長さを間違えて1ペナ。
なんでサンプル通っちゃうの...？

ABC 466 D - Placing Rooks

ABC 466 D - Placing Rooks の考察記事です。

Yuulis I/O

E 問題

Difficulty: 1027 / NoviSteps: 1Q / 解答時間: 33:06

問題概要

$N$ 枚のカードが並んでいて、カードには $1, 2, \ldots, N$ の番号が付けられている。カード $i$ の表面には整数 $A_i$ が、裏面には整数 $B_i$ が書かれており、はじめ、すべてのカードは表面が上を向いている。

これから、以下の操作を高々 $K$ 回行うことができる。

$1 \leq l \leq r \leq N$ なる整数 $l, r$ を選ぶ。 $l \leq i \leq r$ なる各整数 $i$ について、カード $i$ を裏返す。

操作を終えた後、各カードの上を向いている面に書かれている数の総和として考えられる最大値を求めよ。

解答方針

重複した区間の操作は考える必要がないことをに気づければ、 $D_i = B_i - A_i$ $D_{i} = B_{i} - A_{i}$ とおくことで、問題を以下のように言い換えることができる。
- 長さ $N$ の数列 $(D_1, D_2, \ldots, D_N)$ が与えられるので、高々 $K$ 個の互いに重ならない区間を選び、その区間に含まれる整数の総和を最大化せよ。
これは、以下の2つのDPテーブルを定義することで、動的計画法によって解くことができる。
- $\mathrm{dp}_0[i][j] :=$ ここまでに $j$ 個の区間を選び、カード $i$ を裏返さない場合の $D_i$ の総和の最大値
- $\mathrm{dp}_1[i][j] :=$ ここまでに $j$ 個の区間を選び、カード $i$ を裏返す場合の $D_i$ の総和の最大値
初期値は、 $\mathrm{dp}_0[0][0] = 0$ であり、他の値は $-\infty$ とする。
遷移は以下のようになる。
- $\mathrm{dp}_0[i][j] = \max(\mathrm{dp}_0[i-1][j], \mathrm{dp}_1[i-1][j])$
- $\mathrm{dp}_1[i][j] = \max(\mathrm{dp}_0[i-1][j-1], \mathrm{dp}_1[i-1][j-1]) + D_i$
最終的な答えは、
- $\max(\mathrm{dp}_0[N][j], \mathrm{dp}_1[N][j]) \quad (j = 0, 1, \ldots, K)$
- これに $\sum_{i=1}^{N} A_i$ を加えた値となる。