AtCoder Beginner Contest 159 過去問

Python AtCoder

はじめに

AtCoder Beginner Contest 159(過去問)を解きました。

A問題

2つの球を選んで、偶数になる組み合わせは、
全ての組み合わせから奇数×偶数の組み合わせを除いた確率です。

n,m = map(int,input().split(' '))
kakuritu = ((n+m)*(n+m-1))/2
kisuu = m*n
print(int(kakuritu-kisuu))

B問題

文字全体、文字列前半、文字列後半をそれぞれ格納して、
一つずつ回文か否かのチェックを加えています。
文字数が偶数の文字列は最初に否とする判定を加えました。

input_ = input()
length = int(len(input_))
if length%2==0:
  print('No')
  exit(0)

f,b = input_[:int((length-1)/2)],input_[int((length-1/2)):]
str_ = [input_,f,b]

for s in str_:
  #print(s)
  if s==''.join(list(reversed(s))): pass
  else:
    print('No')
    exit(0)
print('Yes')

C問題

一定の辺長から最大となる体積を求める問題です。
立方体が最大体積となると知ってれば楽勝です。

sum_ = float(input())
v = float((sum_/3)**3)
print('%.7f'%v)

D問題

N枚のカードから一枚抜いて、
N-1枚のカード分から同じ整数を持つ組み合わせを求める問題。
自分が書いたのは以下のコード。
ディクショナリをコピーしたせいで、メモリと処理速度の問題からTLEされました。

inp = int(input())
lis = list(map(int, input().split()))
 
dic = {}
 
#count
for l in lis:
  if l in dic: dic[l] += 1
  else: dic[l] = 1
 
dic_sum = dic.copy()
#calcurate
for d in dic:
  dic_sum[d]=int(dic[d]*(dic[d]-1)/2)
  
for l in lis:
  dic_sum_n = dic_sum.copy()
  if l in dic:
    dic_sum_n[l] = int(((dic[l]-1)*(dic[l]-2))/2)
    print(sum(dic_sum_n.values()))

WriteUpを参考にしました。
qiita.com

  • 重複数字: 重複カウント数 (ディクショナリ)
  • 重複数字: パターン数 (ディクショナリ)

⬇︎

  • 重複数字: 重複カウント数 (ディクショナリ)
  • パターン数合計 (整数型)

にするとTLEが改善されました。

  1. 全体の重複数を計算
  2. パターン数を計算
  3. 最初に抽出するカード毎にパターン数を調整

の方向性自体は良かったみたいです。

inp = int(input())
lis = list(map(int, input().split()))
 
dic = {}
 
#count
for l in lis:
  if l in dic: dic[l] += 1
  else: dic[l] = 1
 
#dic_sum = dic.copy()
s = 0
#calcurate
for d in dic:
  s += int(dic[d]*(dic[d]-1)//2)
  
for i in range(inp):
  t = dic[lis[i]]
  print(s-int(t*(t-1)//2)+int((t-1)*(t-2)//2))