そのうち誰かの役に立つ

もしくは誰の役にも立たない

AtCoderチャレンジ供養会場(2020/07/01-2020/07/31)

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

7/5: AtCoder Beginner Contest 173 F - Intervals on Tree

供養

問題

Difficulty: 1806 (記事作成時点)

解法

  • 連結成分の数  = 頂点数  - 辺の数となる
  • 頂点と辺をそれぞれ独立に、自分が含まれる  (L, R) の数を数えて和を取る

実装は

  1.  S = 0 とする
  2.  1 \le u \le N について、 S = S + u \times (N + 1 - u) とする
  3.  1 \le i \lt N について、以下の計算を実施する
    •  u_{i} \gt v_{i} なら  u_{i} v_{i} を入れ換える
    •  S = S - u_{i} \times (N + 1 - v_{i}) とする
  4.  S を出力する

計算量は  O(N)

公式解説

躓いた点

  • 時間内に思いつかなかった

7/11: エイシング プログラミング コンテスト 2020 E - Camel Train

供養

問題

Difficulty: 2123 (記事作成時点)

解法

  •  L_{i} \ge R_{i} ならば、 j \le K_{i} 番目になるように配置した方がよく、そうでないならば  j \gt K_{i} 番目となる方がよい
  •  L_{i} \ge R_{i} であるラクダについて、 L_{i} - R_{i} の降順に並びを決めていく
    •  L_{i} \ge R_{i} ならば、まだ決まっていない  j \le K_{i} のうち最後尾の  j 番目に仮で並ばせる
      • そのように並ばせられるラクダの集合を  C_{L, 0} とする
    •  K_{i} 番目まで全て埋まっていたラクダの集合を  C_{L, 1} とする
  •  L_{i} \lt R_{i} であるラクダについて、 R_{i} - L_{i} の降順に並びを決めていく
    •  L_{i} \gt R_{i} ならば、まだ決まっていない  j \gt K_{i} のうち最前の  j 番目に仮で並ばせる
      • そのように並ばせられるラクダの集合を  C_{R, 0} とする
    •  K_{i} 番目以降が全て埋まっていたラクダの集合を  C_{R, 1} とする
  •  C_{L, 0}, C_{L, 1}, C_{R, 1}, C_{R, 0} の順に並ばせる
    •  C_{L, 0}, C_{R, 0} は仮の順番通りとする

実装は

  1.  (K_{i}, L_{i}, R_{i}) |L_{i} - R_{i}| について降順にソートする
  2.  N + 2 要素のSegment Tree  S, T を用意し、 0 \le i \le N + 1 について  S_{i} = i, T_{i} = i とする
    •  F(n) S_{0}, \dots, S_{n} の最大値を返すとする
    •  G(n) T_{n}, \dots, T_{N + 1} の最小値を返すとする
  3.  A = 0 とする
  4.  0 \le i \lt N について、以下の操作を実施する
    •  L_{i} \ge R_{i} ならば、以下の操作を実施する
      •  p = F(K_{i}) とする
      •  p \ge 1 ならば  S_{p} = 0, A = A + L_{i} とする
      •  p \lt 1 ならば  A = A + R_{i} とする
    •  L_{i} \lt R_{i} ならば、以下の操作を実施する
      •  p = G(K_{i} + 1) とする
      •  p \gt N ならば  A = A + L_{i} とする
      •  p \le N ならば  T_{p} = N + 1, A = A + R_{i} とする
  5.  A を出力する

計算量は1ケースあたり  O(N\mathrm{log}N)

公式解説

躓いた点

  • 時間切れ

7/25: M-SOLUTIONS プロコンオープン 2020 F - Air Safety

供養

問題

Difficulty: 2004 (記事作成時点)

解法

  • 衝突しうる6パターンについて最初に衝突するまでの時間の最小値を求める
    •  X が等しい UD
    •  Y が等しい RL
    •  X - Y が等しい UL、もしくは RD
    •  X + Y が等しい UR、もしくは DL
  • 基準値ごとにバケツを作り、さらにその中でも座標でソートして比較を高速にする

