[白俊]26062805-Python 3

2805.木を切る

https://www.acmicpc.net/problem/2805

私のプール-タイムアウト(Python 3)/通過(PyPy 3)

from sys import stdin
import collections

N, M = map(int, stdin.readline().split())
trees = list(map(int, stdin.readline().split()))

total = sum(trees)
trees.sort()
count = collections.Counter(trees)

if total == M:
    print(0)
else:
    idx = 0
    num = N
    if trees[idx] == 0:
        idx += count[0]
        num -= count[0]
    for t in range(1, max(trees)+1):
        if total - num < M:
            break
        total -= num 
        if t == trees[idx]:
            idx += count[t]
            num -= count[t]

    print(t-1)

木を1本ずつ切り落とす
ツリーの全高とMの場合、トリムする必要はありませんのでprint 0
残りは全部揃えます.
同じ高さのツリーを理解するためにCounterを取得
高さゼロのツリーをあらかじめ除外=>idx,num update
1から最大高さまで十分な範囲があります.
木を一つ一つ切り落とす
=>total-トリム可能なツリーの数
Mより小さい場合はカットできないのでbreak
現在の高さが所与の木の高さと同じなら
idx、num update
=>重複する場合はcount値+-
PyPy

JITコンパイラを含み、一般速度はPythonより

速い.
メモリ使用量が

Python

より大きい
したがって、Python 3とPyPy 3は適宜混合して使用すべきである.

でもこの探索を使うのが定式!!

私のプール2-タイムアウト(Python 3)/通過(PyPy 3)

from sys import stdin

N, M = map(int, stdin.readline().split())
trees = list(map(int, stdin.readline().split()))

total = sum(trees)
trees.sort()

l = 0
r = max(trees)

while l <= r:
    m = (l+r) // 2

    tmp = 0
    for i in range(N):
        if trees[i] >= m:
            break
        tmp += trees[i]	# m 보다 작은 값들
    tmp += m*(N-i)	# 현재 높이 * m 보다 큰 값들의 개수
    
    if total - tmp < M:
        r = m-1
    else:
        l = m+1

print(l-1)

二分航法の使用
「mより小さい値」と「現在の高さ*mより大きい値」を合計から減算
値がMより小さい場合は、より小さな値に切り取る必要があるため、rを変更します.
以上の場合は、lを変更してより大きく切り取ります.

他人の解答

from sys import stdin

N, M = map(int, stdin.readline().split())
trees = list(map(int, stdin.readline().split()))

l = 0
r = max(trees)

while l <= r:
    m = (l+r) // 2

    tmp = 0
    for i in range(N):
        if trees[i] >= m:
            tmp += trees[i] - m
    
    if tmp < M:
        r = m-1
    else:
        l = m+1

print(r)

より簡潔な探求
樹木を並べない
剪定可能なツリーを現在の高さで剪定してtmpに保存し、Mと比較するだけです.

2606.ウイルス

https://www.acmicpc.net/problem/2606

私の答え-成功

from sys import stdin
import collections

N = int(stdin.readline())
C = int(stdin.readline())
network = {i:[] for i in range(1, N+1)}

for i in range(C):
    a, b = map(int, stdin.readline().split())
    network[a].append(b)
    network[b].append(a)

computers = [1]*(N+1)
computers[0] = 0

queue = collections.deque([1])

while queue:
    q = queue.popleft()
    computers[q] = 0
    for n in network[q]:
        if computers[n]:
            queue.append(n)

print(computers.count(0)-2)

ストレージネットワーク
コンピュータにワームウイルスに感染したかどうかを格納
0番目のインデックスを使用しないため、0に初期化
1番コンピュータから感染し始めたので、1をキューに格納します
各popは感染=>コンピュータ[q]=0を表す.
接続されたコンピュータをキューにアタッチ
最終感染コンピュータ数は0～2
(2=>無意味な0番目&開始値は1)