そのうち誰かの役に立つ

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

AtCoderチャレンジ供養会場(2020/06/08-2020/06/14)

競技プログラミング AtCoder 半分全列挙

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

6/8: AtCoder Grand Contest 045 A. Xor Battle

供養

問題

Difficulty: 1776 (記事作成時点)

解法

  • S を後ろから見ていって、 S_{i} = 1 のとき、それまでに見た j \gt i \land S_{j} = 0 であるような A_{j} を任意に組み合わせたときに A_{i} が作れればよい
    • 掃き出し法を使って求めることができる
    • 正方行列ではないので一般化が必要

実装は

  1. N \times 60 の配列 B を用意し、 B_{i, j} を A_{i} の下から j bit目とする
  2. 以下の関数 F(X, A) を用意する
    • n = |X_{0}| とする
    • i = 0, j = 0 とし、 i \ge 60 もしくは j \ge n となるまで以下の処理を実施する
      • p = i とし、 X_{p, j} = 1 もしくは p = 60 となるまで p をインクリメントする
      • p = 60 ならば j をインクリメントして次のループに行く
      • i \ne p ならば X_{i} と X_{p} を入れ換える
      • 0 \le k \lt 60 について、以下の処理を実施する
        • k - i もしくは X_{k, j} = 0 ならばなにもせず次のループに行く
        • 0 \le l \lt n について、 X_{k, l} = X_{k, l} \oplus X_{i, l} とする
        • A_{k} = A_{k} \oplus A_{i} とする
      • i, j をインクリメントする
    • j = 0 とし、 0 \le i \lt 60 について、以下の処理を実施する
      • j \lt n かつ X_{i, j} = 0 である間、 j をインクリメントする
      • j = n かつ A_{i} = 1 ならば \mathit{false} を返す
      • j をインクリメントする
    • \mathit{true} を返す
  3. 60 個の配列 X を用意する
  4. a = 0 とする
  5. i = N - 1, \dots, 0 について以下の処理を実施する
    • S_{i} = 0 のとき、 0 \le j \lt 60 について、 X_{j} の末尾に B_{i, j} を追加する
    • S_{i} = 1 のとき、 F(X, B_{i}) = \mathit{false} ならば a = 1 とする
  6. a を出力する

計算量は O(TN(\mathrm{log}A)^{2})

公式解説

躓いた点

  • 掃き出し法で求められることに気付かなかった
  • 掃き出し法の実装でバグ多数

6/10: AtCoder Regular Contest 087 E - Prefix-free Game

供養

問題

Difficulty: 2448 (記事作成時点)

解法

  • このゲームを、高さ L + 1 の完全二分木上の点に、それまで置いた駒と先祖子孫の関係にならないよう交互に駒を置いていくゲームと考える
    • ゲーム開始時点でいくつかの高さ h の部分木に分割されている
  • 高さ h の部分木について、高さ h^{'} \le h の点に駒を置くと、高さ h - 1, h -2, \dots, h^{'} の部分木に分割される
    • 高さ h の点 i.e. 部分木の根に置くと部分木が消える
  • 高さ h の部分木のGrundy数 g_{h} は 0, g_{h - 1}, \dots, g_{h - 1} \oplus \dots \oplus g_{1} を除く最小の非負整数である
  • 上記から g_{h} は h の rightmost set bit だけを1にした数である
    • e.g. g_{5} = 1, g_{8} = 8
  • 初期状態はTrie Treeを作った時に子がちょうど1つであるノードを見ていけばよい

実装は

  1. s_{i} からTrie Tree T を作る
    • 各ノードは根からの深さ d を持っているとする
  2. g = 0 とする
  3. T の各ノードを見ていき、子がちょうど1つのノード T_{j} があったときに g = g \oplus ( (L - d_{j})\; \mathrm{AND}\; (d_{j} - L) ) とする
  4. g \gt 0 ならば Alice、 g = 0 ならば Bob を出力する

計算量は \sum s_{i} = S として O(S)

公式解説

躓いた点

  • Grundy数の決め方を間違えた

6/12: AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行

供養

問題

Difficulty: 2451 (記事作成時点)

