第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）E,F問題メモ

第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）

ABCらしからぬ配点
100-300-400-550-600-625-625-650

E - Duplicate

• '1'～'9'からなる文字列 $S$ が与えられる
• 次の操作を繰り返す
  • $T$ を空文字列で初期化する
  • $i=1,2,...,|S|-1$ の順に、$T$ の末尾に「$S_i$ を $S_{i+1}$ 回繰り返した文字列」を追加する
  • $T$ を新たな $S$ とする
• $S$ の長さが1になるまでの操作回数を、$\mod{998244353}$ で求めよ
• ただし永遠に終わらない場合は-1を出力せよ
• $2 \le |S| \le 10^6$

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$ が来ると、消える
  • その後、次に来る末尾の1の連続は、「始めからあった分」+「これまでの操作回数 $\times (c-1)$」

S = 113111115111

113111115111
11113111111111511
1111113111111111111151
111111113111111111111111115
11111111113111111111111111111111
111111111111311111111111111111111
1111111111111131111111111111111111
11111111111111113111111111111111111
111111111111111111311111111111111111
（中略）
1111111111111111111111111111111111111111111111111131
11111111111111111111111111111111111111111111111111113
111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111
（中略）
111
11
1

なので、末尾から、1の連続はまとめてシミュレートすると解ける。

Python3

F - Flip Machines

• $N$ 枚のカードがあり、表は $A_i$、裏は $B_i$ の数字が書かれている
• 最初、全てのカードは表が上を向いている
• $M$ 台のマシンがあり、$j$ 台目のマシンは起動すると以下の働きをする
  • $\dfrac{1}{2}$ の確率でカード $X_j$ を、残りの $\dfrac{1}{2}$ の確率でカード $Y_j$ を裏返す
  • ただし、$X_j=Y_j$ である場合もある
• 今から、以下の操作を順に行う
  1. 起動するマシンの集合 $S$ を決める
  2. $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)$A_i \ge B_i$ である（初期から変えない方が得）
  • $A_i \lt B_i$ である
    • (C)確実に裏返すことができる
    • 確実には裏返すことができない
      • (D) 確実には裏返せない同士で、確率で裏返す候補にできるマシンがある
      • (E) (B)または(C)とペアにすれば確率で裏返す候補にできるマシンがある

• (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$ の部分集合を決めると、裏返す候補にできる $L$ の部分集合も決まる。

$H$ の部分集合を全探索して、最大値を取ればよい。

bitDPする。

• $DP[i][S]=i$ 個目の $H$ までを犠牲にするか否か決定し、裏返す候補にできる $L$ の部分集合が $S$ である場合の、$H$ の方のカードの期待値の合計の最大値

最終的なDPの各 $S$ に、$S$ から計算できる $L$ 側の期待値も加算し、その中の最大値が答え。

いずれも、$O(N 2^{N/2})$ の計算量で解ける。

Python3