【AtCoder】ABC200 感想戦 - RONの技術ブログ

2021/5/12に開催されたABC200を振り返ります。
結果はA~Cの3完でした。D問題もう少しで解けそうでしたがあと1歩及ばずでした。
順位：2320位、パフォーマンス：1042、レート：635 → 686(茶)

A問題：A - Century
西暦から世紀を求める問題でした。
100の倍数の西暦の場合に惑わされなければ非常に簡単でした。

n = int(input())
print((n-1)//100 + 1)

B問題：B - 200th ABC-200
整数Nに対して
- Nが200の倍数であればNを200で割る。
- そうでなければ、NをNの後ろに文字列として200を付け加えた整数に置き換える。

という処理をK回繰り返した後の数字を出力する問題でした。
Kの上限が20と小さいので普通にループを回せば良いです。
文字列として200を後ろに加える処理はNを1000倍して200を足せば良いです。(文字列に変換して足しても良い)

n, k = map(int,input().split())
for i in range(k):
    if n % 200 == 0:
        n //= 200
    else:
        n = n*1000 + 200
print(n)

C問題：C - Ringo's Favorite Numbers 2
N個の正整数からなる数列Aにおいて、以下の条件を全て満たす整数の組(i, j)の個数を求める。
- 1 <= i < j <= N
- Ai - Ajは200の倍数

引き算した結果が200の倍数になるということは、配列Aの全要素のmod 200を予め算出しておき、同じ数の選び方を考えれば良いです。
pythonの場合、collectionライブラリのCounterを使うとどの要素が何個あるか辞書型で簡単に求められます。
その後n個から2つを選ぶ組み合わせ(nC2)はn*(n-1)//2で求められるので、答えに加算していけば良いです。

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

a = [itm % 200 for itm in a]
cnt = Counter(a)

ans = 0
for val in cnt.values():
    ans += val * (val-1) // 2

print(ans)

D問題：D - Happy Birthday! 2
問題省略します。
解けませんでしたが、以下のように考えました。
- C問題と同様配列Aの全要素のmod 200を求め、後は要素の組み合わせで同じ値を作れるかを検証すれば良い。
- 2⁷ < 200 < 2⁸より、n>=8の場合は絶対にYesになる。
- 1<N<200よりbit全探索をするとTLEになる。

TLE対応で行き詰まりました。
結論、2⁸>200のため、鳩の巣原理より配列Aの最初の8要素でbit全探索をすれば良いらしいです。
これは初見では厳しかったです。鳩の巣原理勉強しないとですね。

まとめ
A~Cまではすらすらと解けましたが、Dで大ブレーキでした。
レートは結構上がったので、この調子で緑を目指して頑張ります。