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

2026-06-08

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

コンテスト情報

AtCoder Beginner Contest 461 - AtCoder

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

AtCoder

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

A 問題

Difficulty: 12 / NoviSteps: 9Q / 解答時間: 2:00

問題概要

威力が $D$ 以下の攻撃をすべて防ぐが、それより大きい攻撃は防ぐことができない鎧がある。威力 $A$ の攻撃を防ぐことができるか、判定せよ。

解答方針

$A \leq D$ ならYes、そうでなければNoを出力すればよい。

ABC 461 A - Armor

ABC 461 A - Armor の考察記事です。

Yuulis I/O

B 問題

Difficulty: 34 / NoviSteps: 7Q / 解答時間: 1:44

問題概要

$N$ 人の木こりが斧を $1$ 個ずつ持っていたが、全員が斧を池に落としてしまった。池には $N$ 個の斧 $1,2,\dots,N$ が沈んでおり、各木こり $i$ は「自分が持っていた斧は斧 $A_i$ である」と主張している。一方、この池の女神は、各斧 $i$ を持っていたのは木こり $B_i$ であることを知っている。

$N$ 人の木こり全員が本当のことを言っているかどうかを判定せよ。

解答方針

各木こり $i$ について、 $A_i = B_i$ であるかを確認すればよい。

ABC 461 B - The Honest Woodcutters

ABC 461 B - The Honest Woodcutters の考察記事です。

Yuulis I/O

C 問題

Difficulty: 332 / NoviSteps: 3Q / 解答時間: 13:02

問題概要

$N$ 個の宝石があり、 $i$ 番目の宝石の色は $C_i$ で価値は $V_i$ である。この $N$ 個の宝石の中から、宝石の色を $M$ 種類以上として $K$ 個を選ぶことを考える。このとき、選んだ宝石の価値の総和としてありうる最大値を求めよ。

解答方針

色の種類を無視すれば、単純に価値の高い方から $K$ 個を選べばよい。
そのような選び方で色の種類数が足りない場合は、まだ選ばれていない色の宝石を追加する必要があり、代わりに同じ色で2個目以降の宝石を削除する。
したがって、まだ選んでいない色から「その色で最も価値が高い宝石」を追加候補にし、すでに選んでいる宝石のうち「同じ色で2個目以降の宝石」を削除候補にした後、最も価値の高い追加候補と、最も価値の低い削除候補を交換するような操作を、色の種類数が $M$ 以上になるまで繰り返せばよい。

ABC 461 C - Variety

ABC 461 C - Variety の考察記事です。

Yuulis I/O

D 問題

Difficulty: 914 / NoviSteps: 1Q / 解答時間: 45:34

問題概要

$H \times W$ のグリッドがあり、各マスには $0$ または $1$ の整数が書き込まれている。書き込まれた整数の総和が $K$ となる長方形領域がいくつあるか求めよ。

解答方針

考える領域の上下を固定して、列ごとの累積和をとる。
すると、求める長方形領域の条件は「列ごとの累積和」の和が $K$ となるような区間の個数を求めることに帰着される。
ある配列 $A$ $A$ と整数 $x$ $x$ に対して、 $\displaystyle \sum_{i=l}^{r} A_i \geq x$ $i = l \sum r A_{i} \geq x$ が成り立つような $(l, r)$ $(l, r)$ の組の個数を数える関数を $\mathrm{count}(x)$ $count (x)$ とすると、求める答えは $\mathrm{count}(K) - \mathrm{count}(K + 1)$ $count (K) - count (K + 1)$ となる。
- $\mathrm{count}(x)$ は尺取り法の要領で計算量 $O(W)$ で求めることができる。