Pythonで取り組む 競プロ典型 90 問 #星4
競技プログラミングの実力アップのためE869129さんが企画された競プロ典型90問に取り組みました。
難易度が★の数で表示されており、★4問題をPythonで解きました。
★4は私にとって難しく解くのにかなり時間がかかりました。
更新も遅くなりますが継続して取り組むよう頑張ります。
競プロ典型90問の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
001 - Yokan Party（★4）
問題文
左右の長さが L [cm] のようかんがあります。 N 個の切れ目が付けられており、左から i 番目の切れ目は左から Ai [cm] の位置にあります。
あなたは N 個の切れ目のうち K 個を選び、ようかんを K+1 個のピースに分割したいです。そこで、以下の値を スコア とします。
・K+1 個のピースのうち、最も短いものの長さ（cm 単位）
スコアが最大となるように分割する場合に得られるスコアを求めてください。
制約
・1 ≤ K ≤ N ≤ 100000
・0 < A1 < A2 < ⋯ < AN < L ≤ 10^9
・入力はすべて整数
解答例
n, l = map(int,input().split()) k = int(input()) A = list(map(int, input().split())) # すべてx以上の長さで切れるか判定 def judge(x): # 切れた個数 cnt = 0 # 最後に切った位置 sum_len = 0 for i in range(n): # 長さがxを超え、残りの長さがx以上なら切る if A[i] - sum_len >= x and l - A[i] >= x: cnt += 1 sum_len = A[i] if cnt >= k: return True else: return False # 二分探索で最も短い長さを探索 left = -1 right = l+1 while abs(right - left) > 1: mid = (right + left) // 2 if judge(mid): left = mid else: right = mid print(left)
解説
最小値の最大化には二分探索が有効な場面が多いようで、この問題も二分探索を用いて解きました。
最も短いようかんの長さの候補を二分探索していきます。
候補をjudge関数で実現可能か判定します。
judge関数では前回切断した箇所からx以上で、切断したとき残る長さがx以上なら切断することを貪欲に行いました。
切る個数がK + 1ならTrue、そうでなければFalseを返します。
もしTrueならleftをmidに、Falseならrightをmidにして二分探索を進めていきます。
探索が終えたときのleftが求める答えとなりました。
003 - Longest Circular Road（★4）
003 - Longest Circular Road（★4）
問題文
N 個の都市があり、それぞれの都市に 1 から N までの番号が付けられています。 また、N−1 本の道路があり、i 本目 (1 ≤ i ≤ N−1) の道路は都市 Ai と都市 Bi を双方向に結んでいます。 どの都市の間も、いくつかの道路を通って移動可能なものとなっています。
さて、あなたは整数 u, v (1 ≤ u < v ≤ N) を自由に選び、都市 u と都市 v を双方向に結ぶ道路を 1 本だけ新設することができます。そこで、以下で定められる値を スコア とします。
・同じ道を 2 度通らずにある都市から同じ都市に戻ってくる経路における、通った道の本数 （この値はただ 1 つに定まる）
スコアとして考えられる最大の値を出力してください。
制約
・3 ≤ N ≤ 100000
・1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ N−1)
・どの都市の間も、いくつかの道路を通って移動可能
・与えられる入力は全て整数
解答例
import collections # xからの最も遠い距離と頂点を求める幅優先探索 def bfs(x): # 頂点xからの距離 dist = [-1 for _ in range(n)] # 頂点xから最も遠い距離 max_dist = 0 # 頂点xから最も遠い頂点 max_point = 0 que = collections.deque() que.append(x) dist[x] = 0 while len(que) != 0: p = que.popleft() tmp = dist[p] + 1 for i in graph[p]: if dist[i] != -1: continue elif tmp > max_dist: max_point = i que.append(i) dist[i] = tmp max_dist = max(max_dist, tmp) return max_point, max_dist n = int(input()) graph = [[] for _ in range(n)] for i in range(n-1): a, b = map(int,input().split()) graph[a-1].append(b-1) graph[b-1].append(a-1) # 頂点0から最も遠い頂点point point,_ = bfs(0) # 頂点pointから最も遠い距離far _,far = bfs(point) # 答えはfar + 1 ans = far + 1 print(ans)
解説
木構造のグラフにおいて辺を１つ加えて閉路を形成し、その最大の長さを答える問題です。
この最大の長さは、適当な頂点から最も遠い頂点Aを求め、さらに頂点Aから最も遠い頂点Bまでの長さを求め、その値に1を足した値です。
この値を幅優先探索で求めました。
頂点0から最も遠い頂点pointをまずBFSで求めます。
このpointから最も遠い頂点までの距離farを、再度BFSすることで求めました。
解答はfarに1を足した値になりますので、それを出力すればＯＫでした。
008 - AtCounter（★4）
問題文
英小文字のみからなる、長さ N の文字列 S が与えられます。
S の i 文字目を si とします。
S から 0 個以上の文字を取り出す方法は 2N 通りありますが、そのうち以下の条件を満たすものは何通りあるでしょうか？答えは非常に大きくなる可能性があるため、答えを 10^9+7 で割った余りを出力してください。
・取り出した文字を順番を変えずに結合して出来た文字列が "atcoder" となる
ただし「文字を取り出す方法」は、どちらか一方でのみ取り出しているような文字 si (1 ≤ i ≤ N) が少なくとも一つ存在する場合に区別されます。
制約
・1 ≤ N ≤ 100,000
・|S|=N
・文字列 S は英小文字のみからなる
解答例
n = int(input()) S = input() T = "atcoder" mod = 10**9 + 7 # dp[a][b]：Sがa文字目のときatcoderのb文字目までの選び方 dp = [[0 for _ in range(n+1)] for _ in range(len(T)+1)] for k in range(n+1): dp[0][k] = 1 for i in range(n): for j in range(len(T)): if S[i] == T[j]: dp[j+1][i+1] = (dp[j][i+1] + dp[j+1][i]) % mod else: dp[j+1][i+1] = dp[j+1][i] print(dp[len(T)][n])
解説
動的計画法で求める組み合わせの数を求めます。
dp[a][b]をSのa+1文字目まででT = "atcoder"のb+1文字目までを作る選び方の数としました。
初期条件は2つあり、a = 0 のときはSから1文字も使っていないときにTの文字を選択することができないので0通りとします。
b= 0 のときはTから0文字目まで選択するのはどれも選んでいない1通りとしました。
S[i] != T[j]のとき選び方は変わらないのでdp[j+1][i+1] = dp[j+1][i]です。
S[i] == T[j]のとき、S[i]を使用する場合と使用しない場合を考えます。
使用する場合は、Sのi-1文字目まででTのj-1文字目までの文字列をつくる数と同じです。
使用しない場合は、S[i] != T[j]と同様に選び方が変わりません。
したがって、この2つを足し合わせて更新しました。
dpの更新が終わり、dp[len(T)][n]を出力すればACでした。
競技プログラミングの学習にはこちらの本もおすすめです。
リンク
リンク
リンク
