AtCoder Beginner Contest 281 F,G問題メモ

AtCoder Beginner Contest 281

F - Xor Minimization

• $N$ 個の非負整数の集合 $A=\{A_1,...,A_N\}$
• 好きな整数 $x$ を選び、$A$ の各項を、$x$ を XOR したものに置き換えた集合を $B$ とする
• $B$ の最大値としてあり得る最小値を求めよ
• $1 \le N \le 150000$
• $0 \le A_i \lt 2^{30}$

（※以下、桁は2進数での桁を表し、小さい方から（1,2,4,8,16,… を表す桁の順に）1,2,3,… 桁目とする）

再帰で分割していく。

もし、$A$ の中で $d$ 桁目が'0'のものと'1'のものが混在していたら、 どのように $x$ を選ぼうと、$B$ でも'0'と'1'が混在してしまう。

逆に、全て'0'か全て'1'なら、$B$ の全てで必ず $d$ 桁目は'0'にできる。

それを踏まえて、上位bitから考える。

いま、$A$ の中で0と1が混在しているような最上位桁を $d$ とする。
すると、$B$ の最大値も $d$ 桁にならざるを得ない。

$A$ を「$d$ 桁目が0であるグループ」「1であるグループ」に分割すると、 同じグループの操作後の $d$ 桁目は同じになる。

さて、どちらのグループの操作後の $d$ 桁目を0にし、どちらを1にすべきか？

操作後の $d$ 桁目が0になるグループは、その時点で必ず1になるグループより小さくなることが確定するので、 $d-1$ 桁目以降がどんなに大きくなってもかまわない。
$x$ を決める際は、1になるグループの $d-1$ 桁目以降を最小化することに注力すればよい。

よって、それぞれのグループで $d-1$ 桁以降のみで全体と同じ問題を解き、「もしこっちのグループを1にした場合、最小値はいくつになる？」を調べる。

その結果、最大値が小さくなる方を、操作後に $d$ 桁目が1となるようにすればよい。

d桁目
v        ｸﾞﾙｰﾌﾟ
00101101 -,        _0101101  グループ0のみで
01010101  | 0  →  _1010101  全体と同じ問題を解いた答えをpとする
01101110 -'        _1101110
10111000 -,
11100011  | 1  ┐  _0111000  グループ1のみで
11001100 -'    └> _1100011  全体と同じ問題を解いた答えをqとする
                   _1001100

p <= q なら、グループ0の操作後のd桁目が 1 となるようにし、答えは 10000000 + p
p >  q なら、グループ1の操作後のd桁目が 1 となるようにし、答えは 10000000 + q

これを再帰的に処理すれば良い。

処理の途中でグループのサイズが1個になったら、 後はその1個が操作後に完全に0になるような $x$ を選べば良いので、（分割問題の答えは $0$） 以降の桁は探索を打ち切れる。

仮に打ち切らず最終桁まで処理したとしても、$N$ 個の要素がそれぞれ $\log_2{A_i}$ 回、 bitが0か1かチェックされたり分割されたりすることになるので、$O(N \log{A_{max}})$ で処理できる。

Python3

G - Farthest City

• $N$ 頂点の単純連結無向グラフの内、以下の条件を満たすものの個数を $M$ で割ったあまりで答えよ
• 条件
  • 頂点1からの最短距離を考えると、頂点 $N$ が単独で最も遠い頂点である
  • 言い換えると、頂点 $u=2,...,N-1$ の全てについて、$1→u$ の最短距離が、$1→N$ の最短距離より真に小さい
• $3 \le N \le 500$

$M$ が素数とは限らないので、いつもの逆数modや、FFTによる畳み込みは使えない点に注意。
まぁ $N$ が小さいので、二項係数 ${}_nC_r$ なんかは $n \le N$ の範囲なら事前計算してしまえる。

素直(?)に考えると3次元DPで遷移にも $N$ かかって $O(N^4)$ 解法が思いつくが、 実は1次元省略して $O(N^3)$ にできる、という問題。

• $DP[i,j,k]=$ 頂点1からの最短距離が $i$ までを考えて、頂点1を含め $j$ 個を既に使っていて、特に最短距離が $i$ である頂点数が $k$ であるようなグラフの個数

距離   1   2  ...    i

  ①--○--○- ...  -○
    `-○    ` ...  -○
                   -○
                    ↑  ...k個
 └─────────┘ ...j個

ここに、最短距離が $i+1$ の頂点を $l$ 個追加することを考える。

• ① $l$ 個の選び方
  • 既に使った頂点と $N$ を除く $N-j-1$ 個から $l$ 個選ぶ
  • ${}_{N-j-1}C_{l}$ 通り
• ② 最短距離が $i$ である頂点群と $i+1$ である頂点群の間の辺の張り方
  • $i+1$ の頂点1つにつき、$i$ の $k$ 個のそれぞれとの辺を張る/張らないを決められる
    • $i-1$ 以前と辺を張ったら最短距離が $i+1$ でなくなるため、あくまで張るのは直前 $i$ との間のみ
    • $2^k$ 通りの張り方があるが、そのうち「全て張らない」パターンだけは除く必要がある
    • よって、1つにつき $2^k-1$ 通り
  • それが $l$ 個なので $(2^k-1)^l$ 通り
• ③ $i+1$ 同士の辺の張り方
  • 同じ最短距離同士は張っても問題ない
  • $\frac{l(l-1)}{2}$ の全ての頂点間につき、張る/張らないを決められる
  • $2^{l(l-1)/2}$ 通り

これらを掛け合わせたものとなる。

• $DP[i+1,j+l,l]+=DP[i,j,k] \times ① \times ② \times ③$

実は、遷移の式を見ても $i$ が出てこないことからもわかるとおり、$i$ の次元は省略できる。
最短距離が異なっていても「今までに $j$ 個使って、そのうち直前が $k$ 個」という情報さえ一致していれば同じ遷移ができる。

• $DP[j,k]=$ 頂点1を含め $j$ 個を既に使っていて、特に最短距離が最も長い頂点が $k$ 個であるようなグラフの個数
• $DP[1,1]=1$
• $DP[j+l,l]+=DP[j,k] \times ① \times ② \times ③$

さて、$j=N-1$ まで埋め終えたとして、最後に頂点 $N$ との辺を考慮しつつ合計する。

末尾 $k$ 個と頂点 $N$ 間の辺の張り方は、上記②の考え方と同じく $2^k-1$ 個ある。
$DP[N-1,k] \times (2^k-1)$ を $k=1,...,N-2$ で合計すれば答え。

Python3