SMBCプログラミングコンテスト #2（AtCoder Beginner Contest 481） コンテストまとめ

コンテスト情報

SMBC Programming Contest #2 (AtCoder Beginner Contest 481） - AtCoder

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

AtCoder

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

A 問題

• Difficulty: 17 / NoviSteps: 8Q / 解答時間: 0:54

問題概要

$1$ 以上 $9$ 以下の整数 $A,B$ が与えられるので、$A+B$ の値の桁数を求めよ。

解答方針

• 制約より、$A + B \geq 10$ ならば桁数は $2$、そうでなければ桁数は $1$ である。

ABC 481 A - Digits of A+B

ABC 481 A - Digits of A+B の考察記事です。

Yuulis I/O

B 問題

• Difficulty: 78 / NoviSteps: 5Q / 解答時間: 6:23

問題概要

$xy$ 平面上に $N$ 個の点があり、点 $i$ の座標は $(i,A_i)$ である。

$i=1,2,\ldots,N-1$ について点 $i$ と点 $i+1$ を線分で結び、$1$ 本の折れ線を作る。

この折れ線上(端点も含む)にある点のうち、$y$ 座標が $K$ であるものの個数を求めよ。

解答方針

• 頂点が $y = K$ に一致する場合と、線分の内部で $y = K$ を横切る場合を分けて数えればよい。

ABC 481 B - Polyline

ABC 481 B - Polyline の考察記事です。

Yuulis I/O

C 問題

• Difficulty: 187 / NoviSteps: 5Q / 解答時間: 3:40

問題概要

ある銀行口座では、開設時に名前と ID を $1$ 個ずつ割り当てる。 ID の値を選ぶときは、まだ ID として使われていない正の整数のうち最小のものを採用する。

はじめ、この銀行口座はひとつも開設されていない。

以下の出来事が $Q$ 回起きるので、順に処理せよ。

• カボチャがやってきて、名前 $s$ を名乗る。
  • 名前 $s$ が割り当てられた口座が存在する場合、その ID を出力する。
  • 名前 $s$ が割り当てられた口座が存在しない場合、名前 $s$ の口座を新規に $1$ 個開設し、その ID を出力する。

解答方針

• 名前をkey、 ID をvalueとする連想配列を用意して、クエリで与えられた名前が既に登録されているかどうかを確認する。
  • もし既に登録されていれば、対応する ID を出力する。
  • 逆に登録されていない場合は、次に割り当てるべき ID を保持しておき、その ID を出力した後に、連想配列に名前と ID の組を登録すればよい。

ABC 481 C - Bank Accounts

ABC 481 C - Bank Accounts の考察記事です。

Yuulis I/O

D 問題

• Difficulty: 581 / NoviSteps: 2Q / 解答時間: 11:16

問題概要

$N$ 個の惑星と $M$ 本の航路があり、航路 $i$ は惑星 $A_i$ から惑星 $B_i$ へと結ばれていて、各航路は一方通行である。

この空間において、宇宙船は以下の $2$ 種類の操作を行うことができる。

• 今いる惑星から航路が直接結ばれた惑星のうち、番号が最小の惑星に、燃料を消費せずに移動する。
• 今いる惑星から航路が直接結ばれた惑星を好きに選び、燃料を $1$ 消費して選んだ惑星に移動する。

宇宙船が惑星 $S$ から出発して惑星 $T$ に到着するまでに消費する燃料の量の最小値を求めよ。 到達が不可能な場合は代わりに $-1$ を出力すること。

解答方針

• 各有向辺に対してコスト $0$ または $1$ を設定する。ただし、コスト $0$ の辺は、各惑星から出る航路のうち、行き先の惑星番号が最小となる辺だけである。
• あとは、01-BFS で解くことができる。

ABC 481 D - Autopilot

ABC 481 D - Autopilot の考察記事です。

Yuulis I/O

E 問題

• Difficulty: 1326 / NoviSteps: 1D / 解答時間: 29:28 + WA x1

問題概要

$xy$ 平面上に $N$ 個の星があり、$i$ 個目の星は、座標が $(X_i,Y_i)$ である。

原点を通りどの星も通らない直線を $1$ 本引き、その直線によって分けられる二つの領域のうちどちらか一方の領域を選ぶとき、選んだ領域に含まれる星の個数としてありうる最大値を求めよ。

解答方針

• この問題は次のように言い換えられる。
  • 偏角が連続する $[0, \pi]$ 未満の範囲に含まれる点の個数の最大値を求めよ。
• $N$ 個の点を偏角ソートしておき、その配列を2周分に拡張してあげれば、尺取り法で全体を $O(N)$ で処理することができる。
• 本問では、「2点の偏角差が $2\pi$ 未満のとき、その偏角差が $\pi$ 未満である条件は、2点の外積が正であること」と言い換えられるので、これを使うと実装が楽になる。

ABC 481 E - Most Brilliant Starry Sky

ABC 481 E - Most Brilliant Starry Sky の考察記事です。

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

• 順位: 1219th / 10413
• Performance: 1504
• 1407 → 1417 (+10) Highest更新！

E問題まで割と早く行けたので、せっかくならF問題も解きたかった。