yukicoder contest 253 参戦記

A 1081 和の和

結論的に ∑^N_{i=1 N-1}C_i-1A_i になる. N≤100 なのでパスカルの三角形でも解けるだろうけど、めんどくさいのでいつもの mcomb を貼った.

N = int(input())
A = list(map(int, input().split()))

m = 1000000007

fac = [0] * N
fac[0] = 1
for i in range(N - 1):
    fac[i + 1] = fac[i] * (i + 1) % m


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


result = 0
for i in range(N):
    result += mcomb(N - 1, i) * A[i]
    result %= m
print(result)

追記: パスカルの三角形版.

N = int(input())
A = list(map(int, input().split()))

m = 1000000007

c = [[0] * N for _ in range(N)]
c[0][0] = 1
for i in range(1, N):
    c[i][0] = 1
    for j in range(1, i + 1):
        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m

result = 0
for i in range(N):
    result += c[N - 1][i] * A[i]
    result %= m
print(result)

追々記: 想定解らしき、素直にシミュレートする版.

N = int(input())
A = list(map(int, input().split()))

m = 1000000007

t = A[:]
for _ in range(N - 1):
    t = [(t[i] + t[i + 1]) % m for i in range(len(t) - 1)]
print(t[0])

B 1082 XORのXOR

並べ替えた A_i を元にすると、X = A₁ xor A₂ xor A₂ xor A₃ xor ... xor A_{N - 1} xor A_{N - 1} xor A_N となる. A₁ xor A₁ = 1 なので、X = A₁ xor A_N となる. 結果として任意の i != j の i, j について A_i xor A_j の最大値が答えとなる.

N = int(input())
A = list(map(int, input().split()))

result = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        result = max(result, A[i] ^ A[j])
print(result)

C 1083 余りの余り

K を i で割ったとして、j > i である j については K % i % j = K % i である. なので A を大きい順にソートして、A_N で割るまでの総当りをすれば良い. 前進するだけなので計算量は O(2^N) となり解ける.

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)


def f(k, i):
    if i == N:
        return k
    result = -1
    for j in range(i, N):
        result = max(result, f(k % A[j], j + 1))
    return result


print(f(K, 0))

追記: 想定解らしき、O(N2^N-1) のビット全探索版. ただ結局のところ気づかないといけないことは同じなようなので、そうしたら上の解法にたどり着かんか???

from itertools import product

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

result = 0
for p in product([True, False], repeat=N - 1):
    t = K
    for i in range(N - 1):
        if p[i]:
            t %= A[i]
    t %= A[N - 1]
    result = max(result, t)
print(result)

D 1084 積の積

結構いいところまで行っていた(テストケースの3/4がAC)が、解けずに終了.

f(l,r) が 10⁹ 以上とならない l, r を求めるのは尺取り法を使うというのはすぐ分かる. f(l,r) が 10⁹ 未満のとき、l≤x≤r である x について f(x,r) も当然 10⁹ 未満だが、これをループで解に畳み込んでいくと、最大 N=10⁵ の O(N²) になってしまうので TLE 必至. つまり、尺取り法のアキュムレータとは別にもう一つアキュムレータが必要となる.

例として、1,2,3 に4を追加することを考える. もう一つのアキュムレータを b とおくと4を追加する前は b=(1×2×3)×(2×3)×(3) となる. これを b=(1×2×3×4)×(2×3×4)×(3×4)×(4) に変えることになる. つまり変更操作は b=b×4⁴ となる. 要するに「追加する数^{追加後の尺取りの長さ}」を掛けることになる.

次に左端の1を削除することを考える. これは b=(1×2×3×4)×(2×3×4)×(3×4)×(4) を b=(2×3×4)×(3×4)×(4) に変更する操作で、1×2×3×4 を無くす操作となる. ちょうど尺取り法のアキュムレータが 1×2×3×4 で一致しているので、尺取り法のアキュムレータで割ればいい. といっても 10⁹+7 で割った余りなのでフェルマーの小定理を使うことになる. 尺取り法のアキュムレータを a とすると b=b×a^109+7-2 となる.

以上が分かっていれば、O(logN) の冪乗関数を使って、O(NlogN) で解が求めれる.

N = int(input())
A = list(map(int, input().split()))

m = 1000000007
l = 0
a = 1
b = 1
result = 1
for r in range(N):
    a *= A[r]
    b *= pow(A[r], r - l + 1, m)
    b %= m
    while a >= 1000000000:
        b *= pow(a, m - 2, m)
        a //= A[l]
        l += 1
    result *= b
    result %= m
print(result)

E 1085 桁和の桁和

まったく着手できず.

桁和の桁和が0になるのは全ての桁が0のときだけ. 9で余りを取ってしまうと0が発生してしまうが、9を超えたら9を引くようにすればその問題が回避できる. あとは一桁づつ DP で処理すればいい.

T = input()
D = int(input())

m = 1000000007


def update(t, nt, v):
    for i in range(10):
        ni = i + v
        if ni > 9:
            ni -= 9
        nt[ni] += t[i]
        nt[ni] %= m


t = [0] * 10
t[0] = 1
for c in T:
    nt = [0] * 10
    if c != '?':
        update(t, nt, int(c))
    else:
        for i in range(10):
            update(t, nt, i)
    t = nt
print(t[D])