エイシング プログラミング コンテスト 2020 A~D解説

しょうもない実装ミス、誤読を直せずA,Bの2完でした（え？）

A - Number of Multiples

概要

L 以上 R以下の整数のうち、dの倍数であるようなものはいくつありますか？

考察

基本的にはl,r をd　で割った商の差を取れば良い。ただし、l がd で割り切れる時は、+1する

#!/usr/bin/env python3
l, r, d = map(int, input().split())
print(r // d - l // d + (l % d == 0))

B - An Odd Problem

概要

1,..N の番号が書かれたマスがあり、それぞれ値A[i] を持つ。
Nこのマスのうち、番号、値が共に奇数であるマスの数を求めよ

考察

１つずつマスを見てO(N)
スライスを使うと奇数ますだけ見れて楽

#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(0, n, 2):
    if a[i] % 2:
        ans += 1

print(ans)

C - XYZ Triplets

概要

1<=a,b,c
a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a = n
を満たすa,b,c の組み合わせを1<=n<=N に対してそれぞれ求めよ

制約

N<=10**4

考察

1<=a,b,c より、a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a はa**2 ,b**2,c**2よりは大きくなるから、条件を満たすa,b,c, は100未満である。

つまり1~99までa,b,cを全探索すれば良い。

ただし、n をループさせるとO(N)*100**3となってTLEするので、それぞれのn に対して個数を持つリストを用意して、a,b,cの全探索での値がN以下ならそこに対応する個数を+1すれば良い

#!/usr/bin/env python3
n = int(input())
cnt = [0] * (1 + n)
for a in range(1, 100):
    for b in range(1, 100):
        for c in range(1, 100):
            k = a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a
            if k > n:
                continue
            else:
                cnt[k] += 1
for i in range(1, n + 1):
    print(cnt[i])

D - Anything Goes to Zero

概要

D - Anything Goes to Zero
説明しにくいのでリンク
２進数をそれに含まれる1の個数で割っていったあまりに更新するという操作を繰り返す

制約

1<~N<=2*10**5

考察

　桁数が2*10**5なので、まともに計算するとオーバーフローするし、時間がかかる。
　オーバーフロー対策として、mod だけ取れば良いのでmod で計算する。
ただ、1回操作を行うと、1の個数以下になるので2*10**5以下になり大幅に減る。

　それぞれの反転で1の数は+1 or -1 になるので、初期の1の値をcntとすると、cnt+1とcnt-1をmodにした時の値をそれぞれもち、それぞれのbit反転数に対してbit反転した後の値をそこから計算した後、それ以降の操作を行えば良い。

　操作をstepごとにまとめると以下のようになる
step1; 1を数える cnt_1
step2 : 全体の計算をする cnt1 + 1 とcnt1 -1 それぞれ
step3 : それぞれの桁に対して0 なら cnt+ 1 を適用 + 2**k mod cnt + 1
1ならcnt - 1　を適用 - 2**k mod (cnt-1)
step4 : その中でf(x)を0になるまで計算

実装

#!/usr/bin/env python3
n = int(input())
x = input()
cnt = x.count("1")
x_cnt_plus = 0
x_cnt_minus = 0
for i in range(n):
    if x[i] == "1":
        x_cnt_plus += pow(2, n - i - 1, cnt + 1)
        x_cnt_plus %= cnt + 1
        if cnt > 1:
            x_cnt_minus += pow(2, n - i - 1, cnt - 1)
            x_cnt_minus %= cnt - 1
for i in range(n):  # 上からi 桁目に注意
    if x[i] == "0":
        f = x_cnt_plus + pow(2, n - i - 1, cnt + 1)
        f %= cnt + 1
    else:
        if cnt == 1:
            print(0)
            continue
        f = x_cnt_minus + cnt - 1 - pow(2, n - i - 1, cnt - 1)
        f %= cnt - 1
    ans = 1
    while f != 0:
        cnt_f_1 = 0
        k = f
        while k:
            if k % 2:
                cnt_f_1 += 1
            k //= 2
        f = f % cnt_f_1
        ans += 1
    print(ans)