日記: Codeforces Round #797 (Div. 3) A-FをPythonで解く

A. Print a Pedestal (Codeforces logo?)

mod 3で場合分けします。

$h3 < h2 < h1$であることが必要なので、$n$が3の倍数であるときある整数$k$に対して$k < k+1 < k+2$が($h1$が最小なものを探すという)条件を満たす最適な解です。$n$が3の倍数でない時を考えます。この時、余りのブロックを他に積まなければなりません。余りが1なら、$h2$あるいは$h3$を1つ高くすると条件を満たさないので、$k < k+1 < k+3$とするのが最適です。余りが2なら、$h1, h2$のみに積まないと条件を満たさないので$k < k+2 < k+3$とします。

時間計算量$O(1)$, 空間計算量$O(1)$です。

実装

```Python for _ in range(int(input())): n = int(input()) n -= 3 ans = [n//3] * 3 ans[0] += 1 ans[1] += 2 ans[2] += 0 n %= 3 if n == 0: pass elif n == 1: ans[1] += 1 elif n == 2: ans[0] += 1 ans[1] += 1 print(*ans) ```

B. Array Decrements

シミュレーションします。

もし、$b$が$a$から操作されたなら、最大の値になりうるindexは変わらないので、$d = max(a) - max(b)$を計算することで$a$を何回デクリメントしたか(の最小の数)が分かります。このため、新しい配列$c$を$c_i = max(a_i - d, 0)$とし、bと等しいかを判定します。
$d$が負の値の場合はNOです。デクリメントしかできないのに、$a$の最大値より大きな値が$b$に含まれていてはなりません。

時間計算量$O(N)$, Extraな空間計算量$O(N)$です。(配列$c$を作らずに、forで見ていけば$O(1)$です)

実装

```Python for _ in range(int(input())): n = int(input()) data = list(map(int, input().split())) datb = list(map(int, input().split())) d = max(data) - max(datb) if d < 0: print("NO") continue datc = list(map(lambda x: max(0, x - d), data)) if datb == datc: print("YES") else: print("NO") ```

C - Restoring the Duration of Tasks

シミュレーションします。

各タスクの到着順序が順番に並んでいることに注意します。タスク$i$の終了した時間$f_i$は自明なので、そのタスクをいつから開始したのかがポイントです。タスク$i$は前のタスクが終了してからしばらく後に届くこともあるので、終了時間 - max(そのタスクが到着した時間, 前のタスクが終わった時間)になります。

時間計算量$O(N)$, Extraな空間計算量$O(1)$です。

実装

```Python for _ in range(int(input())): n = int(input()) data = list(map(int, input().split())) datb = list(map(int, input().split())) ans = [datb[0] - data[0]] for i in range(1, n): ans.append(datb[i] - max(data[i], datb[i-1])) print(*ans) ```

D - Black and White Stripe

尺取り法をします。

題意より含まれる長さ$k$の区間のうち、wを最小個含むものを答えればよいです。最初に先頭から$k$文字に含まれるWの数を数えたのち、長さ$k$のまま右に1つずつシフトしてこれを求めます。

時間計算量$O(N)$, Extraな空間計算量$O(k)$です。

実装(尺取り)

```Python for _ in range(int(input())): n, k = map(int, input().split()) s = input() dat = [] for x in s: if x == "B": dat.append(1) else: dat.append(0) cur = 0 for i in range(k): if dat[i] == 0: cur += 1 ans = cur l = 0 r = k - 1 for _ in range(n - k): r += 1 if dat[r] == 0: cur += 1 if dat[l] == 0: cur -= 1 l += 1 ans = min(ans, cur) print(ans) ```

この動作はB=0, "W=1"として累積和でも解けます。
時間計算量$O(N)$, Extraな空間計算量$O(N)$です。

実装(累積和)

```Python for _ in range(int(input())): n, k = map(int, input().split()) s = input() dat = [0 if x == "B" else 1 for x in list(s)] cum = [0] for x in dat: cum.append(cum[-1] + x) ans = 1<<61 for i in range(n - k+1): ans = min(ans, cum[i+k] - cum[i]) print(ans) ```

E. Price Maximization

$a_i \mod k$に注目します。

