geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Biginner Contest 257 参加記録

ABC 二分探索 BFS 貪欲法 ダイクストラ

コンテスト中AC:A〜D
コンテスト後にEを自力ACできたので、こちらに書いておきます。

2022/07/01 追記 Fも自力で解けたため追記

C - Robot Takahashi

誤った解法でかなり時間をロスしてました。
また、コンテスト後にこの記事を書いていて、嘘解法であることがわかりました。コンテスト中の嘘解法とコンテスト後の正しいと思われる解法書いておきます。

W_iを大人と子供に分けます。
大人を
A=\{A_1,\ \cdots ,\ A_M\}
子供を
C=\{C_1,\ \cdots ,\ C_K\}

とします。
A,Cのいずれかが空の場合は、N人達成可能です。以下、そうでない場合を考えます。

大人の判定が正しくなる個数を全探索します。この場合、実数xの候補として、Aの要素のみを考えればよいです。

例えば、C_j \lt A_i \leq C_{j+1}という位置にA_iが居るとします。C_j \lt x \leq C_{j+1}の範囲でxを動かしても、子供の判定結果に影響を与えません。また、C_j \lt x \leq A_{i}の範囲にすると、A_iの判定を正しいものにできます。
よって、x=A_iとして、損をすることがないです(A_i = C_{j+1}のケースで少し悩みましたが、これも問題ありませんでした)。
なお、C_jやC_{j+1}が存在しない場合でも、同様となります。

以上から、x=A_1,\ \cdots ,\ A_Mとした時に正しく判定できる人数をカウントします。Aの人数は明らかです。Cの人数は、Cを予めソートしておくことで、二分探索可能です。

コンテスト中の実装は以下のような感じです。
Submission #32731821 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

コンテスト後に、この実装の反例が存在することがわかりました。

5
00100
10 20 30 40 50

このケースでは、実装xをx\gt 50として、子供の判定を全て正しくすることで、正しい判定を4人にできます。
しかし、最初の実装だと、3人になってしまいます。
なぜこのようなことになるかというと、大人の正しい判定が0人となる場合を考慮できていないためです。

これを正しく判定するためには、Aに\inftyを入れておけばよいです(\inftyを正しい判定となる人数に含めてはだめです)。

Submission #32806566 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

D - Jumping Takahashi 2

Sは、ある値以上ならOKで、それ未満はNGという境界があります。そこで、二分探索できないか検討します。

二分探索の判定処理にかかる見積もります。
まず、以下が言えます。

  • ジャンプ力xで全てのジャンプ台に到達できるかは、始点となるジャンプ台を1,\ \cdots ,\ Nまで全探索し、どれか1つでも達成できればよい。

次に、

  • ジャンプ力x、始点sですべてのジャンプ台に到達できるかは、幅優先探索によりO(N+M)で判定できる。

ここで、Mは辺数であり、今回の場合全2点間に辺がある完全グラフとみなせるため、M=\frac{N(N-1)}{2}です。よって、今回はO(N^2)です。

以上から、ジャンプ力xで全てのジャンプ台に到達できるかという判定にかかる計算量はO(N^3)です。

ジャンプ力として考えられる最大をS_{max}とすれば、全体の時間計算量はO(N^3 log{S_{max})}です。
S_{max}=10^{18}とかでも、間に合うと想定でき、二分探索で問題ないことがわかります。

ここからが割と重要で、コンテスト中4回WAを出しました。S_{max}をいい加減に大きくするとオーバーフローします。

というのも、幅優先探索で、ジャンプ台間で移動可能かの判定には問題文中の以下の式を使います。

P_i S \geq |x_i - x_j|+|y_i - y_j|

P_iは最大で10^9になるため、ジャンプ力Sが10^{10}くらいになるとP_i Sがオーバーフローしてしまいます。

そこで、S_{max}をしっかり目に見積もります。
(-10^9,\ -10^9)と(10^9,\ 10^9)間を移動する時、

|x_i - x_j|+|y_i - y_j| = 4\times 10^9となり、右辺が最大です。また、P_i = 1の場合、

S \geq 4\times 10^9かどうかを判定することになるので、S_{max}は4\times 10^9を見積もれば良いことになります。実際にこれでACできました。

その他の方法としては、__builtin_smull_overflowでオーバーフロー判定し、オーバーフローする場合は常に移動出来ることにしておいても良いかもしれません。
Submission #32746202 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

E - Addition and Multiplication 2

10進数X,Yについて、考えます。Xの上からi桁目(の整数)をX_iという様に表現します。

X\gt Yの時、以下が言えます。

  1. Xの桁数がYの桁数より真に大きい
  2. XとYの桁数が等しいとき、上からi-1桁目までが等しいなら、X_i \gt Y_i (但し、便宜上X_0 = Y_0)

1番目の条件より、出来るだけxの桁数を大きくすればよいです。そこで、支払う金額が最小の整数dを選び、可能な限り置き換えを行います。なお、支払う金額が最小のものが複数ある場合、そのうち最大の整数を選びます。

次に2番目の条件より、xの最上位桁から優先的にdより大きい整数に変更できないか検討します。変更後の整数についても大きい方から優先的に選びます。なお、xの桁の2つ分を1つの別の整数に変更すると、桁数が減るので、変更は1対1で行います。

残金がなくなり、変更操作ができなくなった時のxが答えです。

i桁目についての具体的な変更方法は、残金をN'とすると、C_dを払い戻したと考え、N'+C_d \geq C_jなら、i桁目をjとし、残金をN' \leftarrow N' + C_d - C_jと更新します。
Submission #32759248 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

F - Teleporter Setting

町を頂点、テレポーターを辺とした無向グラフとみなします。移動時間は辺の距離とみなします。
一旦簡単のため、全て連結であるとしておきます。

iに全ての未接続だった辺が繋がった場合を考えます。
最短距離は以下のパターンに限定されます。

(1) 未接続だった辺を経由しない
最短距離は、未接続だった辺を無視した1\rightarrow Nの最短距離となります。

(2) 未接続だった辺を経由する
1\rightarrow iとi\rightarrow Nの経路に分けて考えます。最短距離は2つの最短距離の合計です。

  • 1\rightarrow i

    • 1から直接iに行く
      最短距離は未接続の辺を無視した1\rightarrow iへの最短距離となります。

    • 未接続だった辺を持つ頂点sを経由してiに行く
      sは1から最も近い頂点を選びます。この時、1\rightarrow s\rightarrow iという移動となります。最短距離は未接続だった辺を無視した1\rightarrow sへの最短距離+1です。

  • i\rightarrow N

    • iから直接Nに行く
      最短距離は未接続だった辺を無視したi\rightarrow Nへの最短距離となります。

    • 未接続だった辺を持つ頂点tを経由してNに行く
      tはNから最も近い頂点を選びます。この時、i\rightarrow t\rightarrow Nという移動となります。最短距離は未接続だった辺を無視したt\rightarrow Nへの最短距離+1です。

以上より、各iに接続した時の1からNへの最短距離は、(1)又は(2)のパターンのいずれか小さい方となります。

s,t及び未接続の辺を無視した場合の最短距離は、未接続の辺を無視したダイクストラ法を1及びNのそれぞれを始点として1回ずつ行えば求めることが可能です。

1からNに行けない時は、最短距離が\inftyになるようにすれば求めることができます。詳細は実装参照。
なお、s,tが存在しない場合もあるので、注意が必要です(WAしました)。
Submission #32861308 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）