競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - The Number of Even Pairs
偶数が書かれたボールN個と奇数が書かれたボールM個、合計が偶数になる組み合わせの数の数を答える問題です。
単純に偶数同士の組み合わせ$N(N-1)/2$と奇数同士の組み合わせ$M(M-1)/2$を合わせれば答えになります。
N, M = map(int, input().split())
print((N*(N-1))//2 + (M*(M-1))//2)
B - String Palindrome
与えらえた文字列が「回文二つを組み合わせた回文」になっているかを判定する問題です。
左側の前半、左側後半、右側前半、右側後半の4つの文字列が一致しているかを、文字列Nの1/4まで回して判定します。
s = input()
n = len(s)
for i in range((n-1+3)//4):# +3は切り上げ用
if not(s[i] == s[(n-1)//2-i-1] and s[(n+3)//2 + i-1] == s[-i-1] and s[i] == s[-i-1]):
print('No')
exit()
print('Yes')
他の解答とか解説見たらもっときれいな書き方がありました。
s = input()
n = len(s)
sl = s[:n//2]
sr = s[n//2+1:]
if sl == sr and sr == sr[::-1]:
print('Yes')
else:
print('No')
文字列を左右に切り分けて、右側srが回文になっているならそれと一致するslも回文。slとsrがそれぞれ一致する回文なので二つを合わせても回文。条件が二つで済みました。
C - Maximum Volume
高さ横幅縦幅の合計がLの直方体の持つ最大の体積を答える問題です。
高さ=横幅=縦幅の時体積が最大となるので、それぞれの長さは$L/3$。これを3乗するだけです。
L = int(input())
print((L/3)**3)
なんで辺の長さが一致する時最大になるのかは説明できなかったので、一応数学的な説明を書いておきます。
以下が変数三つでの相加相乗平均の公式です。
$$ {a＋b+c\over 3}\geq (abc)^{1/3}$$
高さを$a$, 幅を$b$, $c$と考えると直方体の体積は$abc$で求まります。
$$ ({a＋b+c\over 3})^3\geq abc$$
$a=b=c$の時この式の等号が成立するので最大の体積となります。
D - Banned K
数字の書かれたN個のボールから同じ数同士を選ぶ組み合わせが何通りあるかを、ボールを除外しながら考える問題です。
まず全部のボールから組み合わせ数の合計$S$を求めます。そこから、数字$n$のボールが$m$個あるとき、数字$n$のボールを一個取り出すと$m-1$通りだけ合計$S$が減ることになります。取り出すボールごとに数字$n$を当てはめて出力していきます。
import collections
N = int(input())
li = list(map(int, input().split()))
cn = collections.Counter(li)
sumC = sum([n*(n-1)//2 for n in cn.values()])
for k in range(N):
print(sumC-cn[li[k]] + 1)
E - Dividing Chocolate
板チョコ内のホワイトチョコの量が一定以下になるように割る回数を答える問題です。
「探索の考え方」「割った内のホワイトチョコレートの数の数え方」どちらもわからなかったので諦めました。
解説を見ました。$H\leq 10$という狭い範囲指定があるため、横向きの割り方は愚直に$2^{H-1}$通りの全探索ができます。全探索にはitertools.product()を用いて、0か1が含まれる長さH-1の配列を全通り作成します。これで探索はOK。
横向きに割られたチョコレートは縦向きにホワイトチョコの数を数えた1次元配列として二次元配列SW内に格納し、左から数えていきます。どれかの列のチョコの数が規定数Kを超えたらチョコを縦向きに割ってカウントを0に戻します。これでチョコレートのカウントもできます。ただし1次元配列の持つ値がKを超えていたらチョコを何度割っても不可能なため、その状況は横向きに割るところからやり直し。
というわけで以下のようなコードになります。
import itertools
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
cnt = t.count(1)
SW = []
tmp = [int(s) for s in S[0]]
for i, c in enumerate(t):
if c:
SW.append(tmp)
tmp = [int(s) for s in S[i+1]]
else:
tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
SW.append(tmp)
H_ = len(SW)
sums = [0] * H_
if max(itertools.chain.from_iterable(SW)) > K:
continue
for w in range(W):
sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
if max(sumtmp) > K:
cnt += 1
sums = [SW[i][w] for i in range(H_)]
else:
sums = sumtmp
ans = min(ans, cnt)
print(ans)
この記事はE問まででとりあえず終わりとします。