今、 $ a_i \equiv c \mod k$, $ a_j \equiv d \mod k$, とすると、整数$x,y$を用いて$\lfloor \frac{a_i + a_j}{k}\rfloor = \lfloor \frac{kx + c + ky + d}{k}\rfloor = \lfloor \frac{k(x+y) + (c+d)}{k}\rfloor = \lfloor \frac{k(x+y)}{k}\rfloor + \lfloor \frac{(c+d)}{k}\rfloor = (x+y) + \frac{(c+d)}{k}\rfloor $と変形できます。
つまり、$c+d >= k$である$a_i$, $a_j$のペアを多く見つけられれば、各ペアごとに$+1$できるため答えを最大化できます。ここで、$c,d<k$より、$c+d//k<2$です。

このペアを多く見つけるのには、各要素の$\mod k$をソートして並べ、左右から貪欲に見ていけば良いです。その後、ペアに出来なかったすべてのペアを適当に処理します。

時間計算量$O(N)$, Extraな空間計算量$O(N)$です。

for _ in range(int(input())):
    n, k = map(int, input().split())
    dat = list(map(int, input().split()))
    buf = list(map(lambda x: x % k, dat))
    ans = 0
    from collections import defaultdict
    cnt = defaultdict(list)
    for i in range(n): cnt[buf[i]].append(dat[i])
    l = 0
    r = k - 1
    while l <= r:
        if len(cnt[l]) == 0: l += 1
        elif len(cnt[r]) == 0: r -= 1
        elif (l + r) < k:      l += 1
        else:
            if l == r and len(cnt[l]) == 1: break
            inda = cnt[l].pop()
            indb = cnt[r].pop()
            ans += (inda + indb) // k
    nokori = []
    for i in range(k):
        while len(cnt[i]) > 0: nokori.append(cnt[i].pop())
    for i in range(0, len(nokori), 2): ans += (nokori[i] + nokori[i+1]) // k
    print(ans)

F. Shifting String

サイクルに注目し、そのサイクル内が何回で戻るかに注目します。

0-indexedで説明します。まず、題意のような操作で順列は循環を持ちます。例えば、[2,0,1,3]という順列に対しては、[0->2->1->0->2->...]という長さ3の循環と[3->3->3->...]という長さ1の循環が存在します。
この問題について考えます。abcdについて、p=[2,0,1,3]のとき、k回の操作をk:と示して、0:abcd->1:cabd->2:bcad->3:abcdとなり、3回の操作で元に戻ることが分かります。

次に、abcdeと[2,0,1,4,3]を考えます。0:abcde->1:cabed->2:bcade->3:abced->4:cabde->5:bcaed->5:abcdeとなり、6回の操作で元に戻ることが分かりました。順列$p$に$m$個の循環があり、その長さが$l_m$だとするなら、それらのLCM(最小公倍数)回操作を繰り返すと、元の文字列に戻ると言えます。これは正しいのですが、求めたいのは最小の回数です。aaabbと[2,0,1,4,3]を考えます。この時、何回の操作をしてもaaabbのままで解は$1$となります。例えばabab, [1,2,3,0]はabab -> babaで2回で元に戻ります。

いま、各循環を構成するindexの文字だけを順番に取り出すことを考えます。abcdeと[2,0,1,4,3]の例の１つ目の循環を考えると、[0-2->1]なのでacbとなります。$0,2,1$にいる文字はa,c,bで、操作を1回行うと、左に1つシフトし、c,b,aになることになります。
言い換えれば、文字列$s$が文字$c_0, c_1, c_2...c_m$であったとき、$l$回の操作をすると、$c_{(0+l\mod m)}, c_{(1+l\mod m)}, c_{(2+l\mod m)}$になります。求めたいのは、$c_0 = c_{(0+l\mod m)}$, $c_1 = c_{(1+l\mod m)}$, ... , $c_m = c_{(m+l\mod m)}$となるような最小の$l(>0)$です。

これは、次の問題と同値です。

長さ$n$の文字列$s$がある。この$s$を2つつなげた文字列$t$があるとき、すべての$i(0<i<=n))$に対して、$s[i] = t[k+i]$であるような$1$以上の最小の$k$を求めよ。
例: aaa の場合、aaaaaaに含まれるaaaはaaaaaaでk=1
例: abab の場合、ababababに含まれるababはababababでk=2
例: abc の場合、abcabcに含まれるabcはabcabcでk=3

これは、1(0indexed)文字目以降に求められるLCP(最長共通接頭辞)がn以上の長さををZ-Algorithmで求めておいたり、$n$文字のハッシュをローリングハッシュを使って区間のハッシュを高速に求められるようにしておくことで高速に求められます。

