今日の精進(20191227)

2日目。続いていくと良いな…

GCD on Blackboard

昨日のいもす法からGCDが気になっていたのでやった。両端からGCDして作った2つの配列をGCDして最大を取る。

# coding: utf-8  
from fractions import gcd  
N = int(input())  
A = list(map(int, input().split()))  
l1 = [0] * N  
l2 = [0] * N  
# 前からなのでi-1  
for i in range(1, N):  
    l1[i] = gcd(l1[i-1], A[i-1])  
# 後ろからなのでi+1  
for i in range(N-1)[::-1]:  
    l2[i] = gcd(l2[i+1], A[i+1])  
ans = 0  
for i in range(N):  
    ans = max(ans, gcd(l1[i], l2[i]))  
print(ans)  

ドローン

上下左右の指示があり、?は指示が不明。?の数をカウントしておいて、原点からの距離が最大の場合の出力は$|x|+|y|+cnt$で良いが、最小の場合はできる限り$|x|$と$|y|$の値を減らして行く。原点についてもまだ?が残っている場合は偶奇で場合分け

# coding: utf-8  
S = input()  
T = int(input())  
x, y = 0, 0  
cnt = 0  
for i in range(len(S)):  
    if S[i] == "L":  
        x -= 1  
    elif S[i] == "R":  
        x += 1  
    elif S[i] == "U":  
        y += 1  
    elif S[i] == "D":  
        y -= 1  
    elif S[i] == "?":  
        cnt += 1  
if T == 1:  
    print(abs(x) + abs(y) + cnt)  
else:  
    while cnt > 0:  
        if x < 0:  
            x += 1  
            cnt -= 1  
        elif x > 0:  
            x -= 1  
            cnt -= 1  
        elif y < 0:  
            y += 1  
            cnt -= 1  
        elif y > 0:  
            y -= 1  
            cnt -= 1  
        else:  
            break  
    print(abs(x) + abs(y) + cnt % 2)  

乱数生成

すごい時間かかった…。
全探索すると制約的に間に合わない。奇数の配列の中央値なので、1つは入力の値Kで、もう1つだけ決めれば残りも決まってくるのでそのように計算する。
決める値をiとすると、

  • i < K
    • 数字が全部異なる場合(並べ方は6通り)
    • i以外の2つが同じ場合(並べ方は3通り)
  • i == K
    • iともう1つが同じ場合
      で場合分けして計算する。
# coding: utf-8  
N, K = map(int, input().split())  
ans = 0  
for i in range(1, N+1):  
    # 2つ違う(6通り)  
    if i < K:  
        # 全部違う  
        ans += (N - K) * 6  
        #i以外が同じ  
        ans += 3  
    # 2つかぶり(3通り)  
    elif i == K:  
        ans += (N - K) * 3  
# 全部かぶり(1通り)  
ans += 1  
print(ans / N**3)  

Splitting Pile

解説AC。これが解けないのはやばい。
誤読していて好きな数を取って良いもんだと思っていたが、配列のどこかに切れ目を入れて両方の和の最小値を出す問題だった。問題をちゃんと読もうね。左から一個ずつ引いてって差分が一番小さくなったやつを出力。切れ目iは必ず $0 < i < N -1$でないといけないことに注意。

# coding: utf-8  
N = int(input())  
A = list(map(int, input().split()))  
X = sum(A)  
ans = float("inf")  
x = 0  
for i in range(N):  
    x += A[i]  
    if i < N-1:  
        ans = min(ans, abs(X - 2 * x))  
print(ans)  

Connection and Disconnection

すごい間違えた。同じ文字しか続かない場合の場合分けを完全に間違えていた。
同じ文字しか続かない場合、答えは$|S|*K/2$となる。
それ以外の場合では、

  • 先頭と末尾が同じ場合、その出現回数はK-1
  • それ以外の出現回数はK
  • 連続する文字の数をカウントしておいて、2で割り切った数の和が答え

正しくできているわけでは無いと思うが一応ACできた…(解説にもっと良さそうなのがあった、つらい)

# coding: utf-8  
S = input()  
K = int(input())  
# 同じ文字しか無い場合 --> |S| * K // 2  
if len(list(set(S))) == 1:  
    print(len(S) * K // 2)  
    exit()  
# とりあえずSを2つ重ねて検査  
l = []  
SS = S * 2  
s = SS[0]  
cnt = 1  
for i in range(1, len(SS)):  
    if s != SS[i]:  
        l.append(cnt)  
        s = SS[i]  
        cnt = 1  
    else:  
        cnt += 1  
l.append(cnt)  
ans = 0  
## 先頭と末尾が同じ場合とそれ以外で場合分け  
if S[0] == S[-1]:  
    for i in range(len(l)//2 + 1):  
        if i == 0:  
            ans += l[i] // 2  
        # 先頭と末尾が重なるところはK-1回しか出現しない  
        elif i == len(l) // 2:  
            ans += l[i] // 2 * (K-1)  
        # 内部の同じ文字が続くところはK回出現する  
        else:  
            ans += l[i] // 2 * K  
    # 末尾を足す  
    ans += l[-1] // 2  
else:  
    # 内部しか同じ文字が続かない場合は上のelseの部分しか計算しなくて良い  
    for i in range(len(l)//2):  
        ans += l[i] // 2 * K  
print(ans)  

感想

今日は問題は少ないが難易度は自分に見合ったものだけ解いていた気がする(それでも8AC/dayくらいはせめてやっていきたいが)。2次元配列とグラフの問題を意識的に避けてしまっているので今後はこれらに取り組みたい…取り組みます。