pythonで青くなるブログ

主に競プロのについての記事(日記的な)を書きます。現在atcoder水色,こどふぉ青色。python3使って、やってます。atcoder青くなりたい

ABC248 D Range Count Query

atcoder python 競プロ greedy 最短経路

内容

公式解説と違う解き方なのでメモ。

問題

リストAとクエリ(L,R,X)が与えられる。 Aの区間[L,R]に含まれる 数字X の個数を求める。

atcoder.jp

考えたこと(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にやる!

atcoder SCC DFS post-order

intro

  • 備忘録的メモです。

motivation

  • pythonで、dsfの帰りがけ順序探索(post-order-traversal)をやるときに、非再帰で実装したい

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] が軽くなる。)
  • 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

  • pythonで、post-order-traversalの時に、non-recursion実装を早くする方法のメモ
  • (再帰実装でも、TLEしないと思うけど)
  • SCC分解の時に困ったので、使った。

CF712 Div2 F Flip the Cards

python 競プロ Codeforces greedy

内容

https://codeforces.com/contest/1504/problem/Fcodeforces.com

考えたこと

  • 解説ACです。

codeforces.com

ポイント

  • 減少列を分解するの頭いい。(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

python 競プロ greedy 最短経路 Codeforces

内容

codeforces.com

考えたこと

  • 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.

atcoder python 競プロ dp 組み合わせ 逆元

内容

  • ARC116のD問題 I wanna win the game をpythonで解説AC (解説というよりは、自分用のメモ)

    問題

  • atcoder.jp

  • editorial解と　youtube解説の解の二つでといた。

考えたこと

ポイント

実装

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解は　絶対思いつけない気がした。
  • 典型化しときたい。