AtCoder Beginner Contest 150

今回まだunratedになった。

C - Count Order

直接にitertools.permutationsを利用する。

from itertools import permutations as perm
import sys
readline = sys.stdin.buffer.readline

n = int(readline())
p = tuple(map(int, readline().split()))
q = tuple(map(int, readline().split()))

p_lst = list(perm(list(range(1, n + 1)), n))  # 排列を生成する。辞書順整理済み
pn = qn = 0
for i, j in enumerate(p_lst, 1):
    if p == j:
        pn = i
    if q == j:
        qn = i
    if pn * qn != 0:
        print(abs(pn - qn))
        quit()

D - Semi Common Multiple

import sys
read = sys.stdin.buffer.read
from fractions import gcd
from functools import reduce

n, m, *alst = map(int, read().split())
mm = 2 * m  # 2Xはaiの奇数倍


def lcm(x, y):
    g = gcd(x, y)
    if x // g % 2 == 0 or y // g % 2 == 0:
    # 両方の余りが同時1でないとlcmがどちらかの偶数倍になる
        print(0)
        quit()
    g = x * y // g
    if g > mm:
        print(0)
        quit()
    return g


g = reduce(lcm, alst)
res = (mm // g)
print(res // 2 + res % 2)

E - Change a Little Bit

C列が整理済みとする。(C1<=C2<=C3...)
規則を見つけてみる。

n=1, 0	C1
1	1
合計	1

n=2, 00	C1	C2
01	0	1
10	1	0
11	2	1
合計	3	2

n=3, 000	C1	C2	C3
001	0	0	1
010	0	1	0
100	1	0	0
011	0	2	1
101	2	0	1
110	2	1	0
111	3	2	1
合計	8	6	4

n=4, 0000	C1	C2	C3	C4
...	...	...	...	...
合計	20	16	12	8

よって規則は、
$\quad 2^{n}* {\sum_1^n} C_i*(n+2-i)*2^{n-2}$

$ = 4^{n-1}* {\sum_1^n} C_i*(n+2-i)$
(n=1時も満足する)

import sys
read = sys.stdin.buffer.read

mod = 10**9 + 7
n, *clst = map(int, read().split())
clst.sort()
res = sum((n + 2 - i) * item for i, item in enumerate(clst, 1))
print((4**(n - 1) * res) % mod)

F - Xor Shift

自分のKMPが全然間に合わなかったからZ-functionを勉強した。
Z-function and its calculation

import sys
read = sys.stdin.buffer.read

n, *lst = map(int, read().split())
al = lst[:n]
bl = lst[n:]


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


a = convert(al)
b = convert(bl)


def Z_algorithm(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = z[i - l] if z[i - l] < r - i else r - i - 1
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z


Z = Z_algorithm(b + [-1] + a + a)[n + 1:n + n + 1]

K = [i for i, x in enumerate(Z) if x == n]
X = [al[k] ^ bl[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))

コードはともかく、重要なのはZ-functionの理解です。