AtCoder-ABC214 C - Distribution【Python解答例】

AtCoder Beginner Contest214のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 214 - AtCoder

AtCoder Beginner Contest214 C - Distribution

C - Distribution

問題文

N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。

i(1 ≤ i ≤ N) 番目のすぬけ君は時刻 t に宝石をもらうと Si 単位時間後、すなわち時刻 t+Si にその宝石を (i + 1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 Ti に i 番目のすぬけ君に宝石を渡します。

全ての i(1 ≤ i ≤ N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

・1 ≤ N ≤ 200000
・1 ≤ Si,Ti ≤ 10^9
・入力は全て整数である。

解答例

n = int(input())

S = list(map(int, input().split()))
T = list(map(int, input().split()))

for i in range(2*n):
    T[(i+1) % n] = min(T[(i+1) % n], T[i % n] + S[i % n])

for i in range(n):
    print(T[i])

解説

N人のすぬけ君が それぞれ初めて宝石をもらう時間を答える問題です。

i+1番目のすぬけ君がはじめて宝石をもらうのは、Ti+1時間に高橋くんから宝石をもらうか、i 番目のすぬけ君から宝石をもらうか、どちらか早いほうになります。

したがって、T[i+1]かT[i]+S[i]のうち小さいほうがもとめる時間です。
この小さいほうをT[i+1]に格納していくことで、Tが最も早く宝石をもらえる時間として更新されていきます。

この更新を2周させることでN人のすぬけ君が宝石をもらえる時間が求まります。
1人目のすぬけ君がはじめて宝石をもらえるのは、高橋くんからもらえるT[0]か、N人目のすぬけ君が宝石をもらえる時間のどちらか早いほうです。
N人目のすぬけ君が宝石をもらえる時間を求めるために1周させて、さらに1人目のすぬけ君のはじめて宝石をもらえる時間が2周目に更新されます。
2周させることでTが最も早く宝石がもらえる時間となります。

最後にTの各要素を出力していけばACでした。

ABC214の関連記事はこちら
ebisuke33.hatenablog.com

AtCoder-ABC214 A - New Generation ABC / B - How many?【Python解答例】

AtCoder Beginner Contest214のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 214 - AtCoder

AtCoder Beginner Contest214 A - New Generation ABC

A - New Generation ABC

問題文

AtCoder Beginner Contest は、今回で 214 回目の開催となりました。

今までの AtCoder Beginner Contest において、出題される問題数は次のように変化しました。

・1 回目から 125 回目までは 4 問
・126 回目から 211 回目までは 6 問
・212 回目から 214 回目までは 8 問
N 回目の AtCoder Beginner Contest において出題された問題数を求めてください。

制約

・1 ≤ N ≤ 214
・入力は全て整数である。

解答例

n = int(input())

if 1 <= n <= 125:
    print(4)
elif 126 <= n <= 211:
    print(6)
else:
    print(8)

解説

N回目のコンテストの出題数を答える問題です。

与えられたN回目がどの期間に該当するか条件分けを行い、該当する期間の出題数を出力すればOKです。

AtCoder Beginner Contest214 B - How many?

B - How many?

問題文

a + b + c ≤ S かつ a × b × c ≤ T を満たす非負整数の組 ( a , b , c ) はいくつありますか？

制約

・0≤S≤100
・0≤T≤10000
・S,T は整数である。

解答例

s, t = map(int,input().split())

ans = 0
for i in range(s+1):
    for j in range(s-i+1):
        for k in range(s-i-j+1):
            if i*j*k <= t:
                ans += 1

print(ans)

解説

問題の条件を満たすa, b, c の組み合わせの数を求める問題です。

a + b + c <= 100という制約があるので100までの値で全探索します。

a が i のとき、b は S - i + 1 、c は S - i -j +1の3重ループで探索するとa + b + c <= 100の制約を満たします。

その i , j , k のときにi * j * k <= T であれば、答えのansに1を足します。

ループを抜けたあとにansを出力すればACでした。

ABC214の関連記事はこちら
ebisuke33.hatenablog.com

AtCoder-ABC213 E - Stronger Takahashi【Python解答例】

AtCoder Beginner Contest213のE問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 213 - AtCoder

AtCoder Beginner Contest213 E - Stronger Takahashi

E - Stronger Takahashi

問題文

H 行 W 列の格子状の区画に区切られた街があります。上から i 行目、左から j 列目の区画は、Si,j が . のとき道、# のとき塀です。

高橋君は自分の家から魚屋に買い物に行くことにしました。高橋君の家は街の左上隅の区画にあり、魚屋は街の右下隅の区画にあります。

高橋君は、自分がいる区画から上下左右に隣接する道の区画に移動することができます。街の外に出ることはできません。
塀の区画に移動することはできませんが、高橋君は非常に腕力が強いため、パンチを 1 回繰り出すことで任意の 2×2 の区画内の塀を壊して道にすることができます。

高橋君が魚屋にたどり着くためには、最低何回パンチを繰り出せばよいか求めてください。

制約

・2 ≤ H,W ≤ 500
・H,W は整数
・Si,j は . または #
・S1,1 と SH,W は .

解答例

from collections import deque

# 入力
h, w = map(int,input().split())
maze = []   # 迷路の文字配列
for _ in range(h):
    maze.append(input())

# スタート、ゴール地点
sx = 0
sy = 0
gx = w-1
gy = h-1

# 各座標へ到達するまでに必要なパンチの数（INFで初期化）
INF = int(1e9)
score = [[INF] * w for _ in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]


# スタートからゴールへのscoreを求めるbfs
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    score[sy][sx] = 0 # スタート地点のscoreを0とする

    # キューが空になるまで探索
    while len(que) != 0:
        y, x = que.popleft() # キューの先頭から取り出す
        if y == gy and x == gx: # ゴールなら探索終了
            break
        tmp = score[y][x]
        # (x,y)から4方向に移動 移動後の点は(nx,ny)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            # 移動先が迷路外ならスキップ
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            # 移動先が壁でないならqueの先頭にpush
            if maze[ny][nx] != "#" and score[ny][nx] > tmp:
                score[ny][nx] = tmp
                que.appendleft([ny,nx])
        # パンチをうって移動できる位置に移動 移動後の点は(nx,ny)
        for i in range(-2,3):
            for j in range(-2,3):
                ny = y + i
                nx = x + j
                # 移動先が迷路外やパンチ範囲外の距離ならスキップ
                if nx < 0 or nx >= w or ny < 0 or ny >= h or abs(i)+abs(j)>3:
                    continue
                # パンチ移動後のスコアが低ければ更新しqueの後ろに格納
                if score[ny][nx] > tmp + 1:
                    score[ny][nx] = tmp + 1   # scoreは+1
                    que.append([ny,nx])

    return score[gy][gx]

ans = bfs()
print(ans)

解説

今回はめずらしくE問題まで復習しました。

01BFSという手法で解いています。
同じ手法を勉強したことがありましたので参考までに以前の記事をはっておきます。
ebisuke33.hatenablog.com

基本的にはBFSと同じように進めていきました。
各座標に到達するために必要なパンチの数はINFで初期化したscore配列で管理します。

隣接する4マスへの移動について、移動先が壁でなければ移動前のマスと同じスコアで移動できます。
移動後は移動先のマスをキューの先頭にいれます。

同時に同じマスからパンチを打って移動できる位置についても検討します。
パンチによって移動できるのはx + y = 3の範囲内で、移動先のスコアが移動前のスコア+1より大きければスコアを更新しました。
あわせて移動先のマスをキューの後ろに格納します。

上記のようにBFSを進めていくことで、ゴール地点までに必要なパンチの数を求めることができました。

ABC213の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC213 D - Takahashi Tour【Python解答例】

AtCoder Beginner Contest213のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 213 - AtCoder

AtCoder Beginner Contest213 D - Takahashi Tour

D - Takahashi Tour

問題文

AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から N−1 の番号がついた N−1 個の道路があります。
道路 i を通ると都市 Ai と都市 Bi の間を相互に移動することができます。全ての都市は道路を使って互いに行き来できることが保証されます。

高橋くんは都市 1 を出発し、次のルールで旅をします。

・いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、そのような都市のうち番号が最も小さい都市へ移動する
・そのような都市が存在しないとき
いまいる都市が都市 1 なら旅を終了する
そうでないなら、いまいる都市を初めて訪れたときに直前にいた都市へ移動する
高橋くんが旅の過程で訪れる都市を順に答えてください。

制約

・2 ≤ N ≤ 2×10^5
・1 ≤ Ai,Bi ≤ N
・全ての都市は道路を使って互いに行き来できる

解答例

import sys
sys.setrecursionlimit(10**7) #再帰回数の上限変更

n = int(input())

graph = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

ans = []
def dfs(x,y):
    ans.append(x)
    for next in graph[x]:
        if next != y:
            dfs(next, x)
            ans.append(x)

dfs(1, 0)
print(*ans)

解説

高橋君がたどる都市を順番に答える問題で、オイラーツアーという問題と同じのようです。

DFSするために隣接グラフgraphを持ち、さらに小さい都市から移動するのでgraph[i]をソートします。

DFSは現在の都市xと移動前の都市yを引数として、ソートしたgraph[x]の順番で移動していきました。
移動できる都市があれば次の都市next、および移動前の都市番号として現在の都市番号を渡していきます。
移動できる都市がなくなれば元の都市に戻ります。
移動した都市は順次 ans配列に格納していきました。

DFSが終わったあとにansをアンパックして出力すればACでした。

ABC213の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC213 C - Reorder Cards【Python解答例】

AtCoder Beginner Contest213のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 213 - AtCoder

AtCoder Beginner Contest213 C - Reorder Cards

C - Reorder Cards

問題文

H 行 W 列の格子状に HW 枚のカードが並べられています。i=1,…,N について、上から Ai 行目、左から Bi 列目にあるカードには数 i が書かれており、それ以外の HW−N 枚のカードには何も書かれていません。

これらのカードに対し、以下の 2 種類の操作を可能な限り繰り返します。

・数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
・数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める
操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

・1 ≤ H,W ≤ 10^9
・1 ≤ N ≤ min( 10 ^ 5 , HW)
・1 ≤ Ai ≤ H
・1 ≤ Bi ≤ W
・(Ai , Bi) は相異なる
・入力に含まれる値は全て整数である

解答例

import bisect

h, w, n = map(int,input().split())

A = []
B = []
for i in range(n):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

X = list(set(A))
X.sort()
Y = list(set(B))
Y.sort()

for i in range(n):
    C = bisect.bisect_left(X, A[i]) + 1
    D = bisect.bisect_left(Y, B[i]) + 1
    print(str(C) + " " + str(D))

解説

i番目のカードが問題文にある操作を行ったあとで、どこにあるか答える問題です。

行や列になにも書かれていないカードしかなければ、その行や列を削除できます。
したがって、行であればAiが配列Aのなかで何番目かわかれば答えが求まります。

AやBをset型XやYとして重複を取り除き、さらにリストに戻してソートしました。

ループで各カードの位置AiとBiについてXやYで二分探索を行い、操作後の位置を求めました。
各ループにおいてその位置を出力すればOKでした。

ABC213の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC213 A - Bitwise Exclusive Or / B - Booby Prize【Python解答例】

AtCoder Beginner Contest213のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 213 - AtCoder

AtCoder Beginner Contest213 A - Bitwise Exclusive Or

A - Bitwise Exclusive Or

問題文

0 以上 255 以下の整数 A,B が与えられます。 A xor C=B となる 0 以上の整数 C を求めてください。

なお、そのような C はただ 1 つ存在し、0 以上 255 以下であることが証明されます。

制約

・0 ≤ A,B ≤ 255
・入力に含まれる値は全て整数である

解答例

a, b = map(int,input().split())

c = a ^ b

print(c)

解説

AとBの排他的論理和xorを答える問題です。

Pythonならビット演算子 ^ を使うことでxorを求めることができます。
^ なしなら解けそうにないです (^_^;)

cにxorの結果を代入し、出力すればOKでした。

AtCoder Beginner Contest213 B - Booby Prize

B - Booby Prize

問題文

1,…,N の番号のついた N 人の選手がゲームを行いました。選手 i のスコアは Ai であり、スコアが小さい方が上位になります。

ブービー賞に該当する選手、すなわち、下位から 2 番目の選手の番号を求めてください。

制約

・2≤N≤2×10^5
・1 ≤ Ai ≤ 10^9
・Ai は相異なる
・入力に含まれる値は全て整数である

解答例

n = int(input())

A = list(map(int, input().split()))

B = []
for i in range(n):
    B.append([A[i], i+1])

B.sort(reverse=True)

print(B[1][1])

解説

N人の選手のスコアが与えられるとき下位から2番目のブービー賞の選手の番号を答える問題です。

配列Bにスコアと選手の番号をセットにして スコアをソートします。

下位から2番目の選手の番号はB[1][1]にありますので、これを出力すればACでした。

ABC 213の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

Pythonで取り組む 競プロ典型 90 問 #星4

競技プログラミングの実力アップのためE869129さんが企画された競プロ典型90問に取り組みました。

難易度が★の数で表示されており、★4問題をPythonで解きました。

★4は私にとって難しく解くのにかなり時間がかかりました。
更新も遅くなりますが継続して取り組むよう頑張ります。

競プロ典型90問の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

001 - Yokan Party（★4）

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）

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でした。

競技プログラミングの学習にはこちらの本もおすすめです。

リンク

リンク

リンク

【AtCoder版！蟻本】CODE THANKS FESTIVAL 2017 C - Factory【priority-queue】

AtCoder版！蟻本のpriority-queueの例題としてあげられているABC012 D - バスと避けられない運命をPythonで解いていきます。

リンク

C - Factory

C - Factory

問題文

工場にプレゼントを作る機械が N 台あります。i ( 1 ≦ i ≦ N ) 番目の機械は、最初 ai 秒でプレゼントを 1 個作れます。
しかし、ある機械でプレゼントを 1 個作るたびにその機械のみが劣化して、プレゼントを 1 個作るのにかかる時間が bi 秒増えます。
したがって、i ( 1 ≦ i ≦ N ) 番目の機械で si 個目のプレゼントを作るのに　ai+( si − 1 )×bi 秒かかります。
また、工場に供給される電力が少ないため、複数の機械を同時に動かすことはできません。

イルカはプレゼント K 個をできる限り短い時間で製造したいです。
プレゼントの製造にかかる最小の合計時間を求めてください。

制約

・1 ≦ N ≦ 10^5
・1 ≦ K ≦ 10^5
・1 ≦ ai ≦ 10^9
・0 ≦ bi ≦ 10^9
・入力は全て整数である。

解答例

import heapq

n, k = map(int,input().split())

A = []
B = []
for i in range(n):
    a, b = map(int,input().split())
    heapq.heappush(A, (a, i))
    B.append(b)

ans = 0
for i in range(k):
    tmp, j = heapq.heappop(A)
    ans += tmp
    heapq.heappush(A, (tmp + B[j], j))

print(ans)

解説

K個のプレゼントを作る最短時間を求める問題で、優先度付きキューを用いて解きました。

N台の機会において劣化なしの製造時間Aiを配列Aにいれていきます。

K個のプレゼントを作る時間をansとして、Aの最小値をtmpとして足し合わせていきました。
同時にAに劣化後の製造時間をいれていきます。

このループを抜けたあとにansを出力すればOKでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク