ARC 097 D Equals (python)
けんちょんさんのガイドに沿って解き進めています。
union find の問題。
交換する数字そのものが与えられるので、どことどこを交換したらいいかを効率的に調べる必要があります。
まず、数字から位置を求める配列を作りました。
例えば、上の様な配列があるとしたら、2は先頭にあるので、list[2]=1となります。
n, m = map(int, input().split()) pn = list(map(lambda x:int(x)-1, input().split())) ls = [-1] * n for i in pn: ls[pn[i]] = i
そこからしばらくは、union findの定型です。
def find(x): if par[x] == x: return x else: s = find(par[x]) par[x] = s return s def unite(x,y): s = find(x) t = find(y) if s>t: par[s] = t else: par[t] = s for _ in range(m): x, y = map(lambda x:int(x)-1, input().split()) unite(ls[x],ls[y]) #位置を基準にunite処理をしていきます。
最終的には、i番目の場所(place1)の親 と数字iの場所(place2)の親がつながっていれば良いことになります。
ans2 = 0 for i in range(n): place1 = i place2 = ls[i] if find(place1)==find(place2): ans2+=1 print(ans2)
3N Numbers
priority_queueの問題を解いてみた。
この問題を言い換えると、真ん中のN個の数字に仕切りを置いて、その左側を最大化、右側を最小化するようにN個ずつ選んで、左の和から右の和を引けばよいことになる。
ただし、仕切りのパターンがN+1個あり、そのたびに最大化/最小化の作業を繰り返すと計算量がN^2になってしまう。
そこで、まずは、K番目に仕切りを置いたときに、左側を最大化することだけを考えることにする。
仕切りが一番左端にあるとき、左側の最大値は、sum(左からN個)となる。そこから右に1個仕切りを動かすと、どうなるか。
左側N個に、中央の左端を加えて、その最小値を間引けばよい。この操作を繰り返すと、順々に仕切りを動かした場合の最大値が求まる。
heapq.heappush(l, m[k]) #真ん中のk番目の値をヒープに追加する。 left[1+k] = left[k] + m[k] - heapq.heappop(l) #新たな合計値は、動かす前の合計値から、加えた真ん中の値をたし、さっ引いたヒープの最小値を引けばよい。
ヒープの挿入/取り出しはlogNなので、N*2logN
左右両方で行うため、4NlogNということか。
仕切りを右に動かして、幅を増やしていくのは簡単だが、逆に減らして行くことはできないのがキーポイントです。
なので、右側でも同様に行えばいいが、独立に行う事になる。
つまり、左側で左からK番目の仕切りの場合を計算しているときに、右側では右からK番目の仕切りの場合を計算していることになるため、それらの最大値、最小値を一度記録しなければならず、ループの中で差を計算することができない。
import heapq N = int(input()) an = list(map(int, input().split())) left = [0] * (N+1) #仕切りを0からNまで動かしたときの、仕切りの左側からN個選ぶ時の最大値 right = [0] * (N+1) left[0] = sum(an[:N]) right[-1] = -sum(an[2*N:]) l = an[:N] heapq.heapify(l) m = an[N:2*N] r = [-i for i in an[2*N:]] heapq.heapify(r) for k in range(N): heapq.heappush(l, m[k]) left[1+k] = left[k] + m[k] - heapq.heappop(l) heapq.heappush(r, -m[-1-k]) right[-2-k] = right[-1-k] - heapq.heappop(r) - m[-1-k] ans = -float('inf') for i in range(N+1): ans = max(ans, left[i]+right[i]) print(ans)
ABC 178 初5完!
初5完して、パフォーマンスは1174でした。
近いように見えて遠い緑。速く緑に行きたい!
パパッと行くためには、全完必要。
時間切れになってしまったFはこのサイトがわかりやすい。
tiramistercp.hatenablog.com
3. Longest Substring Without Repeating Characters
問題:Given a string s, find the length of the longest substring without repeating characters.
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
文字列の中から、連続する文字列で重複がない最長の長さを求めよという問題。
チェックする文字列の最初と最後をi, jとして前探索すると、O(N^2)になってします。
以下の様な文字列があった場合、二個目のbで重複が見つかります。そしたら、一個目のbの次まで、重複リストから外しながら検索していき、次の文字列のスタート位置を一個目のbの次の文字に設定します。
こうすると、N-2N計算量になります。
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ans = 1 n = len(s) temp = 1 if n == 0 or n == 1: return n start=0 check = set(s[0]) for i in range(1, n): if s[i] in check: ans = max(ans, temp) for j in range(start, i): if s[j] != s[i]: check.remove(s[j]) else: start = j + 1 temp = i - j break check.add(s[i]) elif i == n - 1: temp += 1 ans = max(ans, temp) else: temp += 1 check.add(s[i]) return ans
ABC141D priority heap
priority heapを使うと、最大値の取得がlogNで可能に。
ランダムな値の挿入もlogNで可能。
import sys import heapq stdin = sys.stdin n,m = map(int, stdin.readline().split()) # heap は通常、最小値がrootのヒープを作成する。最大値を取得するために、マイナス各値にマイナスをかける。 an = [i*(-1) for i in map(int, stdin.readline().split())] #print(an) # リストのheap化 heapq.heapify(an) # heapから最大値を取り出して、半分にしてヒープに戻すことをm回。 for _ in range(m): b = heapq.heappop(an) heapq.heappush(an, (-1)*((-1)*b//2)) ans = (-1)*sum(an) print(ans)
ABC177E パイソンで
import sys from math import gcd stdin = sys.stdin # 標準入力 n = int(input()) an = list(map(int, stdin.readline().split())) # mまでの最小の素因数リスト つまり、8ならば2、17ならば17 # この数が分かれば、素因数分解の際に何で割ればいいか分かる。=試し割の必要なし m = max(an) ls = [i for i in range(m+1)] for i in range(2, m+1): if ls[i] == i: for j in range(2, m//i+1): ls[i*j] = i # print(ls) # ls[6] = 2, ls[7] = 7 # [0, 1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 5] # tを素因数分解したときの素数の集合 def primeset(t): ls2 = set() while t != 1: ls2.add(ls[t]) t = t//ls[t] return ls2 #print(primeset(6)) # primeset(6) = {2, 3} primes = set() for i in an: for j in primeset(i): if j in primes: # 素因数が重複していたら、互いに素ではない。 break else: primes |= primeset(i) continue break # 二重forループを抜ける。 else: print("pairwise coprime") exit(0) # すべての最大公約数を計算 GCD = an[0] for i in range(1, n): GCD = gcd(GCD, an[i]) if GCD == 1: print("setwise coprime") else: print('not coprime')
ABC177
ABCDの4完で、パフォーマンス814でした。
緑がかすかに見えてきた。