第四回日本最強プログラマー学生選手権-予選-(AtCoder Beginner Contest 313)E,F問題メモ
E - Duplicate
問題
例
S = 313
1回目 (3を1回繰り返した文字列)+(1を3回繰り返した文字列)=3111
2回目 (3x1)+(1x1)+(1x1)=311
3回目 (3x1)+(1x1)=31
4回目 (3x1)=3
解法
変な法則なのでひとまず実験する。すると、適当な $S$ から始めるとほぼ永遠に終わらなくなる。
サンプルでは'1'はいっぱい増えても大丈夫そうなので、それ以外の小さい数で試すと、
22 → 22 → 22 → 22 → ...
23 → 222 → 2222 → 222222 → ...
32 → 33 → 333 → 333333 → ...
1212 → 11211 → 11121 → 11112 → 11111 → 1111 → 111 → 11 → 1
2121 → 2112 → 2111 → 211 → 21 → 2
1以外の数が2個続く箇所があるとアウト。(前後に何かしらくっついていたとしても、該当部分の変化は変わらない)
それ以外の場合はいけそう。
改めて、1以外が連続しない数で試してみると、以下が分かる。
末尾の1の連続は、1ずつ短くなる
末尾に1以外の数 $c$ が来ると、消える
S = 113111115111
113111115111
11113111111111511
1111113111111111111151
111111113111111111111111115
11111111113111111111111111111111
111111111111311111111111111111111
1111111111111131111111111111111111
11111111111111113111111111111111111
111111111111111111311111111111111111
(中略)
1111111111111111111111111111111111111111111111111131
11111111111111111111111111111111111111111111111111113
111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111
(中略)
111
11
1
なので、末尾から、1の連続はまとめてシミュレートすると解ける。
Python3
from itertools import groupby
def naive(s):
print(s)
cnt = 0
while len(s) > 1 and len(s) < 1000:
n = len(s)
res = []
for i in range(n - 1):
c = s[i]
k = int(s[i + 1])
res.append(c * k)
s = ''.join(res)
print(s)
cnt += 1
return cnt
def solve(s):
MOD = 998244353
s = s[::-1]
ans = 0
prev_not_1 = False
cum_1 = 0
for c, itr in groupby(s):
c = int(c)
k = len(list(itr))
# print(c, k)
if c == 1:
ans += k + cum_1
prev_not_1 = False
cum_1 = 0
else:
if k > 1 or prev_not_1:
return -1
prev_not_1 = True
ans += 1
cum_1 += (c - 1) * ans
# print(ans)
ans %= MOD
return (ans - 1) % MOD
n = int(input())
s = input()
# print(naive(s))
print(solve(s))
F - Flip Machines
問題
$N$ 枚のカードがあり、表は $A_i$、裏は $B_i$ の数字が書かれている
最初、全てのカードは表が上を向いている
$M$ 台のマシンがあり、$j$ 台目のマシンは起動すると以下の働きをする
今から、以下の操作を順に行う
起動するマシンの集合 $S$ を決める
$S$ に含まれるマシンを番号が小さい順に1回ずつ起動する
うまく $S$ を選んだとき、最終的な「上を向いている面に書かれた数字の合計」の期待値の最大値を求めよ
$1 \le N \le 40$
$1 \le M \le 10^5$
解法
$X_j=Y_j$ か $X_j \neq Y_j$ かで、マシンを区別して考える。
$X_j=Y_j$ のマシンでは、カードを確実に裏返すことができる。
カード $i$ を $X_j \neq Y_j$ のマシンで裏返す候補にしたとき、期待値は平均値 $\dfrac{A_i+B_i}{2}$ となる。
その後、同様のことを何回行おうと、期待値は $\dfrac{A_i+B_i}{2}$ のままである。
その前後で $X_j=Y_j$ で裏返していても同様となる。
↗:裏返された ↘or→:裏返されなかった
1回目 2回目
Ai
↗
Bi→Bi
↗
Ai Bi
↘ ↗
Ai→Ai
↑何回分岐しようと、全ての確率は等しく、またAiとBiが同数現れる
よって、$M$ の制約は大きいが、同じペアのマシンを選ぶ必要は無いし、その順番も関係ないことが分かる。
問題の主旨は、各カードに対し、以下のいずれかを割り当てると言い換えられる。
$X_j=Y_j$ のマシンで裏返すことを「確実に裏返す」、$X_j \neq Y_j$ のマシンの対象とすることを「確率で裏返す」と表現する。
①1度も裏返す候補にしない → 期待値 $A_i$
②1度確実に裏返し、確率で裏返す候補にはしない → 期待値 $B_i$
③1度でも、確率で裏返す候補にする → 期待値 $\dfrac{A_i+B_i}{2}$
各カードは、マシンによって以下のように分類できる。
(A)は、どう足掻いても①
(B)(C)は、①か②で確実に高い面を選べるが、(E)のために③にすることもできる
(D)は、③を選んだ方が得。特に犠牲にするものもない
(E)は、①で低い方を仕方なく取るか、またはペアとなる(B)(C)を③にすることで、自身も③にできる
(A)と(D)の最適解はそれぞれ決定し、残る (B)(C) と (E) をどうするかという問題になる。
(B)(C)に含まれるカードの集合を $H$、(E)に含まれるのを $L$ とする。
$H$ のとある1枚の犠牲(③にする)で、複数の $L$ も③にして期待値を上げることができうるが、その組み合わせはどうすれば最適か?
それぞれに含まれるカードの数によって、2通りの解法がある。
$N \le 40$ なので、小さい方の集合サイズは多くとも $20$ であり、計算量 $2^{20}$ のアルゴリズムが間に合う。
$|H| \le |L|$ の場合
犠牲にする $H$ の部分集合を決めると、裏返す候補にできる $L$ の部分集合も決まる。
$H$ の部分集合を全探索して、最大値を取ればよい。
$|H| \gt |L|$ の場合
bitDPする。
最終的なDPの各 $S$ に、$S$ から計算できる $L$ 側の期待値も加算し、その中の最大値が答え。
いずれも、$O(N 2^{N/2})$ の計算量で解ける。
Python3
n, m = map(int, input().split())
cards = [list(map(int, input().split())) for _ in range(n)]
machines = set()
sure = set()
for _ in range(m):
x, y = map(int, input().split())
x -= 1
y -= 1
if x == y:
sure.add(x)
else:
if x > y:
x, y = y, x
machines.add((x, y))
# 確実に高い方が選べるカード
high = [0] * n
# 裏返せるマシンが1つも無いカード
no_chance = [1] * n
for i in range(n):
if i in sure:
high[i] = 1
no_chance[i] = 0
cards[i].sort(reverse=True)
elif cards[i][0] >= cards[i][1]:
high[i] = 1
# 確実には低い方しか選べないが、そういうの同士で潰しあえるカード
low_both = [0] * n
for x, y in machines:
if high[x] == 0 and high[y] == 0:
low_both[x] = low_both[y] = 1
no_chance[x] = no_chance[y] = 0
# 確実には低い方しか選べず、確実に高い方を選べるカードを犠牲にするとひっくり返せるかもしれない
l_set = {i for i in range(n) if high[i] == 0 and low_both[i] == 0 and no_chance[i] == 0}
h_set = {i for i in range(n) if high[i] == 1 and no_chance[i] == 0}
l_list = sorted(l_set)
h_list = sorted(h_set)
l_reindex = {l: i for i, l in enumerate(l_list)}
h_reindex = {h: i for i, h in enumerate(h_list)}
l_len = len(l_set)
h_len = len(h_set)
# 各highがひっくり返せるlowをbitflagで保持
reversible = [0] * h_len
for x, y in machines:
if high[x] == 1 and y in l_set:
i = h_reindex[x]
j = l_reindex[y]
reversible[i] |= 1 << j
elif high[y] == 1 and x in l_set:
i = h_reindex[y]
j = l_reindex[x]
reversible[i] |= 1 << j
# print(l_list)
# print(h_list)
# print(reversible)
# 小さい方で処理を分ける
res = 0
if h_len < l_len:
for bitset in range(1 << h_len):
tmp = 0
tmpset = 0
for i in range(h_len):
x = h_list[i]
if bitset & (1 << i):
tmpset |= reversible[i]
tmp += sum(cards[x])
else:
tmp += cards[x][0] * 2
for j in range(l_len):
y = l_list[j]
if tmpset & (1 << j):
tmp += sum(cards[y])
else:
tmp += cards[y][0] * 2
res = max(res, tmp)
else:
INF = 1 << 60
dp = [-INF] * (1 << l_len)
dp[0] = 0
for i in range(h_len):
x = h_list[i]
use = sum(cards[x])
nouse = cards[x][0] * 2
rev = reversible[i]
for bitset in range((1 << l_len) - 1, -1, -1):
if bitset & rev != rev:
dp[bitset | rev] = max(dp[bitset | rev], dp[bitset] + use)
dp[bitset] += nouse
for bitset in range(1 << l_len):
tmp = dp[bitset]
for j in range(l_len):
y = l_list[j]
if bitset & (1 << j):
tmp += sum(cards[y])
else:
tmp += cards[y][0] * 2
res = max(res, tmp)
for x in range(n):
if low_both[x] == 1:
res += sum(cards[x])
elif no_chance[x] == 1:
res += cards[x][0] * 2
print(res / 2)