AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes) コンテストまとめ

2026-01-24

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

A 問題

Difficulty: 30 / NoviSteps: 6Q / 解答時間: 6:09 + WA x1

問題概要

$10^{100} \times 10^{100}$ のマス目があり、マス $(P,Q)$ を一番左上のマスとした $100\times 100$ マスの領域のみが黒く塗られており、それ以外のマスは白く塗られている。マス $(X,Y)$ が黒く塗られているか判定せよ。

解答方針

マス $(X, Y)$ は $P \leq X \leq P+99$ かつ $Q \leq Y \leq Q+99$ ならば黒、そうでなければ白で塗られている。

条件を $P \leq X \leq P+100$ かつ $Q \leq Y \leq Q+100$ としたせいで1ペナ。

ABC 441 A - Black Square

ABC 441 A - Black Square の考察記事です。

yuulisio.com

B 問題

Difficulty: 70 / NoviSteps: 6Q / 解答時間: 5:00

問題概要

AtCoder 国の公用語は、高橋語と青木語の $2$ つの言語である。高橋語では長さ $N$ の文字列 $S$ に含まれる英小文字のみを、青木語では長さ $M$ の文字列 $T$ に含まれる英小文字のみを用いる。

AtCoder 国の公用語に含まれる $Q$ 個の単語が与えられるので、それぞれの単語が次のうちどれに該当するか判定せよ。

高橋語の単語であることが確定する
青木語の単語であることが確定する
どちらともいえない

解答方針

$S, T$ $S, T$ に含まれる各アルファベットごとに、以下のように分類しておく。
- 高橋語にのみ含まれる
- 青木語にのみ含まれる
- 両方に含まれる or 両方に含まれない
その後、 $Q$ $Q$ 個の各単語について、それに含まれる各アルファベットを調べ、以下のように判定できる。
- 高橋語にのみ含まれるアルファベットが1つでもあれば「高橋語」と確定
- 青木語にのみ含まれるアルファベットが1つでもあれば「青木語」と確定
- どちらにも該当しなければ判断を保留し、最終的に保留の場合は「どちらともいえない」と判定

ABC 441 B - Two Languages

ABC 441 B - Two Languages の考察記事です。

yuulisio.com

C 問題

Difficulty: 406 / NoviSteps: 2Q / 解答時間: 15:50

問題概要

$N$ 個のカップがあり、 $i$ 番目 $(1\leq i\leq N)$ のカップには $A_i \, \mathrm{[ml]}$ の液体が入っている。また、これらのうちちょうど $K$ 個のカップには日本酒が入っており、それ以外には水が入っている。ただし、どのカップに日本酒が入っているかについては分からない。

高橋君は(1つ以上の)いくつかのカップを選んでそれらに入った液体をすべて飲むことができる。高橋君が確実に $X \, \mathrm{[ml]}$ 以上の日本酒を飲むためには、最低何個のカップを選ぶ必要があるか求めよ。

解答方針

カップを液体の量 $A_i$ の降順にソートする。
多い方から $m$ 個のカップを選んだとき、確実に飲める日本酒の量の合計は少ない方から $K-(N-m)$ 個のカップに入っている液体の量の合計となる。
したがって、 $\displaystyle \sum_{i=N-K+1}^{m} A_i \geq X$ を満たす最小の $m$ を求めれば良い。

ABC 441 C - Sake or Water

ABC 441 C - Sake or Water の考察記事です。

yuulisio.com

D 問題

Difficulty: 732 / NoviSteps: 2Q / 解答時間: 14:21

問題概要

$N$ 頂点 $M$ 辺の有向グラフがあり、 $i$ 番目の辺は頂点 $U_i$ から頂点 $V_i$ へ向かう辺で、コストは $C_i$ である。また、各頂点の出次数は $4$ 以下である。

次の条件をみたす頂点 $v$ をすべて求めよ。

頂点 $1$ $1$ から頂点 $v$ $v$ への経路であって、次の条件を共に満たすものが存在する。ただし、同じ辺を複数回通っても良いが、通るたびに回数とコストがカウントされる。
- ちょうど $L$ 回辺を通る。
- 通った辺のコストの総和が $S$ 以上 $T$ 以下である。

解答方針

「各頂点の出次数は $4$ 以下である」という条件が大きなヒント。
頂点 $1$ からスタートして、のべ $L$ 回の辺をを通るような経路は最大で $4^L$ 通りしかない。
制約から $L$ の最大値は $10$ なので、 $4^{10} \approx 10^6$ であり、DFSによる全探索が可能である。

ABC 441 D - Paid Walk

ABC 441 D - Paid Walk の考察記事です。

yuulisio.com

E 問題

Difficulty: 969 / NoviSteps: 1D / 解答時間: 30:04

問題概要

A, B, Cの $3$ 種類の文字からなる長さ $N$ の文字列 $S$ が与えられる。

$S$ の空でない連続する部分文字列であって、AがBよりも多く含まれるものの個数を求めよ。

解答方針

文字列 $S$ $S$ の各文字を次のように変換する。
- A → $+1$
- B → $-1$
- C → $0$
この置換により、AがBよりも多く含まれる部分文字列は、部分和が正となる区間に対応する。
さらにこの数列に対して累積和を取ることで、累積和配列の転倒数を求める問題に帰着でき、BIT(Fenwick Tree)を用いて $O(N \log N)$ の計算量で解くことができる。