今日の精進(20191226)

はじめに

なるべく精進した結果を残すことにした。がんばります。

今日はCafeCoderのTeabreak 003からやった

A. Hop Step Jump!

1,2,4,5,6,8,...と続く数列に入力Nが含まれるかという問題。$ a_n = 4n - 1 $ が数列に含まれないような数列なので、これに当てはまるようであれば含まれない、そうでなければもとの数列に含まれる。

# coding: utf-8  
N = int(input())  
if (N + 1)//4 == (N + 1)/4:  
    print("No")  
else:  
    print("Yes")  

B. Sound!

必要な配列Aをまずソートして、先頭と末尾から初期値Kまでの距離の和

# coding: utf-8  
N, K = map(int, input().split())  
A = list(map(int, input().split()))  
A.sort()  
# idx = A.index(K)  
ans = 0  
if A[0] < K:  
    ans += K - A[0]  
if A[-1] > K:  
    ans += A[-1] - K  
print(ans)  

C. GoodTriangle

面積が0になっても整数としてカウントされてしまうので、これを回避するよう気をつける。制約が$3 <= n <= 10^2 * 2$だったので全探索で行けると思って最初無駄な計算を繰り返してしまってTLE。真面目に書いたらAC

# coding: utf-8  
def S(a,b,c,d,e,f):  
    return abs((c-a)*(f-b) - (d-b)*(e-a))  

N = int(input())  
ll = []  
for _ in range(N):  
    tmp = list(map(int, input().split()))  
    ll.append(tmp[:])  
ans = 0  
for i in range(N-2):  
    a, b = ll[i]  
    for j in range(i+1, N-1):  
        c, d = ll[j]  
        for k in range(j+1, N):  
            e, f = ll[k]  
            area = S(a,b,c,d,e,f)  
            if area % 2 == 0 and area > 0:  
                ans += 1  
print(ans)  

D. Breaker

円形のテーブルを一周するのにかかる最小回数を答える。移動するマスの数は最大2000なので、すべてのパターンをシミュレートしてもなんとか間に合う。入力される各マスの値は配列だが問題は円形なので、とりあえずマスの配列Aを2つ重ねる必要がある。

# coding: utf-8  
N = int(input())  
A = list(map(int, input().split()))  
A = A * 2  
ans = 10**6  
for i in range(N):  
    start = A[i]  
    cnt = 0  
    s_idx = i  
    idx = i  
    while True:  
        idx = idx + min(N, A[idx])  
        cnt += 1  
        if idx >= s_idx + N:  
            break  
    ans = min(ans, cnt)  
print(ans)  

E. Cafe Road

原点からの各座標の傾きを求めて、数が一番多い傾きのグループの数を出力する。傾きは$m = \frac{y}{x}$で求められるが、$x=0$のときにエラーを吐くのでそれは別にしておく。pythonでは辞書が使えるのでそれを使った。辞書の速さとかをよく知らないので間に合うか不安だったが、やってみたら全然余裕だった。

# coding: utf-8  
N = int(input())  
cafe = {}  
for i in range(N):  
    x, y = map(int, input().split())  
    if x == 0:  
        grad = "dbz"  
    else:  
        grad = y / x  
    if grad not in cafe.keys():  
        cafe[grad] = 1  
    else:  
        cafe[grad] += 1  
print(max(cafe.values()))  

次からはAtcoderの問題

X: Yet Another Die Game

サイコロの出てほしい目は5と6なので、11 で割って2倍すればいい。
問題は11で割った余りの部分で、余り0、 >=7、 <= 6で場合分けする。

  • 余り0の場合、11で割り切れるということなので入力を11で割って2倍
  • 余りが6以下の場合、+1
  • 余りが7以上の場合、+2
    ここらの場合分けがうまく行かずに何回かWAを出してしまった。
    # coding: utf-8  
    X = int(input())  
    if X <= 6:  
      print(1)  
    else:  
      mod = X % 11  
      if mod >= 7:  
          print(X // 11 * 2 + 2)  
      elif mod == 0:  
          print(X // 11 * 2)  
      else:  
          print(X // 11 * 2 + 1)  

Knot Puzzle

長さL以上の2つのロープの隣り合う組み合わせがあれば、その2つの間の結び目を最後に解くようにしたら必ず結び目が全部解ける。L以上になる組み合わせが無い場合は最後の1つの結び目がどうしても解けないのでImpossible

# coding: utf-8  
N, L = map(int, input().split())  
A = list(map(int, input().split()))  
# Lより小さい組み合わせしか無い場合おわり  
flag = False  
for i in range(N-1):  
    if A[i] + A[i+1] >= L:  
        importance_i = i  
        flag = True  
        break  
if not flag:  
    print("Impossible")  
    exit()  

l, r = 0, N-1  
print("Possible")  
ans = []  
while r - l > 1:  
    # print(l, r)  
    if l < importance_i:  
        ans.append(l+1)  
        l += 1  
    if r > importance_i+1:  
        ans.append(r)  
        r -= 1  
# print("importance_i", importance_i)  
ans.append(importance_i+1)  
print(*ans, sep="\n")  

AtColor

いもす法をつかう。と言いつついもす法よくわかっていないですが…(累積和の強い版?)。
まず制約分の配列L(すべて0)を用意しておいて、与えられる範囲[a,b]のL[a]に+1、L[b+1]に-1します。この配列を使って累積和をとることで、答えを求められる。すごい。

# coding: utf-8  
N = int(input())  
l1 = [0] * (10 ** 6 + 2)  
for _ in range(N):  
    a, b = map(int, input().split())  
    l1[a] += 1  
    l1[b+1] -= 1  
# ans = 0  
for i in range(1, len(l1)-1):  
    l1[i] += l1[i-1]  
    # ans = max(ans, l1[i])  
# print(ans)  
print(max(l1))  

感想

なんだかんだ解いたが、わからない問題は結構解説見てしまったので辛い。特にBreakerとかは自力ACできるようになりたい。