AtCoder Beginner Contest 366 F,G問題メモ

AtCoder Beginner Contest 366

F - Maximum Composition

問題文

$N$ 個の一次関数 $f_1,f_2,\ldots,f_N$ が与えられます。 $f_i(x)=A_i x+B_i$ です。
$1$ 以上 $N$ 以下の相異なる $K$ 個の整数からなる長さ $K$ の数列 $p=(p_1,p_2, \ldots p_K)$ について、 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1)\ldots ))$ としてありえる最大値を求めてください。

制約

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq K \leq \text{min}(N,10)$
$1 \leq A_i,B_i \leq 50$ $(1 \leq i \leq N)$
入力はすべて整数

解法

使用する優先順位が決まっているDP。Educational DP Contest にも類題がある。

2つの関数 $f_i,f_j$ を同時に採用するとき、どっちを先に適用した方が結果が大きくなるかが、他の $f$ に依らず決まっていると、考慮すべきパターンが減って嬉しい。

$i$ が先: $A_j(A_i x + B_i)+B_j$
$j$ が先: $A_i(A_j x + B_j)+B_i$

展開すると $x$ を消せて、 $B_iA_j+B_j \ge A_iB_j+B_i$ なら、 $i$ が先の方がよいとなる。
$j$ を左、 $i$ を右に上手くまとめることができて、 $\dfrac{A_j-1}{B_j} \ge \dfrac{A_i-1}{B_i}$ なら $i$ が先の方がよいとわかる。

$g(j) \ge g(i)$ のような関係で常に $i$ がよい、と表現できると、推移関係が成り立つ。
つまり、 $g(i) \ge g(j)$ かつ $g(j) \ge g(k)$ なら、必ず $g(i) \ge g(k)$ も成り立つので、関数全体を“先に使った方がいい”順にソートできる。

関数を $C_i=\dfrac{A_i-1}{B_i}$ を基準にソートする。
使用する $K$ 個の関数を決めた時、 $C_i$ が小さい方から使った方がよい（同率の場合は変わらない）ということになる。
$A_i,B_i$ とも小さいので小数のまま計算しても誤差は大丈夫。

では、 $C_i$ が小さい方から $K$ 個を使えばよいのか？というと、そういうわけではない。
$C_i$ はあくまで使うときの優先順位を決めるものであって、使用/不使用の優先度を決めるものではない。

使用する組は探索する必要があるが、 $K$ が小さいので使用個数を持ったDPができる。

$\mathrm{DP}[i,j]=C$ が小さい方から $i$ 個の関数の使用/不使用を決めて、そのうち $j$ 個使用した場合の、暫定最大値

これで $O(NK)$ で求められる。

Python3

G - XOR Neighbors

問題文

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。 $i$ 番目の辺は頂点 $u_i$ と $v_i$ を双方向に結びます。
このグラフの各頂点に $1$ 以上 $2^{60}$ 未満の整数を書き込む方法であって、次の条件を満たすものが存在するか判定し、存在するならば一つ構築してください。
次数が $1$ 以上のすべての頂点 $v$ について、隣接する頂点 ( $v$ 自身は含まない) に書き込まれている数の総 XOR が $0$ となる

制約

$1 \leq N \leq 60$
$0 \leq M \leq N(N-1)/2$
$1 \leq u_i \lt v_i \leq N$
$i \neq j$ ならば $(u_i,v_i) \neq (u_j,v_j)$

解法

複数の桁を同時に考えるのは難しいので、以下の問題を考える。

各頂点に「 $0$ または $1$ 」を書き込んで、全ての頂点 $v$ について、隣接する頂点に書き込まれた整数の総XORが $0$ となるようにする方法を「複数」求めよ
全ての頂点について、そこに $1$ が書き込まれるような方法が複数の解の中に少なくとも1つあるようにせよ

この方法が60個以下に抑えられれば、1つめの解を $2^0$ の位、2つめの解を $2^1$ の位、… にすることで、全ての頂点を0以外にできる。

頂点  1  2  3  4               頂点   1   2   3   4
解1   0  0  1  1
解2   1  0  1  0   →  元の問題の解 010 100 111 101
解3   0  1  1  1

