パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）E,F問題メモ

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）

E - Lucky 7 Battle

• '0'～'9' からなる長さ $N$ の文字列 $S$ と、'T'と'A'からなる長さ $N$ の文字列 $X$ が与えられる
• TさんとAさんがゲームをする
• ゲームは、空文字列で初期化された文字列 $T$ を使って、以下の通り行う
• ゲームの進行
  • $i$ ターン目では、$X_i$ さんが行動する
  • $X_i$ さんは、$T$ の末尾に '0' または $S_i$ の好きな方を追加する
• 最終的な $T$ を10進数として見たときに、7の倍数ならTさんの勝ち、それ以外ならAさんの勝ち
• 両者が最適に行動したときの勝者を求めよ
• $1 \le N \le 2 \times 10^5$

前から見ていくと、TさんもAさんもどう行動すれば最適か、見通しを立てにくい。
後ろから見ていくとよい。

• $DP[i][j]=$ $i$ ターン終了の時点の $T$ を7で割ったときに、あまりが $j=0～6$ なら（ゲーム終了まで適切に続ければ）Tさんが勝てる場合はTrue, 勝てない場合はFalse

初期値は $DP[N][0]=$ True、それ以外はFalse。
最終的に $DP[0][0]=$ TrueならTさんの勝ち。

遷移を考える。

               i           k : 0 1 2 3 4 5 6
 159 .... 23   5     DP[i][k]: o x o o x o x

この状態の時、$DP[i-1]$ を求めたい。

$j=0～6$ について1つずつ調べる。$j$ を固定すると、$i$ ターン目の操作を加えた時のあまりは2通り。

• $k_{1} = (j*10 + 0 ) \% 7$
• $k_{2} = (j*10 + S_i) \% 7$

Si=5 のとき、
i-1ターン目までで作られた T を7で割ったあまりがたとえば 3 なら、
i ターン目までで作られる T を7で割ったあまりは以下のいずれか。

Siを使わないと 30 % 7 = 2
Siを使うと     35 % 7 = 0

これが、Tさんが勝つ状態になっているかどうかで、$DP[i-1][j]$ を求められる。

• $i$ ターン目がTさんの場合
  • $DP[i][k_{1}], DP[i][k_{2}]$ の少なくともどちらか一方がTrueなら、$DP[i-1][j]=$ True
• $i$ ターン目がAさんの場合
  • $DP[i][k_{1}], DP[i][k_{2}]$ のどちらもTrueなら、$DP[i-1][j]=$ True

Tさんは自分が勝てる方を選べばよいので、遷移先のどれか1つがTrueなら十分。

AさんはTさんが勝ってしまうのを避けるので、避けられない（＝遷移先が全てTrueの）状態でないといけない。

Si=5          k : 0 1 2 3 4 5 6
        DP[i][k]: o x o o x o x    のとき

                        Xi=Tの時   Xi=Aの時
j      k      DP[i][k]  DP[i-1][j] DP[i-1][j]
0  →  0, 5      o, o       o          o
1  →  3, 1      o, x       o          x
2  →  6, 4      x, x       x          x
3  →  2, 0      o, o       o          o
4  →  5, 3      o, o       o          o
5  →  1, 6      x, x       x          x
6  →  4, 2      x, o       x          x

これでDPを計算していけばよい。

Python3

F - Coprime Present

• $A$ 以上 $B$ 以下の $B-A+1$ 個の整数の集合から部分集合を作る
• どの2つの要素も互いに素である部分集合は何通りできるか求めよ
  • 空集合や要素数1の集合も1つとして数える
• $1 \le A \le B \le 10^{18}$
• $B-A \le 72$

2つの数が互いに素というのは、$i=2^3 \cdot 7^2 \cdot 11, j=3^2 \cdot 5$ のように、各整数を素因数分解したときに同じ素因数が出てこないということ。

指数部分は重要でないので捨てて、$i=\{2,7,11\}, j=\{3,5\}$ のように、各整数の素因数の集合を事前計算しておく。

次に、$B-A \le 72$ という変わった制約に注目する。

$73$ 以上の素因数は元の整数集合に2つ以上出てこず、明らかに被らないので、考える必要が無い。
事前計算で調べるのは $71$ までの素因数だけでよく、その個数はちょうど $20$ 個となる。

• $DP[i][S]=i$ 番目の整数まで部分集合に入れる入れないを決めたとき、既に部分集合で使われている素因数の集合が $S$ であるパターン数

ただし $S$ は既述の通り $71$ まで。つまり $2^{20} \simeq 10^6$ 程度の状態数で済む。$i$ の範囲も73個が上限なので、$S$ をbitフラグなどで表現しておけば十分間に合う。

初期状態は $DP[0][0]=1$。答えは $\displaystyle \sum_S DP[B-A+1][S]$。

遷移は、$i$ 番目の整数に含まれる素数集合のbitフラグを $p_i$ として、各 $0 \le s \lt 2^{20}$ に対し

• $s$ と $p_i$ に同じ位置のbitが立っていないときのみ、$DP[i][s \ | \ p_i] += DP[i-1][s]$

とすればよい。

Python3