精進（2024/5/2） - あるぱかのブログ

競プロ典型90問の★4以下を解く

atcoder.jp

001 - Yokan Party（★4）
002 - Encyclopedia of Parentheses（★3）
003 - Longest Circular Road（★4）
結果

001 - Yokan Party（★4）

リンク：001 - Yokan Party（★4） (atcoder.jp)

概要：長さ $L$ の羊羹の切れ込み $N$ 箇所のうち $K$ 箇所を選んで切ります。その時の最小長さの最大値を答えてね

解法が思いつかなかったので方針だけ解説を見ました。1問目の割りに難しくない？？

最小値の最大化＝答えで二分探索すると良いようです。

方針は以下になります。

（問題文で切る回数は $K$ 回となっていますが、最後に羊羹の右端で切ったことにして $K+1$ 回切ることを目標にします）

$left=1$ 、 $right=L$ と置き $ans = \dfrac{left+right}{2}$ として二分探索を行う
配列 $A$ を順番に見て上記の $ans$ を上回ったところでカットする（カウント＋1）。このとき切った個所の $A_i$ を $head$ に記録しておき次に切るときの長さ計算で使用する。
切り終わったあとに残った切れ端の長さは $L-head$ で計算。この長さが $ans$ 以上ならば切った回数+1する（羊羹の右端で切ったことにする）。
上記の操作を終えて切った数が $K+1$ 回に満たないなら $ans$ が大きすぎるということで $right=ans$ に移動する。 $K+1$ 以上ならまだ余裕があるかもしれないので $left = ans$ とする。
二分探索が終わったときには $left=ans$ になっているなずなので $left$ を出力する。

#001 - Yokan Party（★4）
N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split()))
left = 1
right = L
mx = 0
while left+1 < right:
    ans = (left + right) // 2
    head = 0
    cut = 0
    mn = 10**8
    for i in range(N):
        piece = A[i] - head
        if piece >= ans:
            cut += 1
            head = A[i]
    if L - head >= ans:
        cut += 1
    if cut < K+1:
        right = ans
    if cut >= K+1:
        left = ans
print(left)

提出リンク：提出 #52752757 - 競プロ典型 90 問 (atcoder.jp)

002 - Encyclopedia of Parentheses（★3）

リンク：002 - Encyclopedia of Parentheses（★3） (atcoder.jp)

概要：かっこの始まりと終わりが正しく対応する文字列を辞書順で全て出力してね

かっこの始まり側"("を $0$ 、終わり側")"を $1$ としてビットで表現することを考えます。

（　((())())= $00011011$ になる）

長さ $N$ のビット文字列を作成するためにbin()とzfill()を使いました。

（後から調べるとitertoolsの中のproductで簡単に作れるそうですね）

解法は以下の方針としました。（ $N$ が奇数の場合は明らかに条件を満たさないため、以下は $N$ が偶数として考えていきます）

ビットに変換した文字列の先頭は $0$ なので探索範囲は $\dfrac{2^{N}}{2}$ でOK。
$0$ の数と $1$ の数が同じでなければNG。
文字列を頭から見ていって $1$ の数を数え上げる。その数が今見ている文字数の半分より多くなった時点でNG。
（かっこ始まりよりかっこ閉じが多くなった時点で正しい対応にはならないため）
条件をクリアしたらビットからかっこに復元して出力する。

#002 - Encyclopedia of Parentheses（★3）
N = int(input())
if N % 2 == 1:
    print('')
else:
    ans = []
    for i in range((2**N)//2):
        #ビット文字列先頭の0bを排除、桁数がNになるように0で埋める
        s = bin(i)[2:].zfill(N)
        #文字数の半分が1であるこｔ、末尾が1であることを確認
        if s.count('1') == N//2 and s[-1] == '1':
            sm = 0
            for j in range(N):
                if s[j] == '1':
                    sm += 1
                #j文字目までみたときに1の数が半分を超えていないか確認
                if sm > (j+1)//2:
                    break
            if j == N-1:
                ans.append(s)
    n = len(ans)
    for i in range(n):
        kakko = ''
        for j in range(N):
            if ans[i][j] == '0':
                kakko += '('
            else:
                kakko += ')'
        print(kakko)

提出リンク：提出 #52755443 - 競プロ典型 90 問 (atcoder.jp)

productを使ったパターンはこちらです

提出リンク：提出 #52755895 - 競プロ典型 90 問 (atcoder.jp)

003 - Longest Circular Road（★4）

リンク：003 - Longest Circular Road（★4） (atcoder.jp)

概要： $N$ 個の都市を $N-1$ 本の道でつないでいます。都市の間が一番遠い（通る道の数が最大の）都市同士を直接結ぶ1本の道を追加したときに、その閉ループの道の数を出力してね

都市の数に対して1本少ない数しか道がないので、この時点で閉ループが存在しない状態になっています。

そのため最終的な答えは都市同士の距離最大+1となります。

グラフ、距離の探索ということでBFSを使います。使いましたが都市の数 $N \leq 10^{5}$ なので愚直だと $O(N^{2})$ でTLEしました。

（BFSの計算量は辺の数に依存するので $O(N)$ 、すべての都市を始点として行うので $O(N^{2})$ になる）

これ以上の高速化が思いつかず解説を参照。以下の方針であれば2回のBFSで答えが出せるようです。

どこでもいいので適当な点からBFSして各都市までの距離を出す。
下図では都市1を始点にBFSを行い、都市3と都市5が距離最大であることがわかる。
距離が最大となった都市を始点として再度BFSする。
下図では都市5を次の始点とした場合で、都市4が最も遠く距離＝4であることがわかる。
（都市3を始点にしても同じ）

#003 - Longest Circular Road（★4）
from collections import deque
def bfs(G, start):
    q = deque()
    q.append(start)
    dist = [-1] * N
    dist[start] = 0
    visited = [False] * N
    visited[start] = True
    while q:
        now = q.popleft()
        for nxt in G[now]:
            if visited[nxt]:
                continue
            else:
                q.append(nxt)
                visited[nxt] = True
                dist[nxt] = dist[now] + 1
    return dist
N = int(input())
G = [[] for i in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
mx = 0
#都市0を始点にBFS
dist1 = bfs(G, 0)
for i in range(N):
    if dist1[i] > mx:
        #都市0から最も遠い都市を探す
        mx = dist1[i]
        nxt = i
#最も遠かった都市を始点にもう一度BFS
dist2 = bfs(G,nxt)
#道を1本追加するので+1して答え出力
ans = max(dist2)+1
print(ans)

提出リンク：提出 #52904634 - 競プロ典型 90 問 (atcoder.jp)

結果

勝率（勝ち＝解説見ずにAC）は以下の通り。

★1　0/0

★2　0/0

★3　1/1

★4　0/2