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

コンテスト情報

AtCoder Beginner Contest 426 - AtCoder

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

AtCoder

コンテスト時間: 2025-10-04(土) 21:00 ~ 2025-10-04(土) 22:40 (100 分)

A 問題

• Difficulty: 18 / NoviSteps: 7Q / 解答時間: 5:31

問題概要

ある OS のバージョンは古い順に Ocelot, Serval, Lynx である。 バージョン $X$ がバージョン $Y$ 以降のバージョンであるか判定せよ。

解答方針

• バージョン名を数値に対応させて比較すればよい。
• 連想配列を使うと実装がラクそう。

B 問題

• Difficulty: 25 / NoviSteps: 6Q / 解答時間: 2:07

問題概要

英小文字からなる長さ $3$ 以上の文字列 $S$ が与えられる。 $S$ はちょうど $2$ 種類の文字を含み $1$ 文字だけ他の文字と異なるので、その $1$ 文字を答えよ。

解答方針

• 連想配列を使って各文字の出現回数を数え、その回数が $1$ である文字を答えればよい。

C 問題

• Difficulty: 458 / NoviSteps: 2Q / 解答時間: 9:34

問題概要

ある OS のバージョンは $N$ 個あり、古い順に $1,2,\dots,N$ の番号がついている。 また、 PC が $N$ 台あり、初めは $i$ 番目の PC の OS のバージョンは $i$ である。 $Q$ 回の操作を順に行え。 $i$ 回目の操作は以下の通り。

• 現時点での OS のバージョンが $X_i$ かそれ以前の PC 全てを、バージョンを $Y_i(\geq X_i)$ にアップグレードする。その後、この操作でアップグレードを行った PC の台数を出力する。

解答方針

• OS のバージョンをkey、各バージョンの PC 台数をvalueとする連想配列を用いて操作をシミュレーションしていく。

D 問題

• Difficulty: 886 / NoviSteps: 1Q / 解答時間: --:--

問題概要

0および1からなる長さ $N$ の文字列 $S$ が与えられる。 これから $S$ に対して以下の操作を $0$ 回以上行い、 $S$ の全ての文字を同じ文字にしたい。 必要な操作回数の最小値を求めよ。

• 先頭または末尾の $1$ 文字を削除し、その文字を反転して好きな位置に挿入し直す。

解答方針

• 解けてないです。

E 問題

• Difficulty: 1584 / NoviSteps: 1D / 解答時間: 82:00

問題概要

高橋君と青木君が二次元平面上を歩く。 高橋君のスタート地点は $(TS_X, TS_Y)$、ゴール地点は $(TG_X, TG_Y)$ であり、青木君のスタート地点は $(AS_X, AS_Y)$、ゴール地点は $(AG_X, AG_Y)$ である。 二人は同時に各々のスタート地点を出発し、各々のゴール地点に向かって真っ直ぐ速さ $1$ で歩き続け、各々のゴール地点に到達すると停止する。 二人の移動中における両者の間のユークリッド距離の最小値を求めよ。

解答方針

• 状況を数式でモデル化することを考える。
• まず、$d_T = \|\bm{TS}-\bm{TG}\|$、$d_A = \|\bm{AS}-\bm{AG}\|$ とすれば、考えるべき時刻 $t$ の範囲は $0 \leq t \leq \max(d_T,d_A)$ である。
• 次に、高橋君の位置ベクトルを $\bm{p}(t)$、青木君の位置ベクトルを $\bm{q}(t)$ とすると、二人の距離は $\|\bm{p}(t)-\bm{q}(t)\|$ で表される。
  • このノルムの中身は「青木君の位置に対する高橋君の相対位置ベクトル」と考えることができるので、 $\bm{r}(t)=\bm{p}(t)-\bm{q}(t)$ とおく。
  • さらに $f(t)=\|\bm{r}(t)\|^2$ とおくと、 $f(t)$ は $t$ の二次関数で表され、この最小値が求める距離の二乗に等しい。
• $f(t)$ は $0 \leq t \leq \min(d_T, d_A)$ と $\min(d_T, d_A) < t \leq \max(d_T, d_A)$ の二つの区間に分けられるので、それぞれで最小値を求め、それらを比較することで答えを得る。
• 二次関数の最小値を求める上で私は解析的に解いたが、三分探索を用いても良さそう。

成績

Contest Result - AtCoder

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

AtCoder

• 順位: 1413th / 12446
• Performance: 1410
• Rating: 1178 → 1204 (+26) Highest 更新！

C++未経験で AtCoder を始めてから約 4 年半、ついに入水することができました！ 競プロと出会えて本当に良かったです。

これからも精進を続けていきます。