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

n, k = map(int, input().split())
coef = []
for _ in range(n):
    a, b = map(int, input().split())
    coef.append(((a - 1) / b, a, b))
coef.sort()
dp = [0] * (k + 1)
dp[0] = 1
for i in range(n):
    ndp = dp.copy()
    _, a, b = coef[i]
    for j in range(k):
        ndp[j + 1] = max(ndp[j + 1], dp[j] * a + b)
    dp = ndp
print(dp[-1])

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

n, m = map(int, input().split())
links = [0] * n
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u] |= 1 << v
    links[v] |= 1 << u


def get_bit_basis(aaa):
    basis = []
    aaa = set(aaa)
    aaa.discard(0)
    while aaa:
        b = max(aaa)
        basis = [min(a, a ^ b) for a in basis]
        basis.append(b)
        aaa = {min(a, a ^ b) for a in aaa}
        aaa.discard(0)
    return basis


basis = get_bit_basis(links)
for b in basis:
    if b.bit_count() == 1:
        print('No')
        exit()
bl = len(basis)
free = 0  # 基底に、自身の位置が最上位bitであるものがないbitの集合
b = 1 << (n - 1)
i = 0
while b > 0:
    if i == bl:
        free |= b
    elif b > basis[i]:
        free |= b
    else:
        i += 1
    b >>= 1


def solve_free(free, basis):
    ans = [0] * n

    f = free
    i = 0
    while f:
        if f & 1:
            ans[i] = 1
        i += 1
        f >>= 1

    for b in basis:
        if (b & free).bit_count() % 2 == 1:
            ans[b.bit_length() - 1] = 1

    return ans


ans = solve_free(free, basis)
s = 1
for i in range(n):
    if (1 << i) & free:
        result = solve_free(free ^ (1 << i), basis)
        for j in range(n):
            ans[j] |= result[j] << s
        s += 1

print('Yes')
print(*ans)

目次

AtCoder Beginner Contest 366 F,G問題メモ

F - Maximum Composition

問題文

制約

解法

G - XOR Neighbors

問題文

制約

解法