Tenka1 Programmer Contest 2019 C,D,E 問題メモ

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} + \ldots + 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} + \ldots$
    • $a_2 + a_{p+1} + a_{2p} + \ldots$
    • $a_3 + a_{p+2} + a_{2p+1} + \ldots$
    • $a_{p-1} + a_{2p-2} + a_{3p-3} + \ldots$

$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))))

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2019/0420_tenka1_2019.txt · 最終更新: 2019/04/26 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0