ABC367振り返り

前回の振り返り

今日はABC開催日だったので参加結果を振り返る

今回はBCDの3完、A問題が沼って3ペナしたのでブッチしてしまいました😅

A

適当にじっそうしたら3回WA
原因がよく分からず、時間もったいないのでパス

B

文字列を.でセパレートして
第2項が0なら第1項をint、
それ以外なら文字列全体をfloatに変換

ソースコード

main.py

s = input()
i,f = list(map(int,s.split('.')))
x = int(i) if f == 0 else float(s) 
print(x)

C

配列が条件を満たす数を総当り計算
考えうる配列を直積でイテレーションする。

ソースコード

main.py

import sys
from itertools import product
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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)

def main():
    N, K = rLI()
    R = rLI()
    B = [list(range(1,r+1)) for r in R]
    for p in product(*B):
        if sum(p) % K == 0:
            print(*p)
    
if __name__ == '__main__':
    main()

D

2週分累積和の剰余をだして
それぞれの休憩所から時計回りにN-1箇所巡ったとき
休憩所1から今の休憩所までかかる歩数の剰余が一致する数を答えに加算

自分の言葉ではこの説明が限界…

ソースコード

main.py

import sys
from collections import defaultdict, Counter

def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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)


def main():
    N, M = rLI()
    A = rLI()
    S = [0] + A
    S += A
    T = [0] * len(S)
    for i in range(1,2*N+1):
        S[i] += S[i-1]
        T[i] = S[i] % M
    c = Counter(T[:N])
    m = defaultdict(lambda: 0)
    for k,v in c.items():
        m[k]=v
    # err(S)
    # err(dict(m))
    ans = 0
    for i in range(N):
        t0, tn = T[i], T[N+i]
        m[t0] -=1
        # err(T[i],dict(m),T[i+1:N+i],[s-S[i] for s in S[i+1:N+i]])
        ans += m[t0]
        # err(ans, m[t0]) 
        m[tn] +=1
        
    print(ans)
    
if __name__ == '__main__':
    main()

E

線形代数の置換的なものをマッチングに応用したら…
とかおもってグラフならまだ自分は実装できないと思いパス

この考察は全然的外れでダブリングとかいう方法すればいいみたい。

F

セグ木でカウントしようとしたけどTLE
ハッシュ値を出して累積和とかそんなん知らんて…

G

ギリギリまでFやってたから見る時間なかった。
最近XORの問題多くない？

まとめ

A問題に沼って150点落としたが今回もD問題を解くことができた。

E以降の解けなかった問題は実装したことないアルゴリズムを使用する必要があり、
そのあたりの知識を蓄える必要がある。