実装は

  1.  4 \times 4 times 400001 の配列  P を用意する
  2.  0 \leq i \le N について、以下の処理を実施する
    •  U_{i} = U のとき、以下の処理を実施する
      •  P_{0, 0, X_{i}} Y_{i} を追加する
      •  P_{2, 0, X_{i} - Y_{i} + 200000} X_{i} を追加する
      •  P_{3, 0, X_{i} + Y_{i}} X_{i} を追加する
    •  U_{i} = R のとき、以下の処理を実施する
      •  P_{1, 1, Y_{i}} X_{i} を追加する
      •  P_{2, 1, X_{i} - Y_{i} + 200000} X_{i} を追加する
      •  P_{3, 1, X_{i} + Y_{i}} X_{i} を追加する
    •  U_{i} = D のとき、以下の処理を実施する
      •  P_{0, 2, X_{i}} Y_{i} を追加する
      •  P_{2, 2, X_{i} - Y_{i} + 200000} X_{i} を追加する
      •  P_{3, 2, X_{i} + Y_{i}} X_{i} を追加する
    •  U_{i} = L のとき、以下の処理を実施する
      •  P_{0, 3, Y_{i}} X_{i} を追加する
      •  P_{2, 3, X_{i} - Y_{i} + 200000} X_{i} を追加する
      •  P_{3, 3, X_{i} + Y_{i}} X_{i} を追加する
  3.  P_{i, j, k} を昇順にソートする
  4. 配列  A, B、整数  x から整数を返す関数  F(A, B, x) を以下のように定義する
    •  X = 2000001, i = 0, j = 0 とする
    •  i \le |A| \; \mathrm{AND}\; j \le |B| である間、以下の処理を実施する
      •  A_{i} \le B_{j} ならば以下の処理を実施する
        •  X = \mathrm{min}( (B_{j} - A_{i}) \times x, X) とする
        •  i をインクリメントする
      •  A_{i} \ge B_{j} ならば  j をインクリメントする
    •  X を返す
  5.  X = 2000001 とする
  6.  0 \le k \le 400000 について、以下の処理を実施する
    •  X = \mathrm{min}(F(P_{0, 0, k}, P_{0, 2, k}, 5), X) とする
    •  X = \mathrm{min}(F(P_{1, 1, k}, P_{1, 3, k}, 5), X) とする
    •  X = \mathrm{min}(F(P_{2, 0, k}, P_{2, 3, k}, 10), X) とする
    •  X = \mathrm{min}(F(P_{2, 1, k}, P_{2, 2, k}, 10), X) とする
    •  X = \mathrm{min}(F(P_{3, 1, k}, P_{3, 0, k}, 10), X) とする
    •  X = \mathrm{min}(F(P_{3, 2, k}, P_{3, 3, k}, 10), X) とする
  7.  X \ge 2000000 ならば SAFE を出力し、そうでなければ  X を出力する

計算量は  O(N\mathrm{log}N)

公式解説

躓いた点

  • 場合分けの実装が間に合わなかった

7/31: M-SOLUTIONS プロコンオープン 2020 E - M's Solution

供養

問題

Difficulty: 2306 (記事作成時点)

解法

  • 前計算として、南北方向のみもしくは東西方向のみにしか線路が通っていない場合を考える
  • 数直線上で  N 個の値  A_{i} に対して  K 個の値  B_{j} \sum_{i}\mathrm{min}(|A_{i} - B_{j}|) が最小となるよう決めたとき、各  B_{j} A_{j} のいずれかと一致するような選び方が存在する
  • 各集落について線路が通っている場合と線路が通っていない場合の  2^{N} 通りについて、そのときの最小移動距離の合計を求めておく
  • 各集落について、南北方向に線路が通っている、東西方向に線路が通っている、線路が通っていない、の  3^{N} パターンを考える
    • 南北方向、東西方向の両方に線路が通っていることは(結果的にそうなることがあったとしても)考えなくてもよい
    • 南北方向に線路が通っている集落の集合が  V、東西方向に線路が通っている集落の集合が  H であるとする
    • 線路が通っていない各集落について、南北方向にしか線路が通っていない場合で線路が通っている集落の集合が  V である場合の移動距離と、東西方向にしか線路が通っていない場合で線路が通っている集落の集合が  H である場合の移動距離の最小値を合計したものがそのパターンにおける移動距離合計の最小値である
    • 各パターンについて線路を引いた本数を  k としたとき、各  k について最小値を求めればよい

実装は

  1.  L = 0 とし、 0 \le i \lt N について、 L = L + \mathrm{min}(|X_{i}|, |Y_{i}|) \times P_{i} とする
  2.  2^{N} \times N の配列  V, H を用意する
  3.  0 \le p \lt 2^{N} について、以下の処理を実施する
    •  0 \le i \lt N について、 V_{p, i} = |X_{i}|, H_{p, i} = |Y_{i}| とする
    •  0 \le j \lt N について、以下の操作を実施する
      •  p \; \mathrm{AND}\; 2^{j} \gt 0 ならば、 0 \le i \lt N について、 V_{p, i} = \mathrm{min}(|X_{i} - X_{j}|, V_{p, i}), H_{p, i} = \mathrm{min}(|Y_{i} - Y_{j}|, H_{p, i}) とする
  4.  N + 1 個の配列  A を用意し、 A_{i} = L とする
  5.  0 \le p \lt 3^{N} について、以下の操作を実施する
    •  v = 0, h = 0, c = 0, q = p とする
    •  0 \le i \lt N について、以下の処理を実施する
      •  q \% 3 = 0 のとき、 c = c + 1 とする
      •  q \% 3 = 1 のとき、 v = v + 2^{i} とする
      •  q \% 3 = 2 のとき、 h = h + 2^{i} とする
      •  q = \lfloor \frac{q}{3} \rfloor とする
    •  a = 0, q = p とする
    •  0 \le i \lt N について、以下の処理を実施する
      •  q \% 3 = 0 のとき、 a = a + \mathrm{min}(V_{v, i}, H_{h, i}) \times P_{i} とする
      •  q = \lfloor \frac{q}{3} \rfloor とする
    •  A_{c} = \mathrm{min}(a, A_{c}) とする
  6.  0 \le i \le N について、 A_{i} を出力していく

計算量は  O(N3^{N})

公式解説

躓いた点

  • 3通りに場合分けするところを思いつかなかった