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

2026-03-01

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

コンテスト情報

AtCoder Beginner Contest 447 - AtCoder

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

AtCoder

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

A 問題

Difficulty: 15 / NoviSteps: 7Q / 解答時間: 2:12

問題概要

$N$ 個の座席が横一列に並んでいて、各座席には最大で $1$ 人まで座ることができる。隣り合う $2$ つの席の両方に人が座らないように $M$ 人を座席に座らせることができるかどうか判定せよ。

解答方針

左から1つおきに座らせていくことを考えると、 $\left\lceil \frac{N}{2} \right\rceil \geq M$ ならばYesと判定できる。

ABC 447 A - Seats 2

ABC 447 A - Seats 2 の考察記事です。

Yuulis I/O

B 問題

Difficulty: 50 / NoviSteps: 6Q / 解答時間: 4:32

問題概要

英小文字からなる文字列 $S$ が与えられる。 $S$ の中で出現回数が最も多い文字をすべて取り除き、残った文字を元の順序を保ったまま連結して出力せよ。出現回数が最大の文字が複数種類ある場合は、そのすべてを取り除くこと。

解答方針

$S$ の各文字の出現回数を数え、最大の出現回数を求める。
$S$ を先頭から走査し、出現回数が最大の文字でないものを出力していく。

ABC 447 B - mpp

ABC 447 B - mpp の考察記事です。

Yuulis I/O

C 問題

Difficulty: 326 / NoviSteps: 2Q / 解答時間: 12:20

問題概要

英大文字からなる文字列 $S,T$ が与えられる。あなたは以下の $2$ 種類の操作を好きな順序で $0$ 回以上行うことができる。

$S$ の好きな位置(先頭および末尾を含む)に文字Aを $1$ つ挿入する。
$S$ に含まれる文字Aを $1$ つ選んで削除する。なお、残った文字は元の順序を保ったまま連結される。

$S$ を $T$ に一致させることが可能かどうか判定し、可能な場合は必要な操作回数の合計の最小値を求めよ。

解答方針

まず、 $S$ と $T$ の両方から文字Aを全て取り除いた文字列をそれぞれ $S', T'$ とする。 $S' \neq T'$ ならば、 $S = T$ にすることは不可能。
そうでないとき、 A以外の文字で $S$ と $T$ を分割し、それぞれの区間に含まれるAの個数を数える。 $S$ の区間に含まれるAの個数を $s_i$ 、 $T$ の区間に含まれるAの個数を $t_i$ とする。
区間ごとに、 $s_i$ と $t_i$ の差の絶対値を足し合わせる。これが求めるべき答えとなる。

ABC 447 C - Insert and Erase A

ABC 447 C - Insert and Erase A の考察記事です。

Yuulis I/O

D 問題

Difficulty: 430 / NoviSteps: 2Q / 解答時間: 9:18

問題概要

A, B, Cの $3$ 種類の文字のみからなる文字列 $S$ が与えられる。文字列 $S$ に対して、以下で定義される操作を最大で何回操作を行うことができるかを求めよ。

$1 \le i \lt j \lt k \le |S|$ かつ $S_i =$ A, $S_j =$ B, $S_k =$ Cを満たす $(i, j, k)$ の組を選び、 $S$ の $i, j, k$ 文字目を取り除く。残った文字を元の順序を保ったまま左に詰める。

解答方針

以下の3つのカウンターを用意しておく。
- cnt_A: これまでに見た文字のうち、Aの個数
- cnt_AB: これまでに見た文字のうち、Aの後にBが出現するパターンの個数
- cnt_ABC: これまでに見た文字のうち、Aの後にBが出現し、さらにその後ろにCが出現するパターンの個数
$S$ $S$ の先頭から順に文字を見ていき、以下の処理を行う貪欲法が成立する。
- 文字がAのとき、cnt_Aを $1$ 増やす。
- 文字がBのとき、cnt_Aを $1$ 減らし、cnt_ABを $1$ 増やす。
- 文字がCのとき、cnt_ABを $1$ 減らし、cnt_ABCを $1$ 増やす。
最終的に、cnt_ABCが求めるべき答えとなる。

ABC 447 D - Take ABC 2

ABC 447 D - Take ABC 2 の考察記事です。

Yuulis I/O

E 問題

Difficulty: 955 / NoviSteps: 1Q / 解答時間: 31:08 + WA x 1

問題概要

$N$ 頂点 $M$ 辺からなる単純連結無向グラフ $G$ が与えられる。各辺にはコストとよばれる値が定められており、辺 $i$ のコストは $2^i$ である。

今から、 $G$ の連結成分の個数がちょうど $2$ になるように、 $G$ の辺のうちいくつかを選んで削除する。削除する辺のコストの和としてありうる最小値を $998244353$ で割った余りを求めよ。

解答方針

操作を逆から考え、初めに $N$ 個の頂点をそれぞれ独立な連結成分とする。
辺のコストの大きい順に見ていき、その辺が接続する2つの頂点が異なる連結成分に属しているなら、両者を merge する。ただし、連結成分の個数が $2$ 個になったときは打ち切る。
その後、全ての辺を順に見ていき、両端点が異なる連結成分に属している辺のコストを足し合わせる。