ABC439を解いた【中心固定の数え上げ】

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

ABC439のD問題を解いていく

実装コード

条件 7:5:3 は「ある x があって A_i=7x, A_j=5x, A_k=3x」に言い換える。

i,j,kのうちjが最大値の場合を探索するアルゴリズムを用意して、
その後に逆順で探索することでjが最小値の組み合わせ数も計算できるようだ

組み合わせ計算

• Aの各要素が何の倍数か順番にチェック。
• t[x]=これまでの 3x の個数, s[x]=これまでの 7x の個数 を持っておき
• A_j=5x が来たら t[x]*s[x] を足す（7担当の i と 3担当の k を独立に選べるので掛け算）

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
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())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def calc(A):
    ans = 0
    t = defaultdict(lambda: 0)
    s = defaultdict(lambda: 0)
    for a in A:
        if a % 3 == 0:
            t[a//3] += 1
        if a % 7 == 0:
            s[a//7] += 1
        if a % 5 == 0:
            ans += t[a//5]*s[a//5]
    return ans

def main():
    N = rI()
    A = rLI()
    
    ans = calc(A) + calc(reversed(A))
    print(ans)
    
if __name__ == '__main__':
    main()

感想

実装コードは単純だけどそれを考えつくまでが難しそうな考察メインの問題だと思った。