【AtCoder】AtCoder Beginner Contest 428 コンテストまとめ

コンテスト情報

AtCoder Beginner Contest 428 - AtCoder

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

AtCoder

コンテスト時間: 2025-10-18(土) 21:30 ~ 2025-10-18(土) 23:10 (100 分)

新ジャッジの不具合により、コンテスト開始時間が 30 分繰り下げられた模様。

A 問題

• Difficulty: 23 / NoviSteps: 6Q / 解答時間: 3:58

問題概要

高橋君はチャイムが鳴った直後から、以下の動作を繰り返し行う。

• 毎秒 $S$ メートルの速さで $A$ 秒間走る。その後の $B$ 秒間は静止する。

チャイムが鳴ってから $X$ 秒が経過するまでに、高橋君は合計何メートル走るか求めよ。

解答方針

• $(A+B)$秒のサイクルで走る距離と、余りの時間で走る距離を分けて計算すればよい。
• 答えは、$SA \cdot \left\lfloor \frac{X}{A+B} \right\rfloor + S \cdot \min(A, X \bmod (A+B))$ と表せる。

ABC 428 A - Grandma's Footsteps

ABC 428 A - Grandma's Footsteps の考察記事です。

yuulisio.com

B 問題

• Difficulty: 118 / NoviSteps: 5Q / 解答時間: 5:48

問題概要

英小文字からなる長さ $N$ の文字列 $S$ が与えられる。 $S$ の長さ $K$ の連続部分文字列の出現回数の最大値 $x$ を求め、その出現回数が $x$ となるような連続部分文字列を全て辞書順昇順に出力せよ。

解答方針

• 連想配列を使って連続部分文字列の出現回数を数え、その最大値を求める。
• その後、再度連想配列を先頭から走査して、出現回数が最大値となる連続部分文字列を順に出力していく。

ABC 428 B - Most Frequent Substrings

ABC 428 B - Most Frequent Substrings の考察記事です。

yuulisio.com

C 問題

• Difficulty: 483 / NoviSteps: 2Q / 解答時間: 11:31

問題概要

文字列 $T$ が次の条件を満たすとき、$T$ を良い括弧列と呼ぶ。

• 次の操作を $0$ 回以上繰り返すことで $T$ を空文字列にすることができる。
  • $T$ に連続部分文字列として含まれる () を選び、これを取り除く。

文字列 $S$ があり、 $S$ ははじめ空文字列である。 以下の 2 種類のクエリを与えられる順に $Q$ 個処理し、各クエリの直後に $S$ が良い括弧列であるかを判定せよ。

• 1 c: 文字 $c$ が与えられる。$c$ は ( または ) である。$c$ を $S$ の末尾に追加する。
• 2: $S$ の末尾の文字を削除する。

解答方針

• 括弧列にはstackを使うのが定石。まあここではvectorを使うのが楽なのだが。
• (を$1$、)を$-1$として扱い、vectorに追加・削除していく。
• これの累積 min が非負かつ、現時点の和が $0$ であれば良い括弧列である。

ABC 428 C - Brackets Stack Query

ABC 428 C - Brackets Stack Query の考察記事です。

yuulisio.com

D 問題

• Difficulty: 1239 / NoviSteps: 1D / 解答時間: --:--

問題概要

正整数 $x,y$ に対して $f(x,y)$ を以下で定義する。

• 十進表記の $x,y$ をそれぞれ文字列として解釈しこの順に連結して得られる文字列を $z$ とする。$z$ を十進表記の整数として解釈したときの値を $f(x,y)$ とする。

正の整数 $C, D$ が与えられます。以下を満たす整数 $x$ の個数を求めよ。

• $1 \leq x \leq D$
• $f(C, C+x)$ は平方数である。

解答方針

• E 問題の方針が先に見えたので後で帰ってこようと思ったら、時間切れで解けなかった。 → upsolve しました。

ABC 428 D - 183184

ABC 428 D - 183184 の考察記事です。

yuulisio.com

E 問題

• Difficulty: 1167 / NoviSteps: 1D / 解答時間: 57:56

問題概要

$N$ 頂点の木がある。 $v = 1, 2, \dots, N$ について次の問題を解け。

• 頂点 $1, 2, \dots, N$ のうち頂点 $v$ からの距離が最大となる頂点の番号を出力せよ。ただし、条件を満たす頂点が複数存在する場合は最も番号が大きい頂点を出力せよ。

解答方針

• 木上の距離が最大となる頂点を求めるということは、木の直径の両端を求めることと同値である。
• 木の直径を構成する 2 頂点は 2 回の BFS/DFS で求められるが、今回は各頂点$v$からの距離も必要なので、さらにもう 1 回 BFS/DFS を行う。

ABC 428 E - Farthest Vertex

ABC 428 E - Farthest Vertex の考察記事です。

yuulisio.com

成績

https://atcoder.jp/users/Yuulis/history/share/abc428

atcoder.jp

• 順位: 1706th / 12157
• Performance: 1280
• Rating: 1204 → 1212 (+8) Highest 更新！

入水 → 即落緑はなんとか回避。