AtCoder Beginner Contest 236 D,E,G,Ex問題メモ

AtCoder Beginner Contest 236

ちゅこだい、響きがちゅこ

D - Dance

• $2N$ 人の人がいて、$N$ ペア作る
• 人 $i$ と $j$（$i \lt j$）がペアになるとスコア $A_{i,j}$
• $N$ 個のペアのスコアの総XORを最大化せよ
• $1 \le N \le 8$

全探索。上手く実装しましょうという問題。

普通にやると $16!$ とかかかるところ、 「次に決めるペアのうち1人は必ず残っている中で番号最小の人」とすることで、 重複を除けて $15 \times 13 \times ... \times 1 \simeq 2 \times 10^6$ 程度に収まる。

で、それをどうやって実装するか。

たとえばグローバルに used = [0,0,0,0,…] のような長さ $2N$ の配列を持っておく。
人 $i$ をペアに使うと仮定したら used[i]=1 にする。

再帰関数が呼ばれたら、現在のusedから未使用のペアを1つ仮定して（usedを変更して）次の再帰に渡す。

再帰から帰ってきて次のペアの再帰を呼ぶとき、関数を抜けるとき、きちんと仮定した状態を元に戻す。

Python3

よくあるbitDPのような手法も使える。

• $DP[S]=$ bit集合 $S$ の人を使ったときにあり得る暫定スコアの集合

$S$ の小さい方から計算していける。
立っているbitが奇数の場合は飛ばすなどする。

立っている中で一番小さいbit $i$ と、もう1つ立っているbit $j$ をペアにするとして、

• $DP[S] \xleftarrow{add} DP[Sからi,jを除いた集合] の各暫定スコアと A_{i,j} とのXOR$

今回、求めるべきスコアがXORのため、 途中ではどの暫定スコアが結果的に最大を実現できるかわからなくて、全部持っておく必要がある。

そのため、結果的には再帰より遅くなる。まぁそれでも十分間に合う範囲なので、bitDPの書き方に慣れていれば。

• 解説 - AtCoder Beginner Contest 236

重複のないペアの作り方は、特定の条件を満たす順列と1対1対応できる。

条件を満たす順列に限定した中で次に大きいものを求めるのは、償却 $O(1)$ で行える。

E - Average and Median

• 長さ $N$ の数列 $A_1,A_2,...,A_N$ から（連続とは限らない）部分列を取り出す
• 取り出し方
  • $A_i$ と $A_{i+1}$ の少なくとも一方は取り出されなければならない
• 全ての部分列の中で、以下の値をそれぞれ求めよ
  • 平均値の最大値
  • 中央値の最大値（部分列の長さが偶数の場合は中央2つの小さい方）
• $1 \le N \le 10^5$

上手く言い換えての二分探索。

DPで直接求めようとするなら、たとえば以下のようにして平均値の最大値が求められるが、$O(N^2)$ かかる。

• （TLE）$DP[i][j]=i$ 番目までのうち $j$ 個選んだ時の総和の最大値

このような場合、答えを仮定して「平均値 $X$ 以上が実現可能か？」を二分探索する方法がある。
判定が $O(N)$ でできるなら、全体で $O(N \log{A_{max}})$ で可能。

• 平均値は $X$ 以上か？
  • $X$ からの上振れの総和と下振れの総和を比べたら、同じか上振れの方が大きい
  • ＝取り出す $A_i-X$ の総和が0以上
• 中央値は $X$ 以上か？
  • $X$ 以上の要素の個数と未満の個数を比べたら、以上の方か多い
  • ＝取り出す $A_i$ が $X$ 以上なら+1、未満なら-1として総和をとったら、0より大きい

これなら個数を気にせず、常に総和が大きいものだけをDPに記録すればよくなる。

中央値に関しては、定義によって以上・未満の境界が変わるので注意する。

Python3

G - Good Vertices

• $N$ 頂点の有向グラフ、はじめ辺はない
• $t=1,2,...,T$ にかけて、1本ずつ辺 $(u_t,v_t)$ が追加される
  • 自己辺はあり得るが、多重辺はない
• 各頂点について、以下を求めよ
  • 頂点 $1$ からちょうど $L$ 回の移動で到達可能になる最初の時刻
• $2 \le N \le 100$
• $0 \le T \le N^2$
• $1 \le L \le 10^9$

グラフ問題で、頂点 $s→t$ をちょうど $L$ 回で移動するときの○○を求めよ（$L$ はそれなりに巨大）、 という問題は、経路数で見たことがある。

（特に時刻により追加されるとかではない）普通のグラフがあったとして、 ちょうど $L$ 回で $s→t$ に移動できる経路の個数を求めたい。