解法

  • 駅と会社をペアにして考え、 (p_{i}, c_{i}) に対応する点と (q_{i}, c_{i}) に対応する点について双方向に距離 0 の辺を張る
  • 路線乗り換えを表現するために、各駅 v にどの会社とも異なる (v, 0) に対応する点を用意し、 (v, c \ne 0) \to (v, 0) で距離 0 の辺を、 (v, 0) \to (v, c) で距離 1 の辺を張る
  • 路線乗り換えが発生しない状態を表現するために、 (v, c) がユニークになるよう工夫するか、各点について会社ごとに路線番号を覚えておき、同じ駅同じ会社を使う路線 i, j について対応する点が距離 0 で接続されるように辺を張る
    • メッシュである必要はない
  • 上記の場合 N + 2M 頂点 O(M) 辺のグラフができるので、 (1, 0) から (N, 0) までの最短距離を求めればよい

実装は

  1. N + 2M 個の点集合 V からなるグラフ G を用意する
  2. N 個の連想配列 S を用意する
    • S_{i, j} には配列がリンクされる
  3. 0 \le i \lt M について以下の処理を実施する
    • S_{p_{i}, c_{i}} に i を追加する
    • S_{q_{i}, c_{i}} に i を追加する
    • V_{p_{i}} \to V_{N + 2i} で距離 1 の辺を張る
    • V_{N + 2i} \to V_{p_{i}} で距離 0 の辺を張る
    • V_{N + 2i} \to V_{N + 2i + 1} で距離 0 の辺を張る
    • V_{N + 2i + 1} \to V_{N + 2i} で距離 0 の辺を張る
    • V_{N + 2i + 1} \to V_{q_{i}} で距離 0 の辺を張る
    • V_{q_{i}} \to V_{N + 2i + 1} で距離 1 の辺を張る
  4. 0 \le i \lt N について、以下の処理を実施する
    • S_{i} の各key k について、以下の処理を実施する
      • S_{i, k} の長さが 1 以下ならば何もしない
      • 0 \le j \lt |S_{i, k}| - 1 について、以下の処理を実施する
        • V_{N + 2S_{i, k, j}} \to V_{N + 2S_{i, k, j + 1}} で距離 0 の辺を張る
        • V_{N + 2S_{i, k, j + 1}} \to V_{N + 2S_{i, k, j}} で距離 0 の辺を張る
  5. 配列 D を用意し、 G について V_{0} から各点 u への最短距離を D_{u} とする
  6. V_{N - 1} が到達可能なら D_{N - 1}、到達不可能なら -1 を出力する

計算量は O(N + M)

公式解説

躓いた点

  • 駅と会社をペアにして識別する発想が無かった

6/14: 東京海上日動　プログラミングコンテスト2020 D - Knapsack Queries on a tree

供養

問題

Difficulty: 2123 (記事作成時点)

解法

  • 半分全列挙する
  • 木の高さを H としたときに、深さ h^{'} = \lfloor \frac{H}{2} \rfloor までの点 v について、重さの合計 0 \le L \le 10^{5} 以下での最大価値を D_{v, L} として計算しておく
  • v_{i} の深さ h_{v_{i}} が h^{'} 以下ならば D_{v_{i}, L_{i}} をそのまま出力する
  • h_{v_{i}} \gt h^{'} のときは、 v_{i} を含む v_{i} の祖先 h_{v_{i}} - h^{'} 個の全ての組合せについて重さと価値の合計 w, v を計算し、 w \le L_{i} である組合せについて v + D_{v^{'}, L_{i} - w} の最大値を出力する
    • v^{'} は v_{i} の深さ h^{'} の祖先

実装は

  1. U = \mathrm{min}(N + 1, 2^{9}), L = 100001 とする
  2. U \times L の配列 D を用意する
  3. 1 \le v \lt U, 0 \le l \lt L について以下の処理を実施する
    • l \lt W_{v} ならば D_{v, l} = D_{\lfloor \frac{v}{2} \rfloor, l} とする
    • l \ge W_{v} ならば D_{v, l} = \mathrm{max}(D_{\lfloor \frac{v}{2} \rfloor, l - W_{v}} + V_{v}, D_{\lfloor \frac{v}{2} \rfloor, l}) とする
  4. 以下の関数 F(v, l) を用意する
    • v \lt U ならば D_{v, l} を返す
    • a = F(\lfloor \frac{v}{2} \rfloor, l) とする
    • l \ge W_{v} ならば a = \mathrm{max}(F(\lfloor \frac{v}{2} \rfloor, l - W_{v}) + V_{v}, a) とする
    • a を返す
  5. 0 \le j \lt Q について F(v_{j}, L_{j}) を出力していく

計算量は L = \mathrm{max}(L_{i}) として O(N + 2^{\lfloor \frac{H}{2} \rfloor}(Q + L))

公式解説

躓いた点

  • 半分全列挙を思いつかなかった
  • 実装が悪くTLE連発