#目次
1~10
11~20
21~30
31~40
41~50
51~60
61~70
71~80
81~90
91~100 ← 今ココ
#91. ABC145 C - Average Length
Difficulty:297
実際に$\ N!\ $通りの全ての経路の長さの合計を求めて$\ N!\ $で割る。
import itertools
import math
n = int(input())
m = math.factorial(n)
l = [list(map(int,input().split())) for i in range(n)]
x,y = [list(i) for i in zip(*l)]
z = list(range(n))
z = list(itertools.permutations(z))
ans = 0
for i in range(m):
for j in range(n - 1):
ans += math.sqrt((x[z[i][j]]-x[z[i][j+1]])**2 + (y[z[i][j]]-y[z[i][j+1]])**2)
print(ans / m)
Difficulty:304
どんな順に取り除いても 0 と 1 がそれぞれ 1 個以上あれば消すことができる。
消せないのは 0 のみ残る、 1 のみ残る場合なので、 0 と 1 のうち数が少ない方を$\ N\ $とし、$\ N \times 2\ $で取り除ける個数が分かる。
s = list(input())
p = s.count('0')
q = s.count('1')
print(2 * min(p,q))
#93. DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 B - Iron Bar Cutting
Difficulty:303
1 ミリ増やすか減らすか、どちらにしても 1 円ずつかかるならなるべく回数を減らしたい。
最初に全体の長さを計算し、$\ 0+A_1+A_2 \dots\ $と$\ sum(A)-A_1-A_2 \dots\ $の差を毎回比較すれば、操作すべき回数が分かる。
その中で差が一番小さい部分を操作すれば、費用が最低限になる。
n = int(input())
a = list(map(int, input().split()))
ans = 10 ** 16
a_1 = 0
a_2 = sum(a)
for i in range(n - 1):
a_1 += a[i]
a_2 -= a[i]
ans = min(ans, abs(a_1 - a_2))
print(ans)
Difficulty:300
組み合わせ自体は 8 通りと少なく、全通り試す。
$\ 0 \le i \le 7\ $の間で$\ i\ $を別の変数に代入し、$\ i \mod 2=0\ $なら + 、違うなら - を$\ A\ $と$\ B\ $の間に入れる。
その後$\ \lfloor i/2 \rfloor\ $で減らし、これを$\ B,C,D\ $間にも行うので合計 3 回行うことになる。
この操作は 2 進数を参考にしている。
$\ 7=0b111\ $ となり、 1 番右の数字が 0 なら + 、 1 なら - とし、1 ビット右にシフトさせている。
s = list(input())
a = int(s[0])
b = int(s[1])
c = int(s[2])
d = int(s[3])
def p_mark(j):
if j % 2 == 0:
return '+'
else:
return '-'
for i in range(2 ** 3):
j = i
p = a
x = p_mark(j)
if x == '+':
p += b
else:
p -= b
j = j // 2
y = p_mark(j)
if y == '+':
p += c
else:
p -= c
j = j // 2
z = p_mark(j)
if z == '+':
p += d
else:
p -= d
if p == 7:
print(str(a) + x + str(b) + y + str(c) + z + str(d) + '=7')
break
Difficulty:301
全ての数を揃えたいが、操作はどちらも 2 増やすことになるので、$\ 2,3,3\ $のような差が 1 の場合は$\ 4,3,3\ $、$\ 4,4,4\ $と 2 回操作することで揃えられる。
逆に$\ 2,4,4\ $のような差が 2 の場合は 1 回で揃えられる。
操作を繰り返せば最終的に差が 1 か 2 、つまり奇数か偶数になるので、$\ \max(A,B,C)=S\ $とのそれぞれの差$\ 3S-(A+B+C)=N\ $を求める。
$\ N \mod 2=0\ $なら$\ N/2\ $、$\ N \mod 2=1\ $なら最終的に全て 1 ずつ増えるので$\ (N+3)/2$で操作する回数が求められる。
a,b,c = map(int,input().split())
z = max(a,b,c)
x = 3 * z - (a + b + c)
if x % 2 != 0:
x += 3
print(x // 2)
#96. CODE FESTIVAL 2017 qual C B - Similar Arrays
Difficulty:322
似ているの条件から$\ A_i\ $には$\ A_{i-1},A_i,A_{i+1}\ $ の 3 通り似ている数字がある。
3 通りを$\ N\ $回選ぶので$\ 3 \times N\ $通りあり、この中から偶数になるものを数える。
偶数を 1 回でもかければ答えは偶数になるため、全て奇数の場合のみ数えないことになる。
そして、$\ A_i\ $が偶数なら 2 個、奇数なら 1 個の奇数が現れるため、$\ A_i\ $が奇数か偶数か判断し、個数を全て掛け算したものを$\ 3 \times N\ $から引く。
例4 なら$\ 3^{10}-(2 \times 2 \times 2 \times 1 \times 2 \times 2 \times 1 \times 2 \times 1 \times 2)\ $ となる。
n = int(input())
a = list(map(int,input().split()))
ans = 3 ** n
o = 1
for i in range(n):
if a[i] % 2 == 0:
o *= 2
else:
o *= 1
print(ans - o)
#97. ABC121 C - Energy Drink Collector
Difficulty:324
安いドリンクを買った方がお得なので、$\ A,B\ $のリストを$\ A\ $を基準にソートする。
その後、$\ M\ $本買えるまで順番に買っていく。
n,m = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
a,b = [list(i) for i in zip(*l)]
j = 0
ans = 0
while m > 0:
if b[j] <= m:
ans += a[j] * b[j]
m -= b[j]
j += 1
else:
ans += a[j] * m
m = 0
print(ans)
#98. AGC004 A - Divide a Cuboid
Difficulty:278
偶数が存在する場合、そこを半分に分ければ丁度 2 等分できる。
例2 から、赤青で同じ数になるのが分かる。
全て奇数の場合は、長さ$\ N\ $の列を$\ \lfloor N/2 \rfloor\ $と$\ \lceil N/2 \rceil\ $に分ける。
例3 から分けた時の長さの差は 1 なので、$\ A\ $を分けたなら、$\ B \times C\ $個差になることが分かる。
$\ B \times C\ $が小さい方がいいので、 1 番長い列を分けることになる。
a = list(map(int,input().split()))
a.sort(reverse = True)
if a[0] % 2 == 0 or a[1] % 2 == 0 or a[2] % 2 == 0:
print(0)
exit(0)
block = a[0] * a[1] * a[2]
a[0] = a[0] // 2
x = a[0] * a[1] * a[2]
y = block - x
print(abs(x - y))
#99. ABC046 B - AtCoDeerくんとボール色塗り
Difficulty:322
$\ 1\ $個目のボールを$\ R\ $で塗ると$\ 2\ $個目のボールは$\ R\ $以外の色、$\ K-1\ $の中から選び、$\ i\ $個目のボールも$\ K-1\ $の中から選ぶ。
$\ 1\ $個目の色は$\ K\ $から自由に決めれるので、$\ 1\ $が$\ R\ $だった場合の塗り方は$\ (K-1)^{N-1}\ $ということになる。
$\ 1\ $色目は$\ B\ $でも$\ G\ $でも、$\ K\ $色から選ぶので$\ K \times ((K-1)^{N-1})\ $ということになる。
n,k = map(int,input().split())
print(k * ((k - 1) ** (n - 1)))
#100. CODE FESTIVAL 2016 qual A B - 仲良しうさぎ
Difficulty:323
仲良しなうさぎかどうか調べる。
$\ A_i=j\ $かつ$\ A_j=i\ $のときに仲良しなので、仲良しなペアは固定されると考える。
n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
if a[a[i]-1]-1 == i:
ans += 1
print(ans // 2)