pythonのlistで使うpop()

python

ABC 243 Moves on Binary Tree

"L","R","U"で構成された文字列sから、RやLの後ろにあるUを1対1で消していきたい。
制約：sの文字数 n≦10**6

例：LRULURLURLULULRURRLRULRRRUURRU
→LRRLRRLLRR

失敗例：
RUとLUを、sの文字列が短くならなくなるまで消し続ける。
計算量 = Uの数 x sの文字数 = O(N^2)

while True:
  s = s.replace("RU","")
  s = s.replace("LU","")
  if len(s) == pl:
    break
  else:
    pl = len(s)

→TLE


解説例：
リストを用意。Uがきたらリストの末尾を参照。
末尾がSかTならUは追加せずにpop()する。
計算量O(N)

T = []
for a in s:
  if len(T) == 0:
    T.append(a)
  elif a == "U" and T[-1] != "U":
    T.pop()
  else:
    T.append(a)

popといえばdequeの印象だったが、listでpopもうまく使っていきたい。

繰り返し二乗法

python

・x**yを使わないといけないのに、yの制約が「0≦y≦10**9」とかのとき。

①"aのn乗"の計算

def reppow(a,n):
  if n == 0:
    return 1
  if n == 1:
    return a
  if n%2 == 1:
    ret = reppow(a,n-1)*a
    return ret
  ret = reppow(a,n//2)
  ret = ret*ret
  return ret

このままgoogle colabなどで

reppow(3,100000)

で実行（して、結果を表示）しようとすると

ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

となってしまう。

import sys
sys.set_int_max_str_digits(10**6)

これで解決。
ただし、この桁数をそのまま競プロで使うことはなさそうなので、なにかしらのmodを取るような設問にはなりそう。
逆に、4300桁で収まるくらいなら繰り返し二乗法でなくても良い程度の計算量に収まりそう。


②"aのn乗をpで割ったあまり"の計算

import sys
sys.setrecursionlimit(10**9)

def modpow(a,n,p):
  if n == 0:
    return 1
  if n == 1:
    return a%p
  if n%2 == 1:
    ret = modpow(a,n-1,p)*a
    return ret%p
  ret = modpow(a,n//2,p)
  ret = ret*ret
  return ret%p

pypyなら、

import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

も忘れずに追加しておく。

プリム法

python

最小全域木問題に対してのプリム法による解法
AOJ ALDS1_12_A　Minimum Spanning Tree

・まずスタートの点を決める
・「既に到達した点」から「まだ到達していない点」へ行く辺の中で一番コストの低い辺を探す
・その辺を採用し、辺の先の点は「既に到達した点」に加える
・すべての点に到達したところで最小全域木が完成する

問題文が
点i　　　 点jへのコスト　点j+1へのコスト　点j+2へのコスト
点i+1　　点jへのコスト　点j+1へのコスト　点j+2へのコスト
という感じのときに使いやすい

計算量はO(N^2)
でちょっと使いにくいかも

#入力
n = int(input())
A = []
for _ in range(n):
  a = list(map(int,input().split()))
  A.append(a)
ans = 0

#到達したかどうかのboolリスト
used = [False]*n
#適当に0番目から開始
used[0] = True
#到達した点の数のカウントを行う
cnt = 1

while cnt<n:
  mincost = float("INF")
  point_temp = -1
  #現時点で到達がTrueになっている点の行き先のうちで
  for i in range(n):
    if used[i]:
      for j in range(n):
        #行き先への到達がTrueになっておらず、-1でもない点のコストを全検索
        if used[j]:
          continue
        if A[i][j] == -1:
          continue
        if A[i][j] < mincost:
          mincost = A[i][j]
          point_temp = j
  if point_temp == -1:
    print("error")
    exit()
  #最小コストだった点をTrueに変更する
  used[point_temp] = True
  ans += mincost
  cnt += 1
  
print(ans)


クラスカル法、プリム法は
下記のサイトを参考にしました。
ありがとうございます。
algo-logic.info

クラスカル法

python

最小全域木問題に対してのクラスカル法による解法
AOJ GRL 2_A Minimum Spanning Tree

・重みを持つすべての辺をコスト順に並び替える
・コストの低い辺から順に採用するか検討していく
・その辺を採用すると「閉路」ができてしまうなら採用しない
・「閉路」ができてしまうかどうかはunionfindで判定する
・点の数-1個の辺を採用したところで最小全域木が完成する

・問題文が、
点I　　点j　　コスト
点i+1　点j+1　コスト
となっているときに使いやすい

#入力
v,e = map(int,input().split())
costs,edges = [],[]
for _ in range(e):
  s,t,w = map(int,input().split())
  costs.append(w)
  edges.append([s,t])
ans = 0

##UnionFind-->>##
par = [-1]*v
siz = [1]*v

def root(x):
  if par[x] == -1:
    return x
  else:
    par[x] = root(par[x])
    return par[x]

def size(x):
  return siz[root(x)]

def unite(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return False
  if siz[x] >= siz[y]:
    par[y] = x
    siz[x] += siz[y]
  else:
    par[x] = y
    siz[y] += siz[x]
  return True

def issame(x,y):
  tf = root(x) == root(y)
  return tf
##-->>UnionFind##

#辺の並び替え　ここに計算コストO("e"log"e")
costs,edges = zip(*sorted(zip(costs,edges)))
#keyは採用した辺の数を格納する。これがv-1になるまで繰り返す
key = 0
for edge,cost in zip(edges,costs):
  s,t = edge
  #sとtが既に連結していればスキップ
  if issame(s,t):
    continue
  #そうでなければsとtを連結させてkeyを1つ増やす
  unite(s,t)
  key += 1
  ans += cost
  if key == v-1:
    print(ans)
    exit()

Union Find のベース部分

python

unionfindのお約束部分

#n = int(input())

par = [-1]*n
siz = [1]*n

def root(x):
  if par[x] == -1:
    return x
  else:
    par[x] = root(par[x])
    return par[x]

def size(x):
  return siz[root(x)]

def unite(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return False
  if siz[x] >= siz[y]:
    par[y] = x
    siz[x] += siz[y]
  else:
    par[x] = y
    siz[y] += siz[x]
  return True

def issame(x,y):
  tf = root(x) == root(y)
  return tf

エラトステネスのふるい

python

エラトステネスのふるい

・任意のn以下の素数のリストをO(nloglogn)（らしい）で得る。

def prime(x):
  x = int(x)
  if x < 2:
    return []
  P = [True]*(x+1)
  P[0],P[1] = False,False
  res = []
  for i in range(x+1):
    if P[i] == False:
      continue
    else:
      res.append(i)
      q = i*2
      while q < x+1:
        P[q] = False
        q += i
  return res

入力

#input
p = prime(100)
print(p)

出力

#output
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]