【AtCoder】日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415） - 参加記

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

A - Unsupported Type

Difficulty: 11 / NoviSteps: ???

解答時間: 1:06

Difficulty: 28 / NoviSteps: ???

解答時間: 3:55

一直線状の倉庫に偶数個の荷物が保管されており、倉庫の情報は文字列として与えられる。この倉庫にはロボットがあり、このロボットは以下の行動を倉庫から荷物が無くなるまで繰り返す。繰り返しの各回で運び出された2つの荷物が倉庫のどの区画にあったものかを求めよ。
- 荷物をその荷物がある区画番号の小さい方から2つ回収する。回収された荷物は倉庫の外へ運び出される。

Difficulty: 657 / NoviSteps: ???

解答時間: 22:14

$N$ 種類の薬品がある。ここで、1種類以上の薬品が混ざった状態 $i$ を、「 $i$ を2進法で表記した際に下から $k$ 桁目が $1$ ならば、薬品 $k$ が含まれている」と定義する。また、長さ $2^N - 1$ の文字列 $S$ が与えられ、 $S_i =$ 0なら状態 $i$ は安全であり、1ならば危険とする。
次の操作を使って薬品を混ぜ合わせるとき、全ての薬品が混ざった状態を作れるか判定せよ。
- まず、空の瓶を用意する。
- 次に、「まだ瓶に注いでいない薬品を1種類選択し、瓶に注ぐ」ことを繰り返す。このとき、瓶の中で混ざった薬品が危険な状態であってはならない。

$N$ の制約から、bitDP解法が濃厚。
DPテーブルを次のように定義する。
- $\mathrm{dp}_{\mathrm{bit}} :=$ 状態 $\mathrm{bit}$ を安全に作れるか？
初期化時は全てfalseとし、 $\mathrm{dp}_{0} =$ trueである。
遷移について、
- $\mathrm{dp}_{\mathrm{bit}} =$ falseなら、それ以降の遷移は不可。
- $\mathrm{dp}_{\mathrm{bit}} =$ trueなら、まだ注がれていない薬品で $S_i =$ 0を満たす $i$ について、 $\mathrm{dp}_{\mathrm{bit} \, \mathrm{OR} \, i} =$ true とする。
答えは、 $\mathrm{dp}_{2^N - 1}$ の真偽で判定できる。

Difficulty: 846 / NoviSteps: ???

解答時間: 32:45

あるコーラショップでは、コーラの空き瓶と新しい瓶入りコーラとの交換サービスを提供している。はじめ、高橋君は瓶入りコーラを本持っており、これから以下のいずれかの行動を回以上繰り返すことができる。このとき、手に入れるシールの枚数を最大化せよ。
- 持っている瓶入りコーラ1本を飲む。持っている瓶入りコーラの本数が $1$ 減り、空き瓶の本数が $1$ 増える。
- $1$ 以上 $M$ 以下の整数 $i$ を選ぶ。コーラショップに $A_i$ 本の空き瓶を渡し、引き換えに $B_i$ 本の瓶入りコーラおよび記念のシール1枚をもらう。

とりあえず、持っている瓶入りコーラは即座に全て飲み干し、空き瓶に変換することにする。したがって、単に空き瓶の本数 $b$ のみを考えればよい。
すると、ショップに空き瓶を $B_i$ 本渡したとき、 $A_i$ 本の空き瓶とシールが1枚もらえる。
したがって、シール1枚につき $A_i - B_i$ 本の空き瓶を消費することになる。
つまり、 $M$ 個の選択肢の中で $A_i - B_i$ が小さい選択肢から順に可能な限り繰り返せばよい。
この繰り返し回数は $1 + \left\lfloor \frac{b - A_i}{A_i - B_i} \right\rfloor$ で一気に計算できる。ちなみに、 $\left\lceil \frac{b - A_i}{A_i - B_i} \right\rceil$ で計算すると、分子が $0$ のときにバグる。

Difficulty: 1212 / NoviSteps: ???

解答時間: 35:18 + WA x1

のグリッドがあり、上から行目、左から列目のマスをと表す。各マスには何枚かのコインが置かれており、に置かれているコインは枚である。高橋君ははじめにおり、枚のコインを持っている。これから各日目には以下のことが順に起こる。高橋君が一度も空腹で倒れることなく日間を終えられるような方法が存在するとき、はじめに持っているコインの枚数の最小値を求めよ。
- 高橋君が、そのときいるマスに置かれたコインを全て回収する。
- 高橋君が、手持ちのコインを $P_k$ 枚消費してご飯を買う。ただし、所持しているコインが $P_k$ 枚未満の場合、ご飯を買うことはできず倒れてしまう。
- $k \lt H+W-1$ ならば、高橋君が、そのときいるマスの1つ右または下のいずれかのマスを選んでそこに移動する。 $k=H+W-1$ ならば、何もしない。

「条件を満たす $x$ の最小化・最大化」は往々にして $x$ の範囲を二分探索で求められることが多い。今回もその方針で行く。
条件を満たすか否かは、以下のようなDPテーブルを作って考える。
- $\mathrm{dp}_{i, j} :=$ マス $(i, j)$ において、ご飯を買った後の所持コインの最大値
初期化時は全て $-1$ とし、 $\mathrm{dp}_{0, 0} = x + A_{0, 0} - P_0$ である。ただし、この時点で $\mathrm{dp}_{0, 0} \lt 0$ ならfalseを返して判定処理を終了する。
遷移は、マスにどのようにして到達したかを考えると、以下のようになる。
- $\mathrm{dp}_{i, j} = \max(\mathrm{dp}_{i-1, j}, \mathrm{dp}_{i, j-1}) + A_{i, j} - P_k \quad (k = i+j)$
- ただし、 $\mathrm{dp}_{i, j} \lt 0 \Rightarrow \mathrm{dp}_{i, j} = -1$
ここで、 $\max(\mathrm{dp}_{i-1, j}, \mathrm{dp}_{i, j-1}) \lt 0$ のときは $(i, j)$ に到達不可なのでスキップすることに注意(1敗)。
最終的な判定は、 $\mathrm{dp}_{H-1, W-1} \geq 0$ の真偽で行える。
二分探索はいつものめぐる式で。