目次
Tenka1 Programmer Contest 2019 C,D,E,F 問題メモ
C - Stones
問題
- $N$ 個の石が一列に並び、白か黒で塗られている
- 色は長さ $N$ の文字列 $S$ によって示され、$i$ 文字目が
.のとき左から $i$ 個目の石が白、#のとき黒 - いくつかの石の色を塗り替え、「黒い石のすぐ右に白い石がある」箇所がないようにしたい
- 塗り替える必要のある石の個数の最小値を求めよ
解法
最終状態から考えると、'#.'という箇所が1箇所でもあるとダメなので、ある場所に黒が現れたら、そこから右は全て黒になるしか無い。
......#######
こんな感じになる。 境界が $N+1$ 通り考えられるので、全て試して、最も少ないのが答え。
塗り替える石は「最終的に白になるのに初期状態が黒」「黒になるのに初期状態が白」の合計なので、
- 左から数えて、現れた
#の数 - 右から数えて、現れた
.の数
を別々に計算して、合計する。
S = . # # . . . # # # .
i 0 1 2 3 4 5 6 7 8 9 10 .と#の境界候補
---------------------------
→ 0 0 1 2 2 2 2 3 4 5 5 現れた # の数（iが境界だったら、#から.に塗り替えなくてはいけない石の数）
← 5 4 4 4 3 2 1 1 1 1 0 現れた . の数（iが境界だったら、.から#に塗り替えなくてはいけない石の数）
計 5 4 5 6 5 4 3 4 5 6 5
^------------ここが最小
. . . . . . # # # # 最終状態はこうなる
n = int(input())
s = input()
f = [0]
tmp = 0
for c in s:
if c == '#':
tmp += 1
f.append(tmp)
b = [0]
tmp = 0
for c in s[::-1]:
if c == '.':
tmp += 1
b.append(tmp)
b.reverse()
print(min(map(sum, zip(f, b))))
D - Three Colors
問題
- $N$ 個の整数、$i$ 個目の整数は $a_i$
- 与えられたすべての整数を赤、緑、青の3色のいずれかで塗る
- 以下の条件を満たす塗り分け方の個数を、$\mod{998244353}$ で求めよ
- 赤、緑、青で塗った整数の総和をそれぞれ $R,G,B$ とすると、この長さの3辺からなる、正の面積を持つ三角形が存在する
- 同じ整数も区別する
- $3 \le N \le 300$
- $1 \le a_i \le 300$
解法
正の面積を持つ三角形とは、つまり、一番長い辺 $A$ とそれ以外の2辺 $B,C$ が、$A \lt B+C$ となっているということである。 （一番長い辺が他の2辺の合計より長かったら、三角形を作れない）
包除で求める対象を考察した後、DPで具体的な数を数え上げる。
求める対象
条件を満たす組み合わせは3辺がバランスよく配分されてないといけないが、「バランスよい状態」を直接求めるのは難しいことがある。 逆に極端な組み合わせは求めやすく、それを全体から引くと上手くいく、この問題はそういうタイプである。
整数全体の和を $S$ とすると、三角形が出来ないとき、どれか1辺が $\frac{S}{2}$ 以上である。
なので、どれか1辺に $\frac{S}{2}$ 以上の整数が集中してしまう組み合わせの数を求めて全体から引けばよい。
┌ 3色の塗り分け方全体 ────┐ R >= S/2 となる塗り分け方の集合を Ro と表す │ ┌ R >= S/2 ┐ │ │ │ ┌─┼────┐ │ 答え = 全体 │ ┌┼───┼┐│ │ │ - Ro - Go - Bo │ │└───┼┼┘ │ │ + (Ro∩Go) + (Go∩Bo) + (Bo∩Ro) │ │ └┼ B >= S/2 ┘ │ - (Ro∩Go∩Bo) │ └ G >= S/2 ┘ │ └───────────────┘
ここで、R,G,Bは互いに入れ替えても組み合わせ数は変わらないので、最も長いのをRに固定して考える。
まず、Ro∩Go∩Bo は、R+G+B=S なのに3つともS/2以上というのはあり得ないので0通り。
Ro∩Goは、$R=G=\frac{S}{2},B=0$ ちょうどの時のみ。これは、$\frac{S}{2}$ になるような組み合わせ方が $K$ 通りあったとすると、Rの選び方を決めるとGも決まるので、$K$ 通り。
Roは、$R \ge \frac{S}{2}$ となる、ある1つの赤の塗り方が $L$ 本で達成されたとすると、残り $N-L$ 本を2つに振り分けるので、$2^{N-L}$ 通り。 これを全ての $R \ge \frac{S}{2}$ となる赤の塗り方で合計した値となる。
DP
2種類のDPを用いる。
$DP1[i][k]$: $a_i$ まで見たところで、赤の合計が $k$ となるような、青、緑の塗り方も含めた場合の数
$DP2[i][k]$: $a_i$ まで見たところで、赤の合計が $k$ となるような、赤の塗り方だけに着目した場合の数（青、緑の塗り方は考慮しない）
DP2は言い換えれば「赤で塗らないのは必ず緑で塗る」場合の数とも言える。
- 初期値
- DP1[0][0] = 1
- DP2[0][0] = 1
- 遷移
- DP1
- $a_i$ を赤に塗る場合
- DP1[i+1][k+a] += DP1[i][k]
- $a_i$ を赤に塗らない場合、青か緑に塗るので2通り
- DP1[i+1][k] += DP1[i][k] * 2
- DP2
- DP1の、青緑の塗り分けをしない
- DP2[i+1][k+a] += DP2[i][k]
- DP2[i+1][k] += DP2[i][k]
最後まで進めて、先ほどの包除の式に以下を当てはめればよい
- 全体の塗り方
- $N$ 個の整数を3色に塗るので $3^N$
- Ro,Go,Bo
- DP1[N][k] のうち、$k \ge \frac{S}{2}$ である場合の数の合計
- Ro∩Go, Go∩Bo, Bo∩Ro
- DP2[N][S/2]
遷移自体はナップサック問題に似ている。$a_i$ だけずらしながら足し込むので、NumPyを使って高速化できる。逆に、NumPyを使わないと、Pythonでは厳しいか？
import sys
import numpy as np
n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353
s = sum(aaa)
dp1 = np.zeros(s + 1, dtype=np.uint32)
dp2 = np.zeros(s + 1, dtype=np.uint32)
dp1[0] = 1
dp2[0] = 1
for a in aaa:
dp1 = (dp1 * 2 + np.roll(dp1, a)) % MOD
dp2 = (dp2 + np.roll(dp2, a)) % MOD
h = (s + 1) // 2
ans = (pow(3, n, MOD) - dp1[h:].sum() * 3) % MOD
if s % 2 == 0:
ans = (ans + dp2[h] * 3) % MOD
print(int(ans))
E - Polynomial Divisors
問題
- $N$ 次の整数係数の多項式 $f(x) = a_Nx^N + a_{N-1}x^{N-1} + ... + a_1x + a_0$ が与えられる
- 以下の条件を満たす素数 $p$ を全て求めよ
- $x$ にいかなる整数を代入しても、$f(x)$ は $p$ の倍数である（0倍含む）
- $0 \le N \le 10^4$
- $-10^9 \le a_i \le 10^9$
解法
フェルマーの小定理を知っていることがほぼ前提となる。
$x^{p-1} \equiv 1 \mod{p}$ （ただし$x$と$p$は互いに素）
$p$と互いに素な$x$
フェルマーの小定理より、$p-1$ ごとに、$x$ の係数はまとめることができる。
f(x) ＝ a9x^9 + a8x^8 + a7x^7 + a6x^6 + a5x^5 + a4x^4 + a3x^3 + a2x^2 + a1x + a0
≡ (a7 + a3) x^3 + (a6 + a2) x^2 + (a9 + a5 + a1) x + (a8 + a4 + a0) mod 5
このまとめたそれぞれの係数が $p$ の倍数となっていれば、任意の $x$ で $f(x)$ は $p$ の倍数と言える。
ただ、それ以外に答えが存在しない、という証明はよく理解できていない。
$p$と互いに素で無い$x$
$p$ は素数なので $x \equiv 0 \mod{p}$ と表せる。
これを $f(x)$ に代入すると $f(0) = a_0 \mod{p}$ となるので、$a_0$ はそれ単体で $p$ の倍数となっている必要があることがわかる。
以上を総括すると、$f(x)$ が任意の整数 $x$ に対し $p$ で割り切れるための条件は、
- $a_0$ が $p$ の倍数
- 以下が全て $p$ の倍数
- $a_1 + a_p + a_{2p-1} + ...$
- $a_2 + a_{p+1} + a_{2p} + ...$
- $a_3 + a_{p+2} + a_{2p+1} + ...$
- …
- $a_{p-1} + a_{2p-2} + a_{3p-3} + ...$
$p \lt N+2$ である素数 $p$ については、実際に1つ1つ確かめる。たかだか $N \le 10^4$ なのでそれ以下の素数の数は知れている。
$p \ge N+2$ となったら、もう $f(x)$ の係数はまとめられない。よって $a_N～a_0$ 全てが $p$ の倍数である必要がある。 これは、全ての係数の最大公約数をとり、その素因数分解をすることで、求められる。
import sys
from fractions import gcd
def eratosthenes_generator():
yield 2
n = 3
h = {}
while True:
m = n
if n in h:
b = h[n]
del h[n]
else:
b = n
yield n
m += b << 1
while m in h:
m += b << 1
h[m] = b
n += 2
def prime(n):
ret = []
for i in eratosthenes_generator():
if n % i == 0:
ret.append(i)
while n % i == 0:
n = n // i
if n == 1 or i * i > n:
break
if n > 1:
ret.append(n)
return ret
def solve(n, aaa):
g = abs(aaa[-1])
for a in aaa[:-1]:
if a != 0:
g = gcd(g, abs(a))
ans = set(prime(g))
for p in eratosthenes_generator():
if p > n + 2:
break
if p in ans or aaa[0] % p != 0:
continue
q = p - 1
if all(sum(aaa[i::q]) % p == 0 for i in range(q)):
ans.add(p)
ans = sorted(ans)
return ans
n = int(input())
aaa = list(map(int, sys.stdin))
aaa.reverse()
print('\n'.join(map(str, solve(n, aaa))))
F - Banned X
問題
- $0,1,2$ のみからなる長さ $N$ の数列であって、どの連続する部分列に対しても総和がちょうど $X$ にはならないようなものの個数を $\mod{998244353}$ で求めよ
- $1 \le N \le 3000$
解法
問題文がシンプル。こういうの好き（解けるとはいっていない）。
0は総和に影響しないので、後から挿入することで別に考えられる。「$1,2$ のみからなる長さ $1～N$ のそれぞれの個数」を求めればよい。
長さを $L$ に固定して、条件を満たす数列を考える。以下のいずれかの形となる。
- 総和が $X$ 未満
- $X$ が奇数で、全ての項が'2'
- 総和が $X$ より大きく、両端から一定数が'2'でうまいこと $X$ にならないもの（後述）
1つめは、$L$ 個中に $r$ 個'2'があるとすると ${}_{L}C_{r}$ 通りの並べ方があるので、$r$ を総和が $X$ 以上にならない範囲で全部計算して足せばよい。
2つめはあるとしても1個固定。
3つめは少し観察が必要だが、左端から足していくとどこかで $X-1$ になるタイミングがある。すると次は'2'しか置けない。
? ? ? ... ? 2 ...
~~~~~~X-1~~~~~~
~~~~~~X+1~~~~~~~~~
すると、左端は'1'だったらアウトなので、2しか置けない
1 ? ? ... ? 2 ...
~~~~~~ X ~~~~~~ アウト
2 ? ? ... ? 2 ...
~~~~~~X-1~~~~~~ OK
するとさらに右はまた2しか置けない
2 ? ? ... ? 2 2 ...
~~~~~~X+1~~~~~~~~~
これを繰り返すと、両端は数列が規定の長さ L に達するまで2しか置けなくなる
両端には同数の2が並ぶことになる
2 2 2 ? ... ? 2 2 2
この時、右側の'2'の左端直前までの和が、X-1に等しくなる
|-k個-|
2 2 2 ? ... ? 2 2 2
~~~~~和 X-1~~~~~~~
部分列の和が $X$ にならないように作ろうとするとこの条件を満たすしかなく、 逆にこのように作ったものは「? ? ?」の部分がどうなっていようと必ず部分列の和が $X$ にならないことがわかる。
「$k=$ 両端にいくつ'2'が連続しているか」を全通り試す。
真ん中の「? ? ?」の部分は長さ $L-2k$、総和 $X-1-2k$ なので、'1'と'2'だけを置いて成立するか、する場合'2'は何個か、がわかる。二項係数で求められる。
さて、ここまでの1～3つめの数列の条件は、微妙に重複する場合があるので、注意して除く必要がある。
- 長さ $L$ が、全て'2'にしても総和が $X$ に満たないくらい短かった場合
- 1つめと2つめが重複しうる。2つめを加算する条件に、総和が $X$ より大きいことを追加する
- 3つめの「? ? ?」の部分が、全て'2'を置いた場合に成立するような場合
- 2つめと3つめが重複する。3つめで、ちょうどそのようになる場合は数えないようにする
もう少しすっきりした分類の仕方があるかも知れないが、ひとまずこれで重複を除けた。
計算量は、二項係数の事前計算で $O(N^2)$、長さ $L$ を固定してその中で両端の'2'の個数を試すのに $O(N^2)$、あわせて $O(N^2)$ となる。
