AtCoder Beginner Contest 159の感想

ABC159に参加した。

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – The Number of Even Pairs

偶数＋偶数か、奇数＋奇数の2通り。

n, m = map(int, input().split())

ans = n * (n - 1) // 2 + m * (m - 1) // 2
print(ans)

B – String Palindrome

逆転させた文字列が元の文字列と一致するか比較する。

s = input()
n = len(s)
s = [s[i] for i in range(n)]

l = (n - 1) // 2
r = (n + 3) // 2

left = s[:l]
right = s[r - 1:]

if s == list(reversed(s)) and left == list(reversed(left)) and right == list(reversed(right)):
    print('Yes')
else:
    print('No')

C – Maximum Volume

一辺が L / 3 の立方体の時に最大の体積となる。

非常にシンプルかつ記述量が少なく、A問題でも良いような気がした。

l = int(input())

x = l / 3
ans = x ** 3
print(ans)

D – Banned K

O(N^2)になってしまうことが分かりつつも、始めは愚直に実装してTLEになってしまった。

時間内に解けなかったため、コンテスト終了後に再考

始めに、k番目を取り除かずにN個全てを使って2つの整数が等しくなる組み合わせ数を求める。

次に、k番目と等しい整数の組み合わせ数を引く。

集合の演算を考えることでO(N)で解くことができた。

from collections import Counter

n = int(input())
a = list(map(int, input().split()))

if len(a) == len(set(a)):
    for i in range(n):
        print(0)
else:
    kw = Counter(a)
    ans = sum([x * (x - 1) // 2 for x in kw.values()])

    for i in range(n):
        print(ans - kw[a[i]] + 1)