ACL Beginner Contest C,D,E,F問題メモ

ACL Beginner Contest

遅延セグ木理解したと思ったけど理解できてなかった

C - Connect Cities

問題

  • $N$ 個の都市と $M$ 本の道路があり、道路 $i$ は都市 $A_i$ と $B_i$ をつなぐ
  • あと最低何本の道路を追加すれば、全ての都市が連結になるか求めよ
  • $2 \le N \le 10^5$
  • $1 \le M \le 10^5$

解法

Union-Find。

既存の道路による接続を全てuniteしたあと、残っている根(リーダー)の個数を数える。

$K$ 個のリーダーが残っていたら、それを繋ぐために必要な道路の個数は $K-1$ 本。

Python3

D - Flat Subsequence

問題

  • 数列 $A_1,A_2,...,A_N$ と整数 $K$ が与えられる
  • 以下の条件を満たす数列 $B$ の長さとして考えられる最大値を求めよ
    • $B$ は $A$ の(連続とは限らない)部分列
    • $B$ のどの隣り合う2要素も、差の絶対値が $K$ 以下
  • $1 \le N \le 3 \times 10^5$
  • $0 \le A_i \le 3 \times 10^5$

解法

セグメント木を動的に使ってのDP。

以下のDPを定義する。

  • $DP[i][a]=A_i$ までで作れる条件を満たす部分列で、末尾要素が $a$ であるようなものの最大長さ

すると、$i+1$ について更新したければ、$DP[i][A_{i+1}-K]~DP[i][A_{i+1}+K]$ の範囲から最大の長さを持ってきて、そこに+1すればよい。

これは、区間MAXの取得と、一点更新を行えるデータ構造があればできる。セグメント木で実装する。

$DP[i+1]$ についての更新は $DP[i]$ の情報しか不要なので、破壊的に更新していってよい。

Python3

E - Replace Digits

問題

  • $N$ 個の '1' が繋がった文字列 $S$ がある
  • $Q$ 個のクエリを処理する
    • $i$ 番目のクエリでは、$S$ の $L_i~R_i$ 文字目(両端含む)を $D_i$ に置換する
  • 各クエリの後、$S$ を10進数の整数とみなした値を $\mod{998244353}$ で求めよ
  • $1 \le N,Q \le 2 \times 10^5$

解法

遅延伝播セグメント木。

$111111 = 100000+10000+1000+100+10+1$ と分けて、1桁ずつ管理する。

まず、セグメント木のそれぞれのノードが表す1単位を計算する。
たとえば6桁なら、こんな感じ。$S$ の初期状態でもある。

|                        111111                     |
|          111100           |          11           |
|   110000    |     1100    |     11    |      0    |
|100000| 10000|  1000|   100|   10|    1|   0 |   0 |

これを $U_i$ とすると、「ノード $i$ 以下全体が $D$ に書き換えられた」=「そのノード以下全体の合計は $U_i \times D$」となる。

そして、遅延伝播セグメント木には、

  • データとして、ノードの示す区間の総和
  • 遅延データとして、「そのノード以下が全て同じ数字に書き換えられるか、書き換えられるならその数字は何か」

というデータを乗っける。遅延データは当てはまらない場合は-1とかにしておけばいい。

そして、遅延セグ木に定義すべき演算は、以下のようになる。

  • op(データ同士の演算)
    • 普通の足し算
  • mapping(遅延データをデータに反映)
    • -1なら何もしない。それ以外なら $Data_i ← U_i \times Lazy_i$
  • composition(遅延データ同士の合成)
    • 上書きする値が-1以外なら上書き。そうでなければ何もしない

感想

適当に実装したところ上手く動かなかったので、いちから流れを確かめてバグ取りしてたら時間かかった。 どうも、「今ある値に加える」処理と「今ある値を書き換える」処理の区別が付いておらず、後者に対して実装の仕方が分かってなかった。 1)

書き換えるタイプの更新処理では上記のように、 「ノード以下が全て書き換えられるか」というフラグを持たせ、 Trueなら遅延データを参照して、Falseなら現在のデータを参照する、というのが肝要っぽい。

遅延データ側に載せるものには $mapping(a,e)=a$ を満たす単位元のような存在 $e$ が必要らしいが、これが「フラグがFalseであること」に相当するのか。なるほど。

Python3

F - Heights and Pairs

問題

  • $2N$ 人の人がいて、人 $i$ の身長は $h_i$ である
  • 以下の条件を満たしつつ、2人ずつ $N$ 個のペアを作りたい
    • どのペアも、2人の身長が異なる
  • $N$ 個のペアの作る方法としてあり得るものは何通りか、$\mod 998244353$ で求めよ
  • $1 \le N \le 50000$
  • $1 \le h_i \le 10^5$