$$A[u][v] = \begin{cases} 1 & (u→vに辺があるとき) \\ 0 & (ないとき) \end{cases}$$

とすると、$A^L[s][t]$ がその答えとなる。
ダブリングにより高速化すると、 行列1回の乗算 $O(N^3)$ を $\log{L}$ 回行えばよいので、$O(N^3 \log{L})$ で全て求められる。

ある頂点 $k$ について、

• $i→k$ まで $X$ ステップでいける経路数は $A^X[i][k]$
• $k→j$ まで $Y$ ステップでいける経路数は $A^Y[k][j]$
• よって、$i→j$ まで $k$ を介して $X+Y$ ステップでいけるのは $A^X[i][k] \times A^Y[k][j]$

これを $k=1～N$ まで足し合わせると $A^{X+Y}[i][j]$ となるが、この式は行列の乗算と同じことになるということ。

今回はこれの応用バージョンとなる。
$+,\times$ の演算子を、$\min, \max$ にそれぞれ置き換えてしまうと、この問題の解法となる。

• $i→k$ まで $X$ ステップで行く経路の中で、最後に追加された辺は $A^X[i][k]$
• $k→j$ まで $Y$ ステップで行く経路の中で、最後に追加された辺は $A^Y[i][k]$
• $i→j$ まで $k$ を介して $X+Y$ ステップで行く経路の中での最後は $\max(A^X[i][k], A^Y[k][j])$

（もう少し言葉を添えると、$A^X[i][k]$ は 「$i→k$ まで $X$ ステップで行く経路 $P$ の中で最後に追加された辺の時刻を $t_P$ として、 全てのそのような経路の中での $t_P$ の最小値」）

時刻的に最も早いものが求められているので、$k=1～N$ の中でのminが $A^{X+Y}[i][j]$ となる。

今回と演算子は異なるが、可能な条件が以下に説明されている。こちらは最短距離を求めている。

• 動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita

$+,\times$ に相当する演算子と集合が、半環 であればよいらしい。つまり、

• 交換法則、結合法則、分配法則のうち所定のいくつかを満たしていればよい
• 単位元が必要
• 逆元はなくてもよい
• 交換法則、結合法則、分配法則 - 具体例で学ぶ数学

Python3

Ex - Distinct Multiples

• 長さ $N$ の整数列 $(D_1,...,D_N)$ が与えられる
• 次の条件を満たす整数列 $(A_1,...,A_N)$ の個数を $\mod{998244353}$ で求めよ
• 条件
  • 各要素は $1$ 以上 $M$ 以下
  • 各 $i$ につき、$A_i$ は $D_i$ の倍数
  • 各 $A_i$ は全て異なる
• $1 \le N \le 16$
• $1 \le M \le 10^{18}$

包除原理。状態のまとめ方がきれいだが、かなり難しい。

以下、方針は概ね公式Editorialと同様。

$A_i$ が全て異なるという条件がないなら話は簡単で、 $1～M$ の中に $D_i$ の倍数は $\dfrac{M}{D_i}$（切り捨て）個あるのだから、 $i=1～N$ について全て掛け合わせればよい。

しかし実際は同じ値があってはならない。
包除原理を使えそうだが、何を1つの状態として、$(-1)^k$ の $k$ に相当する部分を数えればよいか？

添字のペア $(i,j)$ について、「$A_i$ と $A_j$ が（明示的に）同じ」ことを1つとして、 $\frac{N(N-1)}{2}$ 通りのペアのうち何個が同じかを数えればよい。

• $E$ を、全 $\frac{N(N-1)}{2}$ 個のペアの集合の冪集合とする
• $S$ を、$E$ の適当な1つの要素とする。$S$ はペアの集合である
• 答えは以下となる
  • $\displaystyle \sum_{S \subset E}(-1)^{|S|}(S に含まれる全ペア(i,j)についてA_i=A_jであるような数列の個数)$

これは、$N$ 頂点の無向グラフで、ペアを辺として考えるとイメージしやすい。
ひとつながりになった連結成分の頂点に相当する $A_i$ は全て同じ値となる。

この時、$(1,2)$ かつ $(2,3)$ が同じなら自動的に $(1,3)$ も同じになるが、 包除原理の上では機械的に「$S$ として $(1,3)$ を含む場合」「含まない場合」別々に数えなければならない。
（なんとなく直感に反する）

D = (② ③ ⑤ ⑦)    Sに含む:1 含まない:0

②③ ②⑤ ②⑦ ③⑤ ③⑦ ⑤⑦        パターン数
  0    0    0    0    0    0   →  + M/2 * M/3 * M/5 * M/7
  1    0    0    0    0    0   →  -    M/6    * M/5 * M/7
  0    1    0    0    0    0   →  -    M/10   * M/3 * M/7
  1    1    0    0    0    0   →  +       M/30      * M/7
  1    1    0    1    0    0   →  -       M/30      * M/7
  ...