では、その解の1つはどう求めたらよいか？

$N$ が小さいので、隣接頂点をbitsetで考える。

各頂点 $i$ に対し、隣接頂点に'1'を立てたbitsetを $A_i$ とする。
（ $i$ が頂点 $\{6,4,2,1\}$ と隣接していた場合、 $A_i=$ 000101011 みたいな）

各頂点への'0'と'1'の割り当てもbitsetで考え、例えば $X=$ 101010101 のように割り当てたとする。

この時、 $A_i \& X$ の pop count が偶数なら、 $i$ についてはXOR条件を満たせることを意味する。
「 $a \& b$ の pop count が偶数となる」ことを、 $E(a,b)$ と表現することにする。

「全ての頂点 $i$ について、 $E(A_i,X)$ が真となる」ような $X$ が、解の1つとなる。

この時、例えば「頂点 $u$ は $\{1,2,3,4\}$ に隣接（ $A_u=1111$ ）し、 $v$ は $\{2,3\}$ に隣接（ $A_v=0110$ ）していた」なら、そのXORである $1001$ に対しても、 $E(1001,X)$ は真となっていなければならない。
連鎖的に考えると、 $A=(A_1,...,A_N)$ からいくつか選んでXORして作れるようなbitset $B$ に対しては、全て $E(B,X)$ が真となっているはずである。

この性質から、XOR基底を求める解法が考えられる。

Gauss-Jordan の掃き出し法と、連立一次方程式の解き方 - けんちょんの競プロ精進記録

$A$ を掃き出して以下のような形にする。この掃き出した結果を $A'$ とする。

1 0 1 1 0 0 1 0 0    * 最上位bitの位置は（0を除き）重複しない。
  1 1 0 0 0 0 0 1
        1 0 1 0 1    * ある要素で最上位bitが立つ桁は、
          1 0 0 1      必ず他の要素は'0'。
              1 1
                0    * 最上位bitが立つ要素がない桁は、
                0      各要素、'0'でも'1'でもよい。
                :

$A'$ の各行に対して $E(A'_i,X)$ が真なら、それらを任意にXORした要素 $c$ に対しても $E(c,X)$ は真となる。
$A'$ は $A$ のXOR基底であり、 $A'$ の要素同士のXORで全ての $A$ の要素を作れる。

よって、 $A'$ の（0でない）要素 $A'_1,A'_2,...$ に対して、全て $E(A'_i,X)$ が真となる $X$ を考えればよい。

$A'_i$ の中に、1000 のように「最上位bitにしか'1'が立っていない数」が存在する場合、 $E(A'_i,X)$ が真となるためには、 $X$ の下から $4$ 桁目はどうしても'0'にせざるを得ない。
つまり、頂点 $4$ に'1'を書き込むような解を作ることができないので、不可能となる。

そうで無い場合、 $X$ の「最上位bitが立つ要素が無い桁」に割り当てる値を全て固定する。
すると、各 $i$ に対し、 $A'_i \& X$ の値が未定なのは $A'_i$ の最上位bitのみとなる。
つまり、各 $A'_i$ の最上位bitを、0にすべきか1にすべきかが一意に決まり、組み合わせると $X$ 全体が一意に決まる。

            v v     v   v    ←最上位bitが立つ要素がない桁
 A'1    1 0 1 1 0 0 1 0 0
 A'2      1 1 0 0 0 0 0 1
 A'3            1 0 1 0 1
 A'4              1 0 0 1
 A'5                  1 1

    X   ? ? 0 1 ? ? 1 ? 1    とした場合

A'1&X   ? 0 0 1 0 0 1 0 0    → ? = 0
A'2&X   0 ? 0 0 0 0 0 0 1    → ? = 1
   :            ...のように、各行、最上位bitが一意に決まる
   
    X   0 1 0 1 0 1 1 1 1    よって、X 全体も一意に決まる

今回はなるべく多くを1にしたいので、固定の仕方は

最上位bitが立つ要素がない桁が、全て'1'
最上位bitが立つ要素がない桁の、どれか1つだけが'0'

これで、全ての $X$ の桁が、どれかしらの試行で'1'となる。

Python3