Open8

Atcoderがんばるメモ

cryptoboxcryptobox

https://atcoder.jp/contests/abc187/tasks/abc187_c
自力でやったやつ。WAかつTLE

from sys import stdin
import sys

n = int(input())
s_list = []
for _ in range(n):
  s = stdin.readline()[:-2]
  s_list.append(s)

for i in s_list:
  if i in s_list and "!" + i in s_list:
    print(i)
    sys.exit()
print("satisfiable")

回答例

N = int(input())
S = set(input() for i in range(N))
for s in S:
    if "!" + s in S:
        print(s)
        exit()
print("satisfiable")
cryptoboxcryptobox

https://atcoder.jp/contests/abc185/tasks/abc185_c

from math import factorial

L = int(input())

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

print(combinations_count(L-1,11))

絵に起こして考えたらただの組み合わせだと気づくことができた

cryptoboxcryptobox

https://atcoder.jp/contests/abc186/tasks/abc186_d
自力⇨TLE

import itertools

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

ans = 0
for i in itertools.combinations(A, 2):
  ans += abs(i[0]-i[1])
print(ans)

解答

import itertools

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

A = sorted(A)
S = 0
ans = 0
for i in range(0, N):
  ans += i * A[i] - S
  S += A[i]
print(ans)
cryptoboxcryptobox

https://atcoder.jp/contests/abc185/tasks/abc185_d

敗因
・計算量の求め方を間違えていた
N=10^9ならforを使う回数はおそらく気にしなくていい。forの中でfor使うとTLE
https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0

解答

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

A = sorted(A)

#番兵追加
A.insert(0, 0)
A.append(N+1)

ans = 0
white_box = []
for i in range(M+1):
  box_length = A[i+1]-A[i]-1
  if (box_length != 0):
    white_box.append(box_length)

try:
  k = min(white_box)
except ValueError:
  print(ans)
  exit()

for j in white_box:
  ans += -(-j // k)
print(ans)