さて、これで方針は決まったが、困ったことも残る。

頂点ならともかく、辺について含む/含まないの全組み合わせは $2^{\frac{N(N-1)}{2}}$ で最大 $2^{120}$ になる。

制約からして、なんとか頂点集合である $2^N$ 通りくらいにまとめたい。

• $DP[V]=$ 頂点集合 $V$ だけで問題を解いた場合の答え

しかしこれ、たとえば $V=\{②③⑤⑦\}$ に関係するような $S$ を考えると、 連結のしかたにいろんなパターンがあってそれぞれ個数が異なるし、 連結のしかたが同じでも辺の組み合わせや数が異なる場合もあるしで、結構まとめづらそう。

全体が複数の連結成分に分かれているかもしれないことが複雑さに拍車をかけているので、 例えば「番号最小の頂点 $u$ が含まれる連結成分の頂点集合 $V'$」を固定する。

一部分でも連結であることが保証されると、幾分か計算しやすくなる。各頂点集合について

• $g(V)=V$ 全体が連結である場合の、$V$ に相当する部分のみの数列の個数
  • 全て同じ値なので、$V$ に含まれる $D_i$ の総LCMを $L$ として、$\dfrac{M}{L}$（切り捨て）
• $h(V)=V$ 全体が連結になるような辺の張り方で、使われた辺数が偶数なら+1、奇数なら-1 として数え上げたもの

とすると、$u$ を含む連結成分については、その寄与は $g(V')h(V')$ で求められる。

$V'$ 以外の部分については、より小さい部分集合の $DP$ を利用できる。

• $\displaystyle DP[V]=\sum_{V' \subset V,u \in V'}g(V')h(V')DP[V \backslash V']$

なので、$g(),h()$ を求めれば計算できそうなことがわかった。

$g()$ については、集合のLCMを小さい方から計算していくと、$M$ をそれで割った値が該当する。

LCMがオーバーフローするが、$M$ を超えたら $g()$ は0なので、$M+1$ で天井を切っておくなどすればよい。

$h()$ については、定義上、$V$ のサイズが同じなら答えも同じとなる。
サイズを引数にとることにして、$h(1)～h(N)$ を求められればよい。

特に連結を考慮しない全ての辺集合の集合（$2^{\frac{|V|(|V|-1)}{2}}$ 通り）から、 連結でないものを除くことを考える。

連結でない場合、ある頂点 $u$ を固定して、$u$ の含まれる連結成分以外にいくつかの非連結頂点が存在する。

ｕ--○  ○--○
｜      
○        ↑非連結頂点

非連結となった頂点集合 $U$ 内での（連結を考慮しない）辺の張り方は、 完全グラフの辺 $\frac{|U|(|U|-1)}{2}$ 本から 何本かを選ぶことに相当するので、二項係数で表現できるのだが、

完全グラフの辺数を n として、そこから0本、1本、... n本選ぶ場合の数は  
nC0, nC1, ..., nCn

ここで、二項係数での左から奇数番目の和と偶数番目の和は、等しくなる。

• 二項係数の和，二乗和，三乗和 | 高校数学の美しい物語

1 3 3 1             1+3 = 3+1 = 4
1 6 15 20 15 6 1    1+15+15+1 = 6+20+6 = 32

なので、ほとんどの $U$ において、その間の辺の張り方で奇数と偶数は等しい。
$u$ を含む連結成分側の辺数の偶奇がどっちだろうが、○+偶数 と ○+奇数 の個数が同じなので、 辺数の偶奇による+1と-1は互いに打ち消しあうことになる。

唯一、$|U|=1$ の場合のみ、$U$ 内で張れる辺の候補は0本（偶数）の1通りのみとなり、+1 として寄与する。

よって、非連結となる1頂点の選び方が $|V|-1$ 通り、 $u$ が含まれる連結成分内の辺の張り方の寄与が $h(|V|-1)$ なので、漸化式によって求めることができる。

• $h(1)=1$
• $h(|V|)=-(|V|-1)h(|V|-1)$

要は階乗 $(|V|-1)!$ を $|V|$ の偶奇によって正または負にすればよい。

$DP[\phi]=1$ として、以上のやり方でDPを小さい方から計算していける。

計算量は、$V$ を全通り、さらにその中で $V$ の部分集合を全通り試すので、$O(3^N)$ となる。

頂点集合 $V$ を固定し、その中で固定した頂点 $u$ を含む連結成分を考える、という手法が2回登場する。
グラフの数え上げでは、それだけよく使う手法なのだろう。

Python3