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

programming_algorithm/contest_history/atcoder/2020/0412_abc162.txt · 最終更新: 2020/04/12 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0