Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 334 F問題 Christmas Present 2

問題

atcoder.jp

提出解答

atcoder.jp

解法

座標平面上の点  S, P_i~(i=1,2, \dots, N) S = (S_X, S_Y), P_i = (X_i, Y_i) とする.

動的計画法で解く.  i = 1, 2, \dots, N+1 に対して,  {\rm DP}(i) で, 問題を  P_i, P_{i+1}, \dots, P_N へ制限したときの距離の総和の最小値とする. このとき, 最終解答は  {\rm DP}(1) になる.

ベースケースは  i = N + 1 のときで, このとき, 経由すべき点がないことから, 移動が発生しないので,  {\rm DP}(N + 1) = 0 である.

遷移式を考える.  i のときに, 連続して配るプレゼントの個数  k で場合分けをする. 連続して  k 個配る場合における距離の総和を最小化する移動の方法は, 以下の手順をたどることになる.

  •  S から 点  P_i へ移動.
  •  j = 1,2, \dots, k - 1 に対して, 点  P_{i+j-1} から  P_{i+j} へ移動.
  •  P_{i + k - 1} から点  S へ移動.
  • それ以降は  {\rm DP}(i + k) を達成するように移動する.

よって, この場合における距離の総和の最小値は

 \displaystyle \operatorname{dist}(S, P_i) + \sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j}) + \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + K)

となる.

これを  k について動かすことによって,  {\rm DP}(i) の値は

 \displaystyle \begin{align*} {\rm DP}(i)
&= \displaystyle \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left( \operatorname{dist}(S, P_i) + \sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j}) + \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + k) \right) \\
&= \displaystyle  \operatorname{dist}(S, P_i) + \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left(\sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j}) + \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + k) \right) 
\end{align*}\

となる.

ここで,  T(i + k) := \operatorname{dist}(P_{i + k - 1}, S) + {\rm DP}(i + k) とおくことにすると,

 \displaystyle {\rm DP}(i) = \operatorname{dist}(S, P_i) + \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left(\sum_{j = 1}^{k - 1} \operatorname{dist}(P_{i + j - 1}, P_{i + j})+ T(i + k) \right)

となる.

また,  1 \leq l \leq r \leq N に対して,

 \displaystyle U_{l,r} := \sum_{t = l + 1}^r \operatorname{dist}(P_{t - 1}, P_t)

とおくことにすると,

 \displaystyle {\rm DP}(i) = \operatorname{dist}(S, P_i) + \min_{\substack{1 \leq k \leq K \\ i + k \leq N + 1}} \left( U_{i, i + k} + T(i + k) \right)

となる.

ここで,  U_{i, i + k} + T(i + k)~(1 \leq k \leq K) について,

 U_{i, i + k} + T(i + k) =  \operatorname{dist}(P_i, P_{i + 1}) + U(i +1, i + k) + T(i + k)

が成り立つ.

 \operatorname{dist}(P_i, P_{i + 1}) k によらない一定の値である.

したがって, 次のことが高速にできるデータ構造があれば高速に  {\rm DP}(i) を計算できる.

  • 区間における最小値を取得する.
  • ある区間に一定値を加算する.

これを可能にするデータ構造としては遅延評価セグメント木がある.

よって,  U(i, i + k) + T(i + k) を遅延評価セグメント木によって適切に区間作用を行い  {\rm DP}(i) を計算することによって,  {\rm DP}(1) O(N \log N) 時間で求めることができる.

AtCoder Beginner Contest 314 F問題 A Certain Game

問題

atcoder.jp

提出解答

atcoder.jp

解法

「データ構造をマージする一般的なテク」を利用して, この問題を解く.

  • 以下のものを用意する.
    •  1,2, \dots, N を頂点に持つ Union-Find  U.
    •  x=1,2, \dots, N に対して,  \Gamma_x \gets 0, \delta \gets 0 とする.
      •  \Gamma_x は頂点  x を代表元に持つ連結成分におけるベースとなる期待値を記録する.
      •  \delta_x x が属する連結成分の代表元を  y としたときの  \Gamma_y と, その時点での勝利回数の期待値との差を記録する.
    •  i=1,2,\dots, N に対して,  V_i i の一要素のみからなるリストとする.
  •  i=1,2, \dots, N-1 の順に以下を行う.
    •  U において,  p_i が属する連結成分の頂点数が,  q に属する連結成分の頂点数より大きいならば,  p,q を入れ替える.
    •  p_i, q_i U における  p_i の代表元,  q_i における代表元に置き換える.
    •  U において,  p_i, q_i が属する連結成分の頂点数をそれぞれ  a,b とする.
    •  V_p の各頂点  y について,  \delta_y \displaystyle \Gamma_{p_i} - \Gamma_{q_i} - \frac{b-a}{a+b} を加算する.
    •  \Gamma_{q_i} \dfrac{b}{a+b} を加算する.
    •  V_{q_i} V_{p_i} の全ての要素を付け加える.
    •  U において,  p_i, q_i を併合する.

