AtCoder 京セラプログラミングコンテスト2021 ABC200 個人的メモ

所感

abcd4完でhighest更新
やったぜ

A - Century

ちょっと混乱してた。
$N\leq 3000$だったので、Nで全探索。

N = int(input())

ans = 0
for i in range(3001):
    if i == N:
        break
    if i % 100 == 0:
        ans += 1

print(ans)

B - 200th ABC-200

問題文通りに実装。

N, K = map(int, input().split())

for _ in range(K):
    if N % 200 == 0:
        N //= 200
    else:
        N = int(str(N) + "200")

print(N)

C - Ringo's Favorite Numbers 2

全探索するとTLEしそう。
「$A_i-A_j$が200の倍数になるということ」は、「$A_i$と$A_j$の下2桁が等しいこと」と「3桁目が共に偶数であるか共に奇数であること」の両方を満たしていること、と言い換えられる。

「3桁目が共に偶数であるか共に奇数であること」の理由

200の倍数は全て3桁目が偶数になるから、ある数に200の倍数を掛けても3桁目の偶奇は変わらない(偶数+奇数=偶数、偶数+偶数=偶数)。

こう考えると、Aの各要素は200通りに分けられる。
200通りに分けられた要素で同じ場所に分けられた要素同士で組$(i, j)$をつくれば$A_i-A_j$が200の倍数になる。
よって、200通りそれぞれの要素の個数での組み合わせの総和を求めればおｋ。

公式解説と同じことをわかりにくく考えた形になってた。
https://atcoder.jp/contests/abc200/editorial/1245

from math import comb

N = int(input())
group_by_mod = [[0] * 2 for _ in range(100)]
for a in input().split():
    # 配列外参照を回避するために、aの前に0を加えておく
    # 001ならint()に入れたときに0が除去され、1となる
    a = "000" + a
    group_by_mod[int(a[-2:])][int(a[-3]) % 2] += 1

ans = 0
for i in range(100):
    for j in range(2):
        # combの第一因数が0のとき、combは0を返す
        # つまりgroup_by_mod[i][j]=0のとき、ans+=0
        ans += comb(group_by_mod[i][j], 2)

print(ans)

D - Happy Birthday! 2

全探索するとTLEしそうだけど、他に何も思いつかん。
終了間際だったので、ダメ元で提出したら何かacした。

bit全探索した。

鳩の巣原理により、201個以上のパターンを調べれば必ず1つ以上は総和を200で割ったあまりが同じ数列が見つかる。
なので、TLEせずに済む。

https://ja.wikipedia.org/wiki/鳩の巣原理

from itertools import compress, product

N = int(input())
# Aはmod200した後の値で保持
A = list(map(lambda x: int(x) % 200, input().split()))

seen = [[] for _ in range(200)]
for bit in product([0, 1], repeat=N):
    indexes_lst = list(compress(range(N), bit))  # bit全探索

    tmp_sum = sum(A[i] for i in indexes_lst) % 200
    if seen[tmp_sum]:
        print("Yes")
        print(len(seen[tmp_sum]), *[x + 1 for x in seen[tmp_sum]], sep=" ")
        print(len(indexes_lst)  , *[x + 1 for x in indexes_lst]  , sep=" ")
        exit()

    seen[tmp_sum] = indexes_lst

print("No")