Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】AtCoder Beginner Contest 423 - 参加記 | 緑コーダーが解くAtCoder

AtCoder-ABC-コンテストまとめ AtCoder-ABC AtCoder ABC コンテストまとめ競技プログラミング

コンテスト時間: 2025-09-14(日) 21:00 ~ 2025-09-14(日) 22:40 (100分)

A - Scary Fee

Difficulty: ??? / NoviSteps: ???

解答時間: 4:16

ある銀行の通帳からお金を引き出すには、 $1000$ 円単位で引き出し額を指定したうえで、引き出し額 $1000$ 円あたり $C$ 円の手数料を残高から別途支払う必要がある。残高が $0$ 円未満になる引き出しを行うことはできない。通帳の残高が $X$ 円のとき、最大で何円を引き出せるか求めよ。

求める条件は、を整数として以下のように書ける。
- $1000m + Cm \leq X \iff m \leq \frac{X}{1000 + m}$
これを満たす $m$ の最大値は $\left\lfloor \frac{X}{1000 + m} \right\rfloor$ だから、これを $1000$ 倍したものを答えとすればよい。

B - Locked Rooms

Difficulty: ??? / NoviSteps: ???

解答時間: 3:16

$N + 1$ 個の部屋が一列に並んでおり、部屋の間には $N$ 個のドアがあり、ドア $i$ は部屋 $i - 1$ と部屋 $i$ の間にある。各ドアについて鍵の状態を表す値 $L_i$ が与えられ、 $L_i = 0$ のときドア $i$ の鍵は開いており、 $L_i = 1$ のとき閉まっている。2人の人がおり、1人は部屋 $0$ に、もう1人は部屋 $N$ にいる。それぞれの人は、ドア $i$ の鍵が開いているときに限り、部屋 $i - 1$ と部屋 $i$ の間を移動することができる。このとき、2人のいずれも到達できない部屋の個数を求めよ。

両端からの2人の動きをシミュレートし、到達できた部屋のインデックスを求める。
その後、両者の差から答えを求めればよい。

C - Lock All Doors

Difficulty: ??? / NoviSteps: ???

解答時間: 20:52

$N + 1$ 個の部屋が一列に並んでおり、部屋の間には $N$ 個のドアがあり、ドア $i$ は部屋 $i - 1$ と部屋 $i$ の間にある。各ドアについて鍵の状態を表す値 $L_i$ が与えられ、 $L_i = 0$ のときドア $i$ の鍵は開いており、 $L_i = 1$ のとき閉まっている。高橋君ははじめ部屋 $R$ におり、ドア $i$ の鍵が開いているときに限り部屋 $i - 1$ と部屋 $i$ の間を移動でき、部屋 $i - 1$ または部屋 $i$ にいるときに限りドア $i$ の鍵に対して開閉操作を行うことができる。すべてのドアの鍵が閉まった状態にするために行う鍵の開閉操作の回数として考えられる最小値を求めよ。

鍵が閉まっているドアの中で、インデックスが最小のものを $l$ 、最大のものを $r$ とする。
すると、高橋君が訪れるべき部屋の範囲は $[m_l, m_r ] = [ \min(l, r, R), \max(l, r, R) ]$ と求められる。
この範囲において、 $L_i = 1$ となる $i$ の個数を $c$ とすれば、 $m_r - m_l + c$ が答えとなる。

D - Long Waiting

Difficulty: ??? / NoviSteps: ???

解答時間: 32:29

同時に最大人の客を入れられるレストラン店があり、1つの待ち行列を管理している。時刻の時点で店内に客はおらず、待ち行列も空である。今日は個の団体客が来る予定であり、団体客の人数は人で、時刻に待ち行列の末尾に加わる。また、この団体客は入店してから単位時間後に退店する。それぞれの団体客は、以下の2条件が同時に満たされた最も早い時刻に、待ち行列を離れて入店する。
- その団体客は、待ち行列の先頭にいる。
- その団体客と、店内にいるすべての団体客の人数を合算すると、 $K$ 人以下になる。
それぞれの団体客が入店する時刻を求めよ。

団体客の「列に並ぶ」と「退店」をイベントとして扱い、priority_queueを用いながらイベントソートの要領でシミュレーションしていけばよい。
自作構造体をpriority_queueに突っ込む際は、比較関数を自分で定義する必要があるので注意(1敗)。

結果

Performance: 1072

1177 → 1167 (-10)

D問題の実装を手間取り過ぎた。