目次
AtCoder Beginner Contest 162 D～F問題メモ
D - RGB Triplets
問題
- R,G,Bの3種の文字からなる長さ $N$ の文字列 $S$ が与えられる
- 以下の条件を全て満たすindexの組 $(i,j,k)$ の個数を求めよ
- (1) $i \lt j \lt k$
- (2) $(S_i,S_j,S_k)$ は全て異なる（R,G,Bが1つずつ）
- (3) $j-i \neq k-j$ （間隔が異なる）
- $1 \le N \le 4000$
解法
まず、条件(3)が無ければ、答えは $S$ に含まれる（Rの個数）×（Gの個数）×（Bの個数）で求められる。
また、条件(3)の候補となるindexの組はたかだか $O(|S|^2)$ しかないので、全て調べられる。
間隔が同じ $i,j,k$ について、条件(1)(2)を満たしているものがあれば、答えから引けばよい。
from collections import Counter
n = int(input())
s = input()
cnt = Counter(s)
ans = cnt['R'] * cnt['G'] * cnt['B']
for i in range(n):
l = 1
si = s[i]
while i + l * 2 < n:
if si != s[i + l] and si != s[i + l * 2] and s[i + l] != s[i + l * 2]:
ans -= 1
l += 1
print(ans)
E - Sum of gcd of Tuples (Hard)
問題
- 各項が $1～K$ のいずれかの整数である長さ $N$ の数列は、$K^N$ 個ある
- 全てについて最大公約数を求め、その総和を求めよ
- $2 \le N \le 10^5$
- $1 \le K \le 10^5$
解法
こういうの苦手……に加え、実際の計算量と直感的な計算量が合わない。
数列のGCDが1以外の値（$g$ とする）を取るというのは、以下の2つを共に満たしているときである。
- 全ての項が $g$ の倍数
- 全ての項を $g$ で割ると、その数列のGCDは1
さらに全ての項を $g$ で割った時、そこに存在しうる数字は、$1～\dfrac{K}{g}$ のいずれかである。（切り捨て）
ということは、$K$ について以下のような関数を定義すれば、何となく再帰的に求められそう。
$f(k) = $ 各項が $1～k$ の長さ $N$ の数列で、GCDが1になるものの個数
答えは、$f(\dfrac{K}{1})+2f(\dfrac{K}{2})+3f(\dfrac{K}{3})+...+Kf(\dfrac{K}{K})$ となる。
また、個数の帳尻を合わせると $k^N = f(\dfrac{k}{1})+f(\dfrac{k}{2})+f(\dfrac{k}{3})+...+f(\dfrac{k}{k})$ となる。
つまり、$f(k) = k^N - f(\dfrac{k}{2}) - f(\dfrac{k}{3}) - ... - f(\dfrac{k}{k})$ で求められる。
ただし、$f(1)=1$ とする。
さて、$\dfrac{k}{2},...,\dfrac{k}{k}$ だが、$k$ が大きくなるにつれ同じ値が相当数含まれる。特に、$\dfrac{k}{k/2}$ 以降に関しては必ず1となる。
K=14
割る数 1 2 3 4 5 6 7 8 9 10 11 12 13 14
14 7 4 3 2 2 2 1 1 1 1 1 1 1
なので、一度求めた $f(k)$ についてはメモ化しておくことで、$f(k)$ を再帰的に求めていっても、そこまで大した計算量にならないで済む。
具体的には、最大ケース $N=10^5,K=10^5$ で、下記get()が呼ばれるのが390754回、さらにその中でcntに存在せずに具体的な計算に進むのが630回。
def solve(n, k):
if k == 1:
return 1
MOD = 10 ** 9 + 7
ans = (k // 2 + 1 + k) * (k - k // 2) // 2 % MOD # k/2～k の和
cnt = {1: 1}
def get(d):
if d in cnt:
return cnt[d]
result = pow(d, n, MOD)
result -= d - d // 2
for i in range(2, d // 2 + 1):
result -= get(d // i)
result %= MOD
cnt[d] = result
return result
for i in range(1, k // 2 + 1):
ans += i * get(k // i)
ans %= MOD
return ans
n, k = map(int, input().split())
print(solve(n, k))
F - Select Half
問題
- 長さ $N$ の整数列 $A_1,...,A_N$ が与えられる
- この中から、ちょうど $\dfrac{N}{2}$（切り捨て）個の整数を、どの2個も連続しないように選ぶ
- 選んだ要素の和としてあり得る最大値を求めよ
- $2 \le N \le 2 \times 10^5$
- $|A_i| \le 10^9$
解法
偶数の時は簡単。
先頭から1つおきに取っていき、どこかで2つ間を空け、そこからまた1つおきに取っていく、という方法しかない。（先頭、末尾の長さが0の場合も含める）
3 1 4 1 5 9 2 6 ~ ~ ~ ~
「先頭から1つおき」「末尾から1つおき」に取ったときの累積和を求めておき、切り替える箇所を全探索すればよい。
3 1 4 1 5 9 2 6
先頭から 0 3 7 12 14
末尾から 17 16 15 6 0
↓
0 3 7 12 14
+ 17 16 15 6 0
--------------------
17 19 22 18 14 → 最大値は22
奇数の時が困る。
たとえば $N=11$ なら5個だけ選べばよいので、間を2つ空けてよい場所が2つ（または間を3つ空けてよい場所が1つ）ある。
3 1 4 1 5 9 2 6 5 3 5 ~ ~ ~ ~ ~
間を空ける場所全探索は、$O(N^2)$ かかるので厳しそう。DPで解けないか考える。
ここで、問題の条件は「取らない数を最小化する」ことでも達成できる。よって、問題を以下のように言い換える。
- $A_1,...,A_N$ から、$\dfrac{N}{2}$（切り上げ）個取った総和を最小化する
- 2つ以上連続して取らないことはできない
- 直前に取った状態で連続して取ることができるのは、2回まで
- 初期状態は「直前に取った状態」であるとする
こうすると、以下のDPで求めることができる。2つ以上連続で取らないことが無いので、2つ前までの状態があればよく、多少、遷移もわかりやすくなる。
- $DP[i][j] = A_i$ まで考えて、$A_i$ は取り、あと連続して取ることができる残り回数が $j$ 回の時の総和の最小値
- 初期条件（$i$ は0-indexとして）
- $DP[-2] = [INF, INF, INF]$
- $DP[-1] = [INF, INF, 0]$
INFは、その条件が不可能なことを示す。
- 遷移
- $DP[i][2] = \min(INF, DP[i-2][2] + A_i)$
- $DP[i][1] = \min(INF, DP[i-2][1] + A_i, DP[i-1][2] + A_i)$
- $DP[i][0] = \min(INF, DP[i-2][0] + A_i, DP[i-1][1] + A_i)$
各遷移、INFの次は1個空けて取る操作、その次は連続して取る操作を示す。
最終的に、$DP[N-1][1]$ または $DP[N-2][0]$ の小さい方が答えとなる。（$DP[N-2][2]$ は取る数が足りてない）
3 1 4 1 5 9 2 6 5 3 5
j 0 - - - 4 - 5 - 14 - 15 - 17 - ←┬ 17,19の小さい方が答え
1 - - 3 - 5 - 7 - 9 - 14 - 19 ←┘
2 - 0 - 1 - 2 - 11 - 17 - 20 -
各遷移のイメージ
x → min(x,y)+Ai
- y ↗
元の問題の答えは、$A_1～A_N$ の総和から、言い換えた問題の答えを引くことで求められる。
from itertools import accumulate
def solve_odd(n, aaa):
INF = 10 ** 18
p0, p1, p2, a0, a1, a2 = INF, INF, INF, INF, INF, 0
for a in aaa:
n2 = min(INF, p2 + a)
n1 = min(INF, a2 + a, p1 + a)
n0 = min(INF, a1 + a, p0 + a)
p0, p1, p2, a0, a1, a2 = a0, a1, a2, n0, n1, n2
return sum(aaa) - min(p0, a1)
def solve_even(n, aaa):
fwd = [0] + list(accumulate(aaa[::2]))
bwd = [0] + list(accumulate(aaa[::-2]))
bwd.reverse()
return max(f + b for f, b in zip(fwd, bwd))
n = int(input())
aaa = list(map(int, input().split()))
if n % 2 == 0:
print(solve_even(n, aaa))
else:
print(solve_odd(n, aaa))
