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

コンテスト情報

AtCoder Beginner Contest 449 - AtCoder

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

AtCoder

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

A 問題

• Difficulty: 30 / NoviSteps: ??? / 解答時間: 1:26

問題概要

正整数 $D$ が与えられるので、直径が $D$ の円の面積を求めよ。

解答方針

• $\displaystyle \pi \left(\frac{D}{2}\right)^2 = \frac{\pi D^2}{4}$ を計算して出力すればよい。

ABC 449 A - π

ABC 449 A - π の考察記事です。

Yuulis I/O

B 問題

• Difficulty: 45 / NoviSteps: ??? / 解答時間: 3:52

問題概要

$H$ 行 $W$ 列のブロックからなる長方形状のチョコレートがある。

$Q$ 個のクエリが与えられるので、順に処理せよ。 クエリは以下のいずれかの形式で与えられる。

• 1 R: 下 $R$ 行のチョコレートのブロックの個数を求め、それらを食べる。
• 2 C: 右 $C$ 列のチョコレートのブロックの個数を求め、それらを食べる。

解答方針

• クエリを処理するごとに、$H, W$ をそれぞれ更新していく。
• クエリ1では、$RW$ を出力した後に $H \leftarrow H-R$ とすればよい。
• クエリ2では、$HC$ を出力した後に $W \leftarrow W-C$ とすればよい。

ABC 449 B - Deconstruct Chocolate

ABC 449 B - Deconstruct Chocolate の考察記事です。

Yuulis I/O

C 問題

• Difficulty: 330 / NoviSteps: ??? / 解答時間: 5:32

問題概要

英小文字からなる長さ $N$ の文字列 $S$ が与えられるので、整数の組 $(i, j)$ であって、以下の条件をすべて満たすものの個数を求めよ。

• $1 \leq i \leq j \leq N$
• $S_i = S_j$
• $L \leq j - i \leq R$

解答方針

• 各アルファベットについて、 $S$ での出現位置をそれぞれ小さい順に頻度配列として記録していく。
• $S$ の $i$ 文字目に注目したとき、 $j$ として見るべき範囲は $i + L \leq j \leq i + R$ である。
• したがって、頻度配列の $S_i$ の要素について $i + L$ 以上 $i + R$ 以下のものがいくつあるかを二分探索で数え、それを全ての $i$ について合計すればよい。

ABC 449 C - Comfortable Distance

ABC 449 C - Comfortable Distance の考察記事です。

Yuulis I/O

D 問題

• Difficulty: 927 / NoviSteps: ??? / 解答時間: 45:48

問題概要

$2$ 次元座標平面があり、座標が $(x, y)$ である格子点は $\max(|x|, |y|)$ が偶数のとき黒、奇数のとき白で塗られている。

$L \leq x \leq R$ かつ $D \leq y \leq U$ を満たす整数の組 $(x, y)$ のうち、座標 $(x, y)$ が黒く塗られているものの個数を求めよ。

解答方針

• 「$f(X, Y) :=$ $0 \leq x \leq X$ かつ $0 \leq y \leq Y$ の範囲の格子点で、黒く塗られているものの個数」と定義する(ただし、 $X \leq Y$)。
  • $0 \leq y \leq X$ の正方形部分の黒の点の個数 $c_1$ は、 $c_1 = \begin{cases} \dfrac{(X+1)(X+2)}{2} & (X \text{ が偶数}) \\ \dfrac{X(X+1)}{2} & (X \text{ が奇数}) \end{cases}$ と求められる。
  • $X \leq y \leq Y$ の長方形部分の黒の点の個数 $c_2$ について、$c_2 = \left( \left\lfloor \dfrac{Y}{2} \right\rfloor - \left\lfloor \dfrac{X}{2} \right\rfloor \right) (X + 1)$
  • $f(X, Y) = c_1 + c_2$
• 与えられた矩形範囲を第1象限に分割・移動する。
• 矩形範囲 $0 \leq l \leq x \leq r$ かつ $0 \leq d \leq y \leq u$ における黒の点の個数は、包除原理により $f(r, u) - f(l-1, u) - f(r, d-1) + f(l-1, d-1)$ と求められる。

ABC 449 D - Make Target 2

ABC 449 D - Make Target 2 の考察記事です。

Yuulis I/O

成績

Contest Result - AtCoder

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

AtCoder

• 順位: 1974th / 12335
• Performance: 1333
• 1242 → 1251 (+9)

D問題、これで緑下位Diffか。

方針は悪くなかったと思うけど、実装に時間かかりすぎたかもしれない。