最後に残る唯一の連結成分の代表現を  z としたとき,  i=1,2, \dots, N のそれぞれに対する正解は,  \Gamma_z+\delta_i である.

AtCoder Beginner Contest 304 C問題 Subscribers

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

座標平面上に  N 人の人がいる. 人  i は座標  (X_i, Y_i) にいる.

ウイルス V は感染した人から (Euclid) 距離で  D 以下にいる人全てに感染させる能力を持っている.

ある時, 人  1 がウイルス V に感染した. そして, 十分長い時間が経過した時, 各人はウイルス V に感染しているか?

制約

  •  1 \leq N \leq 2000
  •  1 \leq D \leq 2000
  •  -1000 \leq X_i, Y_i \leq 1000
  •  i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)

解法

実際に, 人 1 から距離が  D 以下の人に対して, ウイルス V を感染させていくシミュレーションを行えば良い. ただし, 一度感染したひとに関する調査はスキップしなければならない.

ちなみに, これはあるグラフ上の BFS となる, 実際, 次のような無向グラフ  G=(V,E) における頂点  1 が属する連結成分を調べていることと同等である.

  •  V:=\{1,2, \dots, N\}
  •  E:=\{ij \mid (X_i-X_j)^2+(Y_i-Y_j)^2 \leq D^2 \}

 G E の辺の構成について, 全ての組み合わせについて見る必要があるので,  O(N^2) 時間かかり, 最大で  \dfrac{N(N+1)}{2} 本となる.

よって, 計算量は BFS によって,  O(N^2) 時間となる.

AtCoder Beginner Contest 304 B問題 Subscribers

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

 N の値に応じて, 以下の処理をせよ.

  •  N \leq 10^3-1 ならば,  N を出力せよ.
  •  10^3 \leq N \leq 10^4-1 ならば,  N の一の位を切り捨てた整数を出力せよ.
  •  10^4 \leq N \leq 10^5-1 ならば,  N の十の位以下を切り捨てた整数を出力せよ.
  •  10^5 \leq N \leq 10^6-1 ならば,  N の百の位以下を切り捨てた整数を出力せよ.
  •  10^6 \leq N \leq 10^7-1 ならば,  N の千の位以下を切り捨てた整数を出力せよ.
  •  10^7 \leq N \leq 10^8-1 ならば,  N の万の位以下を切り捨てた整数を出力せよ.
  •  10^8 \leq N \leq 10^9-1 ならば,  N の十万の位以下を切り捨てた整数を出力せよ.

制約

  •  0 \leq N \leq 10^9-1

解法

上の場合分けをそのまま実装してもよいが,  N \geq 1000 のときは命令をよく見ていみると, 上3桁以外を切り捨てろという処理であるから, 次のようにして出力すべき整数を求めることができる.

  •  N の桁数を  d とする. 出力すべき整数は  N の上3桁に  10^{d-3} を掛けた整数である.

 N の上3桁については,  N を文字列とすると簡単に取得できる.

また,  N \leq 10^3-1 のときはそのまま  N を出力することに注意.

AtCoder Beginner Contest 304 A問題 First Player

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

 N 人が時計回りに座っている.  i 番目の人の名前は  S_i で, 年齢は  A_i である.

 N 人は  1,2, \dots, N の順に並んでいる.

なお,  N 人の名前は全員異なり, 年齢も全員異なる.

年齢が最も小さい人から順に時計回りで  N 人出力せよ.

制約

  •  2 \leq N \leq 100
  •  S_i は英小文字からなる長さ  1 以上  10 以下の文字列.
  •  S_1, \dots, S_N は全て異なる.
  •  0 \leq A_i \leq 10^9
  •  A_1, \dots, A_N は全て異なる.

