Open8
Atcoderがんばるメモ
自力でやったやつ。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")
敗因
・入力受け取りにforを使っていること
・setを知らなかった
ある集合を作成した後、ある値が集合内に含まれるか調べたい時
Key in List # O(n) ただし、nはlistの要素数
Key in Set # O(1)
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))
絵に起こして考えたらただの組み合わせだと気づくことができた
自力⇨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)
- 絶対値のままだと厄介→工夫して外すことができないか考える。例えばソート
- iやjを整数値で固定してみると法則が見えるかもしれない
敗因
・計算量の求め方を間違えていた
N=10^9ならforを使う回数はおそらく気にしなくていい。forの中でfor使うとTLE
解答
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)