ABC433Dを解いた【二分探索】

筆者はレート800前後の茶～緑コーダ

ABC433のD問題を解いていく

実装コード

準備

• Aの各要素aの桁数sをまとめたSのリストを用意
• 「s桁の数 a の M での剰余を昇順に並べたリスト」→lowers[s]を用意

A の各要素aを全探索

• iを1からSの最大値(D)までループ
• (a * 10^i + c) % M == 0となるような i桁のAの要素cの個数 をカウント
• 求めたいcの値はb = a % Mから逆算してc = (M - b) % M を lower[i] 内で二分探索して一致した数を加算

最後に合計値を出力

main.py

import sys
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left

def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

d = defaultdict(lambda: 0)
c = Counter()

def main():
    N, M = rLI()
    A = rLI()
    S = [len(str(a))for a in A]
    D = max(S)
    #err(S)
    #err(D)
    #upper = [0] * (D+1)
    lowers = [[] for _ in range(D+1)]
    for a,s in zip(A,S):
        lowers[s].append(a%M)
    for lower in lowers:
        lower.sort()
    ans = 0
    for a,s in zip(A,S):
        #err(a,a % M)
        for i in range(1,D+1):
            a *= 10
            b = a%M
            c = (M-b)%M
            #err(a,b,c,lowers[i],bisect_left(lowers[i],c+1) - bisect_left(lowers[i],c) )
            ans += bisect_left(lowers[i],c+1) - bisect_left(lowers[i],c) 
    print(ans)

if __name__ == '__main__':
    main()

感想

解説読むのむずかったしこの記事で説明するのもむずい問題だった。