解法

次のようにすればよい.

  •  \alpha:=\min A を求める.
  •  A_j=\alpha を満たす  j を求める.
  • 以下を  N 回繰り返す.
    •  S_j を出力する.
    •  j 1 を加算する. その後,  j=N+1 ならば,  j \gets 1 とする.

AtCoder Regular Contest 161 B問題 Exactly Three Bits

問題

atcoder.jp

提出解答

(※ C++ での提出) atcoder.jp

問題の概要

 N 以下の正の整数  X で以下を満たすものは存在するか? 存在するならばそのような整数のうちの最大値を求めよ.

  •  X 2 進法表記したときに現れる  1 の個数がちょうど  3 である.

 T 個のマルチテストケース

制約

  •  1 \leq T \leq 10^5
  •  1 \leq N \leq 10^{18}

解法

条件を満たす  X のうち, 最小の正の整数は  X=7 なので,  N \lt 7 の範囲では存在しないとなる.

以降では  N \geq 7 とする.

 g(N,k) N 以下の非負整数で,  2 進法表記したときに現れる  1 の個数がちょうど  k であるような非負整数のうち, 最大であるようなものと定義する (存在しない場合は  -\infty).

このとき, 次のようにして場合分けすることによって, 帰納的に導くことができる.

  •  N=0 の場合,  0 以下の正の整数は存在しないので,  g(0,k)=-\infty である.
  •  k=1 の場合,  a 2^a \leq N \lt 2^{a+1} 以下を満たす整数として,  g(N,1)=2^a である.
  •  N が奇数のとき,  1 の位をどうするかで場合分けすることにより,  g(N,k)=\max(2g(\frac{N-1}{2}, k-1)+1, 2(\frac{N-1}{2}, k)) となる.
  •  N が偶数のとき,  1 の位をどうするかで場合分けすることにより,  g(N,k)=\max(2g(\frac{N}{2}-1, k-1)+1, 2(\frac{N}{2}, k)) となる.

これにより, 求めるべきは  g(N,3) である. また,  g(N,k) に出てくる引数の候補は  O(\log N) 個であるので,  g(N,3) O((\log N)^2) 時間で求めることができる.

これは   T 個のテストケースの下では, 高速な言語を使用することによって, 正解することができる.

AtCoder Regular Contest 161 A問題 A Make M

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さが奇数である整数列  S=(S\1, \dots, S_M) に対して, 以下を満たすとき,  S は M 型であるという.

  •  S_1 \lt S_2 \gt S_3 \lt S_4 \gt \dots \gt S_{N-3} \lt S_{N-2} \gt S_{N-1}

 N を奇数とする. 長さ  N の整数列  A=(A_1, \dots, A_N) が与えられる.  A を適切に並び替えることによって, M 型にすることは可能か?

制約

  •  1 \leq N \leq 2 \times 10^5
  •  N は奇数である.
  •  1 \leq A_i \leq 10^9

解法

以下は同値である.

  •  A を適切に並び替えると, M 型にすることができる.
  •  A を昇順に並び替えた列を  B=(B_1, \dots, B_N) とし,  K=\dfrac{N+1}{2} とすると,
     B_1 \lt B_{K+1} \gt B_2 \lt B_{K+2} \gt \dots \gt B_{K+K-2} \lt B_{K+1} \gt B_{K+K-1}
    が成り立つ.

(下) ならば (上) は明らかなので, (上) ならば (下) を証明する.

 A を並び替えることによって,  A は M 型であるとする. このとき,  A の奇数項目の最小値を  X とする.

このとき,  A の奇数項目に  X より大きい整数が,  A の偶数項目に  X より小さい整数が存在する場合, これら  2 項は交換しても M 型を保ったままである.

このようにすることで,  A の奇数項目は全て  X 以下, 偶数項目が全て  X 以上にすることができる.

また, このときの  A に含まれる  X については以下のうちのどちらかが成り立つ.

  •  A の奇数項目が全て  X で,  A の偶数項目は全て  X より大きい.
  •  A の奇数項目にある  X の数と  A の偶数項目にある  X の数 (要するに  A にある  X の数) が  (N-K) 個以下.

どちらの場合にしても, 奇数項目, 偶数項目それぞれ昇順に並び替えることによって,  A は (下) での操作の結果による並び替えになり, M 型にもなる.