Summer Festival Contest 2018 (Division 2)

Summer Festival Contest 2018 (Division 2) - AtCoder

A - 夏祭り会議 (Summer Festival Meeting)

• 2番目以降3数の和はゼロに保たれる x[k] + y[k] + z[k] = 0 for k >= 2
• この式を使うと、if K>=2: x[k+2] = 0 ==> x[k] == 0が成立することが示せる。
• 制約よりi=1は解にならない

X,Y,Z = map(int,input().split())
x2=Y-Z
y2=Z-X
z2=X-Y
if x2*y2*z2==0:
    print(2)
else:
    x3=y2-z2
    y3=z2-x2
    z3=x2-y2
    if x3*y3*z3==0:
        print(3)
    else:
        print(-1)

1 2 3
3

B - 太鼓の名人 (Taiko Expert)

• 最後のDの位置xと最初のKの位置yを比べればよい
• x>yならば0でx<yのときxとyの間にある?の数をzとするとz=y-x-1
• zのなかにDが何個あるかで場合分け出来るのでans = z+1
• 結局ans = y-x

L = int(input())
S=input()

x = -1
y = L
for i in range(L):
    if S[i] == "D":
        x = i
    if S[i] == "K" and y == L:
        y = i
if x > y:
    ans = 0
else:
    ans = y-x
print(ans)

C - 整数占い (Uranai Integer)

• f(x,y) = 2 + xy + 2x + 2yが結合律を満たす
• 同様に交換法則も満たす
• よって最終結果は順序によらないので1通り計算すればよい
• fにmodをつけても同じことがいえる

import Control.Applicative
main = do
    getLine
    a <- map read . words <$> getLine
    print $ solve a
modulo = 10^9 + 7 :: Integer
solve :: [Integer] -> Integer
solve = foldl1 (\x y->mod (2+x*y+2*x+2*y) modulo)

E - 石積み (Pyramid Piling)

• 実験する！
• 各次元について題意を満たす最小のsの組を全探索で求めてみる
• 実験コード↓

S=55
a = [i for i in range(1,S+1)]
print(a)
b=[]
b.append(a)

N=15
for i in range(1,N):
    x = 0
    b.append([0 for _ in range(S)])
    for j in range(S):
        x += b[i-1][j]
        b[i][j] = x
    #print(b[i])
ans=[]
left=[]
right=[]
for k in range(N-1):
    flag = False
    for i in range(S):
        if flag:
            break
        for j in range(S):
            if flag:
                break
            if b[k][i] == b[k+1][j] and i*j !=0:
                print(k+1,i+1,j+1,b[k][i])
                ans.append(b[k][i])
                left.append(i+1)
                right.append(j+1)
                flag = True
print(left)
print(right)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55]
1 3 2 3
2 4 3 10
3 5 4 35
4 6 5 126
5 7 6 462
6 8 7 1716
7 9 8 6435
8 10 9 24310
9 11 10 92378
10 12 11 352716
11 13 12 1352078
12 14 13 5200300
13 15 14 20058300
14 16 15 77558760
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

これによりたぶん次のコードで通るであろうことがわかる。

N=int(input())
print(N,N+1)