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

2026-03-16

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

コンテスト情報

AtCoder Beginner Contest 448 - AtCoder

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

AtCoder

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

A 問題

Difficulty: 13 / NoviSteps: 7Q / 解答時間: 2:58

問題概要

長さ $N$ の整数列 $A$ と整数 $X$ が与えられる。 $i=1,2,\cdots,N$ の順に以下の処理を行え。

もし $A_i<X$ なら、 $X=A_i$ に更新した上で1を出力する。
そうでないなら0を出力する。

解答方針

問題タイトルにあるように、これはいわゆるchmin関数の処理である。
私はchminを以下のように実装しているので、chmin(X, A_i)がtrueならば1を出力し、そうでないなら0を出力すればよい。

1.template <typename T>
2.inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

ABC 448 A - chmin

ABC 448 A - chmin の考察記事です。

Yuulis I/O

B 問題

Difficulty: 68 / NoviSteps: 5Q / 解答時間: 6:02

問題概要

$M$ 種類のコショウがレストランに置いてあり、種類 $j$ のコショウは $C_j \mathrm{\, [g]}$ ある。

高橋君はこの店で $N$ 個の料理を注文した。相性の都合で $i$ 番目の料理には種類 $A_i$ のコショウしかかけることができず、 $i$ 番目の料理にかけられるコショウの量の上限は $B_i \mathrm{\, [g]}$ である。なお、種類 $j$ のコショウを合計 $C_j \mathrm{\, [g]}$ を超えてかけることはできない。

高橋君が料理にかけたコショウの量の合計を最大にしようとするとき、合計何 $\mathrm{g}$ のコショウを料理にかけることができるか求めよ。

解答方針

$i$ 番目の料理にかけられる最大のコショウの量は、 $v_i = \min(B_i, C_{A_i})$ である。
したがって、 $\sum_{i=1}^N v_i$ を求めればよい。
このとき、 $C_{A_i} \leftarrow C_{A_i} - v_i$ と更新しておくことを忘れないようにする。

ABC 448 B - Pepper Addiction

ABC 448 B - Pepper Addiction の考察記事です。

Yuulis I/O

C 問題

Difficulty: 262 / NoviSteps: 2Q / 解答時間: 9:26

問題概要

$N$ 個のボールが袋に入っており、ボール $i$ には整数 $A_i$ が書かれている。以下の $Q$ 個のクエリを処理せよ。

各クエリでは長さ $K$ の数列 $B$ が与えられるので以下の一連の操作を行うこと。ここで、 $B_i$ は全て $1$ 以上 $N$ 以下で、かつ相異なる。

まず、ボール $B_1, B_2, \cdots, B_K$ を全て袋から取り出す。
そして、現在の袋に入っているボールに書かれた整数の最小値を出力する。
その後、取り出した $K$ 個のボールを全て袋に戻す。

解答方針

袋の中に入っているボールに書かれた整数をmultisetで管理する。
クエリでは、まず $A_{B_1}, A_{B_2}, \cdots, A_{B_K}$ を順にeraseし、先頭要素を出力した後、 $A_{B_1}, A_{B_2}, \cdots, A_{B_K}$ を順にinsertする。
eraseの引数に $A_{B_i}$ のポインタを渡してあげることで、同じ値が複数あっても1つずつ消すことができる。

ABC 448 C - Except and Min

ABC 448 C - Except and Min の考察記事です。

Yuulis I/O

D 問題

Difficulty: 430 / NoviSteps: 1Q / 解答時間: 18:27 + WA x 1

問題概要

$N$ 頂点からなる木が与えられ、頂点 $i$ には整数 $A_i$ が書かれている。

$k=1,2,\cdots,N$ について以下の問題に答えよ。

頂点 $1$ から頂点 $k$ への単純パスに含まれる頂点について、同じ整数の書かれた異なる $2$ 頂点の組が存在すればYes、そうでないならNoと答えよ。

解答方針

与えられるのは木なので、頂点 $1$ を根とすれば任意の頂点 $k$ までの単純パスは一意に定まり、DFS を用いて全ての頂点に対する根からのパスを計算することができる。
ある頂点に到達したとき、ここまでのパス上の頂点にどの数字が何個あるかを記録する連想配列と、2個以上ある整数の種類数を記録する変数を保持する。
行きがけ時は頂点の値を連想配列に追加し、帰りがけ時には頂点の値を連想配列から削除することで、 DFS をしながら答えを求めることができる。