ABC248 D Range Count Query
内容
公式解説と違う解き方なのでメモ。
問題
リストAとクエリ(L,R,X)が与えられる。 Aの区間[L,R]に含まれる 数字X の個数を求める。
考えたこと(1-originで書いてます)
- F(L,R) =Aの区間[L,R]に含まれる 数字X の個数とする。
- F(L,R) = F(1,R)-F(1,L-1) である。
- クエリが、[1,R]と[1,L-1]の二つに分かれる。 * それぞれを求めて、最後に計算する。
- F(1,q)を求める方法があればいい。
- これまでに出現した各数字の個数を記憶しておく。(CNT[x]=これまでに出たxの個数)
- qごとに A[:q]のxを数えるのは計算量的に辛い
- Aの数字を左から見つつ、クエリ[1,q]のqの小さい順に計算していくことで、Aを一回見るだけで良くなる。
実装
from collections import defaultdict N = int(input()) A =list(map(int,input().split())) Q = int(input()) # F[L,R]->F[1,R]-F[1,L-1] query_sep=[] for idx in range(Q): l,r,x = map(int,input().split()) query_sep.append((l-1,x,idx)) query_sep.append((r,x,idx)) #F[1,q]のqの小さいものから見ていく query_sep = sorted(query_sep,key=lambda x:x[0]) ans=[[] for _ in range(Q)] CNT=defaultdict(int) cur_a_idx=0 #Aをどこまで見たか #F[1,q]のqの小さいものから見ていく for cur,x,idx in query_sep: # A[:q]まで、CNTする while cur_a_idx<cur: a = A[cur_a_idx] CNT[a]+=1 #A[q]の数を+1する cur_a_idx+=1 #CNTには、A[:q]までのそれぞれの数字の個数が入っている。 cnt = CNT[x] #ansのi-th queryのところに、結果を入れる。 # L<Rなので、ans[0]はF(1,L) ans[1]はF(1,R)が入る ans[idx].append(cnt) for l in ans: #F(L,R)=F(1,R)-F(1,L-1) print(l[1]-l[0])
memo: pythonで post-order traversalをnon-recursiveにやる!
intro
- 備忘録的メモです。
motivation
issue
- TLEしてしまう。
- おそらく、下のような実装になるはずで。
- while文の中の、
for nex in adj[node]:
の部分が、遅い- nodeに戻ってくるたびに、このfor文が回ってしまう
- すでに訪問済みのnexには、もう行かないので、無駄なloopが回っている。
N = num_node adj = [[] for _ in raneg(N)] # 隣接list # adjを問題に沿って、構築する visited = [False]*N # post_orderを記録する post_order = [] # dfsをstackを使って再現 for s in range(N): stack = [s] visited[s] = True while stack: node = stack.pop() for nex in adj[node]: # お隣さんに移動する if visited[nex]: continue # stackにnodeとnexをこの順で入れることで、dfsできる stack.append(node) stack.append(nex) visited[nex] = True break else: # breakされなかったら通る(nodeより先(startから遠い)のnodeはすでに訪問した場合 post_order.append(node)
solution
- すでに訪問したnodeは,adjから消す
pro&cons
- pro: 早くなる
- adjがloopのたびに短くなるので、
for nex in adj[node]
が軽くなる。)
- adjがloopのたびに短くなるので、
- cons: adjが破壊される
- あとで再利用とかしたい時は、copyを作ってからやる。
code
- before:
for nex in adj[s]
- after:
while adj[s]: nex = adj[s].pop()
for s in range(N): stack = [s] visited[s] = True while stack: node = stack.pop() while adj[node]: #<=<=<= ここが変更点 nex = adj[node].pop() #<=<= adjに対する破壊的操作 if visited[nex]: continue stack.append(node) stack.append(nex) visited[nex] = True break else: # breakされなかったら通る(nodeより先(startから遠い)のnodeはすでに訪問した場合 post_order.append(node)
summary
CF712 Div2 F Flip the Cards
内容
- CodeForces 712 Div2 F問題を、pythonでといた
問題
https://codeforces.com/contest/1504/problem/Fcodeforces.com
考えたこと
- 解説ACです。
ポイント
- 減少列を分解するの頭いい。(minf>maxfのとこ)
- この条件の時、new_eleは、seq1,seq2のどっちにも入れる。
- つまり、これまでのseq1,seq2のどっちをひっくり返すかが、今後の要素に影響しない-> 切り離せる。
実装
import heapq N = int(input()) cards=[list(map(lambda x:int(x)-1,input().split())) for _ in range(N)] #(1=N)のカードの、反対側の値 rev_cards=dict() #(1~N)のカードについて、(min,max)の形にするためにひっくり返した? flipped=dict() #全てのカードを、((1~N),(N+1~2*N))にするために必要なcost costs=0 for a,b in cards: ar,br= min(a,b),max(a,b) #両方ともNより小さいなら無理 if br<N: print(-1) exit() rev_cards[ar]=br if b==br: flipped[ar]=False else: flipped[ar]=True costs+=1 # i以降のmax(先に求めておく) suff_max=[-1]*(N+1) for i in reversed(range(N)): suff_max[i] = max(suff_max[i+1],rev_cards[i]) # iまでのmin(更新しながら進む) pre_min=float("inf") #costi -> def_seq_iのなかで、前処理ですでにflipされているカード数 cost1=0 cost2=0 #答え ans=0 #二つの減少列 def_seq1=[float("inf")] def_seq2=[float("inf")] for i in range(N): pre_min=min(pre_min,rev_cards[i]) rev = rev_cards[i] if rev<def_seq1[-1]: def_seq1.append(rev) cost1+=int(flipped[i]) elif rev<def_seq2[-1]: def_seq2.append(rev) cost2+=int(flipped[i]) else: #減少列の数が3つ以上になると無理 print(-1) exit() #これを満たす時、iとi+1で、減少列を分解できる。 if pre_min>suff_max[i+1]: print("i=>",i) print(def_seq1,def_seq2) print(cost1,cost2) s1= len(def_seq1)-1 s2 = len(def_seq2)-1 #dec_seq2をひっくり返す (seq1の前処理でひっくり返されたやつ + seq2ひっくり返すながさ -seq2で前処理でひっくり返された数) rev2=cost1+s2-cost2 #dec_seq1をひっくり返す rev1=cost2+s1-cost1 ans += min(rev1,rev2) if rev1<rev2: print("rev=>",def_seq1) else: print("rev=>",def_seq2) cost1=0 cost2=0 def_seq1=[float("inf")] def_seq2=[float("inf")] print("ans=>",ans) print(ans)
終わりに
CF712 Div2 E Traveling Salesman Problem
内容
- CodeForces 712 Div2 E問題を、pythonでといた
問題
考えたこと
- TSPだけど、N<=10*5なので、greedyとかで行けそう。
- beautyが大きいところから、小さいところには、cでいける。
- 一番beautyが大きい都市まで行けば、あとは、残りを辿るだけで良くなる。
ポイント
- どんな移動をしても、最低で C=sum(c_i)はかかる。
- max_beautyの都市まで行けば、あとは c_iだけの移動になる。
- city1-> max_beauty_city間での、最短路を求めればいい。
実装
N = int(input()) costs=[list(map(int,input().split())) for _ in range(N)] # beautyでsortする。 costs=[(a,a+b) for a,b in costs] costs = sorted(costs,key=lambda x:x[0]) #とりあえず。costのsumは絶対必要。(それをどれだけ増やさずにいけるか) min_ans=sum(v[1]-v[0] for v in costs) #i->jの移動コストは、 ci + max(0,aj-ai-ci)) #ciは先に足してあるので、max(0,aj-ai-ci)を小さくする。 #今まで使った(ai+ci)の最大値を記録しておく。そこからの差分だけ増やしていけばいい dist=costs[0][0] print("sort=>",costs) #とりあえず、 max_beautyの都市まで行けばいい。 for i in range(N): min_ans += max(0,costs[i][0]-dist) dist = max(dist,costs[i][1]) print(min_ans) #終わりに * atcoderのどこかにも、似た問題があった気がした。 思い出せないけど・
ARC116 D I wanna win the game.
内容
考えたこと
ポイント
実装
youtube liveの解法(桁ごとにDPしてく)
- 多分 O(logM*N**2)
- 定数倍改善しないと、TLEした。
# -*- coding: utf-8 -*- class FactMod(): ''' modの値が素数の時のfactと組み合わせを求める フェルマーの小定理を用いているため、modが素数以外の時は使えない NとかRの値が固定なら、combとか、複数回呼び出すより先に、計算してしまってlistとかで持っておく方が良い。(TLE対策) ''' def __init__(self, n, mod): ''' コンストラクタ f:nまでの i!の値を 配列に入れる inv_f: (i!)^-1 の値を配列に入れる ''' self.mod = mod self.f = [1]*(n+1) for i in range(1, n+1): self.f[i] = self.f[i-1]*i % mod self.inv_f = [pow(self.f[-1], mod-2, mod)] for i in range(1, n+1)[::-1]: self.inv_f.append(self.inv_f[-1]*i % mod) self.inv_f.reverse() def fact(self, n): ''' n!の値を返す ''' assert n>=0 return self.f[n] def comb(self, n, r): ''' nCrの値を返す ''' #assert n>=r>=0 if r==0: return 1 ret = self.f[n] * self.inv_f[n-r]*self.inv_f[r] ret %= self.mod return ret def perm(self, n, r): """ nPrの値を返す """ assert n>=r>=0 ret = self.f[n] * self.inv_f[n-r] ret %= self.mod return ret def div(self,x,y): """ x/yの値を返す このclassにいるべきじゃないな """ return (x*pow(y,self.mod-2,self.mod))%self.mod def comb_low_r(self,n,r,MOD): """ nCr=\frac{\Pi_{i=0}^{i=r-1}(n-i)}{\Pi_{i=1}^{i=r}(i)} FactMod(N,MOD)のNの値が大きいと、前計算が重くて、動かない。 nCrのrが小さいという保証があるなら、以下のコードでも、十分早いはず """ ret=1 for i in range(r):#分子の計算 ret*=(n-i) ret%=MOD for i in range(2,r+1):#分母の計算(powでinv(i)を求める。) ret*=pow(i,MOD-2,MOD) ret%=MOD return ret N,M = map(int,input().split()) MOD=998244353 F = FactMod(N,MOD) #下から見ていくからreverseしとく bit_M = bin(M)[2:][::-1] bit_len_M = len(bit_M) max_carry=2501 max_carry=N//4*2+10 max_carry=2501+2 #一個前の情報しかいらないから、prevDPとnxDPの二つの一次元配列でいい DP=[0]*max_carry DP[0]=1 #毎回F.combを呼び出すとneckになるから、先に combs=[0]*(N+1) for i in range(N+1): combs[i]=F.comb(N,i) for i in range(bit_len_M): nxDP=[0]*max_carry cur_digit=int(bit_M[i]) for j in range(max_carry):#DPの遷移先 tmp=0 for k in range(int(cur_digit),max_carry,2):#DPの遷移元 cur_sum=(j*2-k+1)//2*2 if not(0<=cur_sum<=N): continue tmp+=DP[k]*combs[cur_sum] tmp%=MOD nxDP[j]=tmp DP=nxDP print(DP[0]%MOD)
editorialの解法(sum(A)の値ごとにDPしてく)
# -*- coding: utf-8 -*- class FactMod(): ''' modの値が素数の時のfactと組み合わせを求める フェルマーの小定理を用いているため、modが素数以外の時は使えない ''' def __init__(self, n, mod): ''' コンストラクタ f:nまでの i!の値を 配列に入れる inv_f: (i!)^-1 の値を配列に入れる ''' self.mod = mod self.f = [1]*(n+1) for i in range(1, n+1): self.f[i] = self.f[i-1]*i % mod self.inv_f = [pow(self.f[-1], mod-2, mod)] for i in range(1, n+1)[::-1]: self.inv_f.append(self.inv_f[-1]*i % mod) self.inv_f.reverse() def fact(self, n): ''' n!の値を返す ''' return self.f[n] def comb(self, n, r): ''' nCrの値を返す ''' ret = self.f[n] * self.inv_f[n-r]*self.inv_f[r] ret %= self.mod return ret def perm(self, n, r): """ nPrの値を返す """ ret = self.f[n] * self.inv_f[n-r] ret %= self.mod return ret def div(self,x,y): """ x/yの値を返す """ return (x*pow(y,self.mod-2,self.mod))%self.mod N,M = map(int,input().split()) MOD=998244353 F = FactMod(N,MOD) #DP[i]: sum(A)=iの時に、条件を満たす配列の数 DP=[0]*(M+1) DP[0]=1 for i in range(1,M+1): if i%2==1: continue else: for j in range(N): if 2*j>N or 2*j>i: continue DP[i] += F.comb(N,2*j)*DP[(i-2*j)//2] DP[i]%=MOD print(DP[-1])
終わりに
- editorial解は 絶対思いつけない気がした。
- 典型化しときたい。