東京海上日動コンテスト2020, abc170

NOMURA プログラミングコンテスト 2020 A,B,C の3完
ABC170 A,B,C,D の4完でした。
土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1 <= j <= N の範囲で [ j-A[ j-1 ], j+A[ j-1 ]+1 ) の区間を +1 する→リストを見終わったらセグ木から A を更新する、のを繰り返しました。
A[ j ] の最大値が N で、２の指数関数的に A[ j ] が大きくなるから、繰り返す回数は高々 log(N) で、一回の区間加算と A の更新でそれぞれ N, N*log(N) かかる(はず)だから計算量は O(N*log(N)+N*log(N)*log(N)) でやや通るか怪しいけど pypy で 1998ms で通った。
Submission #14246080 - Tokio Marine & Nichido Fire Insurance Programming Contest 2020
D は半分全列挙じゃねとなったところまでは良かったけど永久に TLE していた。前処理とか定数倍高速化とかわからん。

日曜は集中力が足りない＆Dが苦手なセットで大変だった。
計算量がイメージしにくい＆サンプルだけで条件が突き詰めにくい問題が苦手。
色々考えて、結局ソートして小さいものから、約数のリストを作り、そのリストに今まで見た数が一つも入っていなければオッケーだなとなるも、めちゃTLEしそうでなかなか手が進まなかった。
O(N) でできそうな方法ばかり考えようとしていた。
結局その方針で解くも、例えば [ 2, 3, 5, 5, 7 ] のように同じ数字が含まれているときに、最初に 5 が来たときに 今まで見た数の集合には { 2, 3 } しか含まれていないので、5 を答えに入れてしまったりしていてデバッグに苦労した。あと、1 から約数をつくるときに RE を吐いたりしたり、TLEを不用意に連発して 7 WA した
重複しているかどうかは約数の集合と今まで見た数の集合をそれぞれ set で持っておいて積集合を取るといい。pypyじゃないとTLEする。

#ABC170 D
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()

if a[0] == a[-1]: # n=1 やサンプル２のような時
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1: #１だけは素因数分解するときにバグるので別で処理
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct): # 約数のリストつくるやつ
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n): #素因数分解
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct): # 約数の集合を作る
      c.add(num(div))

# 積集合をとり、それが空でかつ同じ数字が並んでない時に答えを加算
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i) #今まで見た数の集合を更新

print(ans)

E はねぼこさんの記事をみて解きました。
【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita
園児の所属が変わるたびに、( From → to に変わったとする）
①最高レートの集合から、移動前の幼稚園の最高レートを消す
②最高レートの集合から、移動後の幼稚園の最高レートを消す
③移動前の幼稚園から園児を消す
④移動後の幼稚園に園児を入れる
⑤最高レートの集合に、更新された移動前の幼稚園の最高レートを入れる
⑥最高レートの集合に、更新された移動後の幼稚園の最高レートを入れる
⑦最高レートの集合から最低値を出力する
⑧園児のいる幼稚園を更新する
の8動作を行います。
そしてこれを set がない python で実現するには
１．園児のレートと所属を保管するリスト（ info )
２．最高レートの集合 ( max_table )
３．最高レートから削除されたはずのレートの集合 ( er_max )
４．幼稚園 i にいる園児の集合 * 2*10**5 ( sc )
５．幼稚園 i から削除したはずの園児の集合 ( er_sc )
の5個を作り、
①→ er_max に移動前の幼稚園の最高レートを入れる
②→ er_max に移動後の幼稚園の最高レートを入れる
③→ er_sc [ From ] に園児のレートを入れる
④→ sc [ to ] に園児のレートを入れる
... とやっていきます。
こうすることで、⑤～⑦で必要となる今現在の最高値、最低値の出力を、
list と er_list から一つずつ heap で取り出して、取り出した２つが異なればそれが現在の最小値（最大値）とすることができます。記事を読もう。
後は空のリストから heappush するとエラーになるので初めに 0 とか INF を入れたりした。

#ABC 170 E
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappush,heappop
inf = 10**9+1

n,q = map(int,readline().split()) # 1-indexed
info = [0]*(n+1)
er_sc = [[0] for i in range(2*10**5+1)]
sc = [[0] for i in range(2*10**5+1)]

for i in range(n):
  a,b = map(int,readline().split())
  info[i+1] = (a,b)
  heappush(sc[b],-a)
  
max_table = [] # これは空になることないので何も入れなくていい
er_max = [inf] # 空になりうるので inf を入れておく
for i in sc:
  m = -heappop(i)
  if m != 0:
    heappush(max_table,m)
  heappush(i,-m)
  
for i in range(q):
  c,to = map(int,readline().split())
  rate,From = info[c]
  from_m = -heappop(sc[From])
  to_m = -heappop(sc[to])
  heappush(sc[From],-from_m)
  heappush(sc[to],-to_m)
  if from_m != 0:
    heappush(er_max,from_m) # 1
  if to_m != 0:  
    heappush(er_max,to_m) # 2
  heappush(er_sc[From],-rate) # 3
  heappush(sc[to],-rate) # 4
  
  while True:
    no = -heappop(er_sc[to]) # 5
    ch = -heappop(sc[to])
    if no == 0 or no != ch:
      if ch != 0:
        heappush(max_table,ch)
      heappush(er_sc[to],-no)
      heappush(sc[to],-ch)
      break
      
  while True:
    no = -heappop(er_sc[From]) # 6
    ch = -heappop(sc[From])
    if no == 0 or no != ch:
      if ch != 0:
        heappush(max_table,ch)
      heappush(er_sc[From],-no)
      heappush(sc[From],-ch)
      break

  while True:
    no = heappop(er_max) # 7
    ch = heappop(max_table)
    if no == inf or no != ch:
      print(ch)
      heappush(max_table,ch)
      heappush(er_max,no)
      break
      
  info[c] = (rate,to) # 8

追記：きりさんの記事をみて、
素因数分解を O(n^(1/4)) でする - Qiita
素因数分解のオーダーを O(n**(1/2)) から O(n**(1/4)) にしたので 1 秒以上速くなりました。
まだ python だと TLE するけど。
Submission #14422336 - AtCoder Beginner Contest 170