解法

たたみ込みを使った包除原理。

まずこのような問題は、全てのペアを作るパターン数から、当てはまらないものを除くことができるか考える。

すると、同じ身長となってしまうペアの個数で包除原理を使えそう。

包除原理の適用

まず、$2K$ 人から $K$ 個のペアを作るパターン数というのは、1個飛ばしの階乗(二重階乗)で求められる。これを最初に計算しておく。

  • $Pair[3] = 5 \times 3 \times 1$
  • $Pair[5] = 9 \times 7 \times 5 \times 3 \times 1$

次に、同じ身長のペアが少なくとも $k$ 個できてしまうパターン数を、$k=0,1,2,...$ で求める。

  • $Pat[k]= $ 少なくとも $k$ 個、同じ身長ペアができるペアの作り方

たとえば「身長10の人が7人」「身長20の人が10人」他の身長は1人ずついたとして、以下を計算していく。

  • 全てのペアの作り方(少なくとも0個、同じ身長ペアができる)
    • $Pat[0]=Pair[N]$
  • 少なくとも1個、同じ身長ペアができる
    • 身長10から1組の場合: $Q_1={}_{7}C_{2} \times Pair[1]$
    • 身長20から1組の場合: $Q_2={}_{10}C_{2} \times Pair[1]$
    • それ以外のペアの選び方: $Pair[N-1]$
    • $Pat[1]=(Q_1+Q_2) \times Pair[N-1]$
  • 少なくとも2個、同じ身長ペアができる
    • 身長10から2組: $Q_1={}_{7}C_{4} \times Pair[2]$
    • 身長10から1組、身長20から1組: $Q_2={}_{7}C_{2} \times Pair[1] \times {}_{10}C_{2} \times Pair[1]$
    • 身長20から2組の場合: $Q_3={}_{10}C_{4} \times Pair[2]$
    • それ以外のペアの選び方: $Pair[N-2]$
    • $Pat[2]=(Q_1+Q_2+Q_3) \times Pair[N-2]$

すると、答えは $Pat[0]-Pat[1]+Pat[2]-Pat[3]+...$ で求められる。

問題は、$Pat$ をどう求めるか。ここにたたみ込みを用いる。

たたみ込み

同じ身長の人が $n$ 人いたとして(これを $n$ 人グループと称する)、この中だけで、同じ身長のペアを $k$ 組作るパターン数を考える。

これは、$n$ 人の中からどの人をペアにするかで ${}_{n}C_{2k}$、その $2k$ 人をどう組み合わせるかで $Pair[k]=(2k-1)!!$、これを掛け合わせたものとなる。

たとえば7人なら、以下のようになる。

7人グループからk個のペアを作る方法
k  0   1   2   3
   1  21 105 105

次に、グループが2つあったとして、その中から同じ身長のペアを合計 $k$ 組作るパターン数を考える。

たとえば7人グループと10人グループがあったとして、

10人グループからk個のペアを作る方法
k  0   1   2    3    4   5
   1  45 630 3150 4725 945

「2つのグループのどちらかから、同じ身長のペアを合計 $k$ 組作るパターン数」は、たとえば $k=4$ なら以下のようになる。

 7人から  10人から
のペア数  のペア数
       0         4       1 x  4725 =   4725
       1         3      21 x  3150 =  66150
       2         2     105 x   630 =  66150
       3         1     105 x    45 =   4725
                     -----------------------
                                     141750 

この操作は、まさにたたみ込みである。
たたみ込んだ結果は以下のようになる。

k  0   1    2     3      4  ...     8
   1  66 1680 21210 141750  ... 99225

MODを取りながらのたたみ込みは、AtCoder-Libraryのconvolutionを使うと2つの配列長の和を $N$ として $O(N \log{N})$ で求めることができる。

同じ身長のグループが3個以上でも、このようなマージを順番に適用していくことで求められる。

ただし、マージにかかる計算量は、前述の通り配列の合計の長さに比例する。
適当に順番を決めてしまうと、何度も長い配列をマージすることになってしまい、TLE。

サイズの短い方から順番に行っていくと、全体で $O(N (\log{N})^2)$ になる。

「マージは小さい方から」。よく忘れて、見当違いの高速化に走りがち。

感想

マージする順番以外は(コンテスト終了後に)自力でたどり着けたが、 正直、たたみ込みに気付いたのはAtCoder-Library Contestだからというのが大きい気がする。

Python3

1)
まぁ、より抽象化すれば両者は同じことなんだろうけど
programming_algorithm/contest_history/atcoder/2020/0926_abl.txt · 最終更新: 2020/09/30 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0