ARC 097 D Equals （python）

atcoder.jp

けんちょんさんのガイドに沿って解き進めています。
union find の問題。
交換する数字そのものが与えられるので、どことどこを交換したらいいかを効率的に調べる必要があります。
まず、数字から位置を求める配列を作りました。

例えば、上の様な配列があるとしたら、２は先頭にあるので、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の問題を解いてみた。

atcoder.jp

この問題を言い換えると、真ん中のN個の数字に仕切りを置いて、その左側を最大化、右側を最小化するようにN個ずつ選んで、左の和から右の和を引けばよいことになる。
ただし、仕切りのパターンがN+1個あり、そのたびに最大化/最小化の作業を繰り返すと計算量がN^2になってしまう。

そこで、まずは、K番目に仕切りを置いたときに、左側を最大化することだけを考えることにする。
仕切りが一番左端にあるとき、左側の最大値は、sum(左からN個)となる。そこから右に１個仕切りを動かすと、どうなるか。
左側N個に、中央の左端を加えて、その最小値を間引けばよい。この操作を繰り返すと、順々に仕切りを動かした場合の最大値が求まる。

heapq.heappush(l, m[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) #仕切りを０から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)になってします。

以下の様な文字列があった場合、二個目のｂで重複が見つかります。そしたら、一個目のｂの次まで、重複リストから外しながら検索していき、次の文字列のスタート位置を一個目のｂの次の文字に設定します。

こうすると、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から最大値を取り出して、半分にしてヒープに戻すことをｍ回。
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でした。
緑がかすかに見えてきた。