時間計算量$O(N)$, Extraな空間計算量$O(N)$です。

実装(Z-Algorithm)

class zAlgorithm():
    def __init__(self, s):
        self.sdat = list(map(lambda x: ord(x), s))
        self.sl = len(s)
        self.res = [0] * self.sl
        self.res[0] = self.sl
        i, j = 1, 0
        while i < self.sl:
            while (i + j) < self.sl:
                if self.sdat[j] != self.sdat[i + j]:
                    break
                j += 1
            self.res[i] = j
            if (j == 0):
                i += 1
                continue
            k = 1
            while (i + k) < self.sl and (k + self.res[k] < j):
                self.res[i + k] = self.res[k]
                k += 1
            i += k
            j -= k

def do():
    import math
    def lcm(x, y): return (x * y) // math.gcd(x, y)
    n = int(input())
    s = input()
    dat = list(map(int, input().split()))
    for i in range(len(dat)): dat[i] -= 1
    visited = [False] * n
    cycles = []
    ans = 1
    for i in range(n):
        if visited[i]: continue
        route = []
        cur = i
        while visited[cur] is False:
            visited[cur] = True
            route.append( s[cur])
            cur = dat[cur]
        instr = "".join(route * 2)
        zres = zAlgorithm(instr)
        ind = 1
        while zres.res[ind] < len(route): ind += 1
        ans = lcm(ans, ind)
    print(ans)

# n questions
q = int(input())
for _ in range(q):
    do()

aaa

実装(ローリングハッシュ)

```Python

Mersenne 2^61

2^61 - 1

Original C++: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6

Verify: https://atcoder.jp/contests/abc141/submissions/me

"""
rollingHash61
init(s) O(N)でハッシュを取る
calc hash [l, r) r = OPEN
"""

class rollingHash61():
MOD = (1 << 61) - 1
BASE = 20200213
MASK30 = (1 << 30) - 1
MASK31 = (1 << 31) - 1
hashTable = []
pow = []
slen = -1
sdat = []

def __init__(self, s: str):
    self.sdat = list(map(lambda x: ord(x), s))
    self.slen = len(s)
    self.hashTable = [0] * (self.slen + 1)
    self.pow = [1] * (self.slen + 1)
    for i in range(self.slen):
        self.hashTable[i + 1] = self.multi(self.hashTable[i], self.BASE)
        self.hashTable[i + 1] += self.xorshift(self.sdat[i] + 1)
        self.pow[i + 1] = self.multi(self.pow[i], self.BASE)
        self.hashTable[i + 1] = (self.hashTable[i + 1] - self.MOD) if (self.hashTable[i + 1] >= self.MOD) else \
        self.hashTable[i + 1]

def hash(self, l, r):
    # calc hash [l, r)  r = OPEN
    res = self.MOD + self.hashTable[r] - self.multi(self.hashTable[l], self.pow[r - l])
    return res if (res < self.MOD) else (res - self.MOD)

def mod(self, x):
    res = (x >> 61) + (x & self.MOD)
    return res - self.MOD if res >= self.MOD else res

def multi(self, x, y):
    xu, xd = x >> 31, x & self.MASK31
    yu, yd = y >> 31, y & self.MASK31
    m = xd * yu + xu * yd
    mu = m >> 30
    md = m & self.MASK30
    return self.mod(xu * yu * 2 + mu + (md << 31) + xd * yd)

def xorshift(self, x):
    return x ^ (x << 13) ^ (x >> 17) ^ (x << 5)

def do():
import math
def lcm(x, y): return (x * y) // math.gcd(x, y)
n = int(input())
s = input()
dat = list(map(int, input().split()))
for i in range(len(dat)): dat[i] -= 1
visited = [False] * n
cycles = []
ans = 1
for i in range(n):
if visited[i]: continue
route = []
cur = i
while visited[cur] is False:
visited[cur] = True
route.append( s[cur])
cur = dat[cur]
instr = "".join(route * 2)
rh = rollingHash61(instr)
ind = 1
while rh.hash(0, len(route)) != rh.hash(0+ind, len(route)+ind): ind += 1
ans = lcm(ans, ind)
print(ans)

n questions

q = int(input())
for _ in range(q):
do()

</div></details>
https://codeforces.com/contest/1690/submission/159943612