AtCoder-ABC212 D - Querying Multiset【Python解答例】

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

AtCoder Beginner Contest212 D - Querying Multiset

D - Querying Multiset

問題文

高橋君は何も書かれていないたくさんのボールと 1 つの袋を持っています。 最初、袋は空で、高橋君は Q 回の操作を行います。 それぞれの操作は以下の 3 種類のうちのいずれかです。

・操作 1 : まだ何も書かれていないボール 1 つに整数 Xi を書き込み、袋に入れる。
・操作 2 : 袋に入っているすべてのボールについて、そこに書かれている数を、それに Xi を加えたものに書き換える。
・操作 3 : 袋に入っているボールのうち書かれている数が最小のもの（複数ある場合はそのうちの 1 つ）を取り出し、そこに書かれている数を記録する。その後、そのボールを捨てる。
1 ≤ i ≤ Q について i 回目の操作の種類 Pi および操作 1 , 2 における Xi の値が与えられるので、操作 3 において記録された数を順に出力してください。

制約

・1 ≤ Q ≤ 2×10^5
・1 ≤ Pi ≤ 3
・1 ≤ Xi ≤ 10^9
・入力は全て整数である。
・Pi=3 であるような i が 1 つ以上存在する。
・Pi=3 であるとき、 i 回目の操作の直前の時点で、袋には 1 つ以上のボールが入っている。

解答例

import heapq

q = int(input())

box = []
# boxを優先度付きキューに
heapq.heapify(box)

sum = 0
for i in range(q):
    Q = list(map(int, input().split()))
    if Q[0] == 1:
        heapq.heappush(box, Q[1]-sum)
    elif Q[0] == 2:
        sum += Q[1]
    else:
        tmp = heapq.heappop(box)
        print(tmp + sum)

解説

優先度付きキューを使って解くことができました。

p=2のときにsumにxを足し合わせて累積和をとります。

p=1のときに配列boxにxからsumを引いた値を入れていることにしました。

これによりp=3のときは単純にboxの最小値を取り出せばいいことになります。

出力するときはsumを足した値を解答すればOKでした。

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

AtCoder-ABC212 C - Min Difference【Python解答例】

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

AtCoder Beginner Contest212 C - Min Difference

C - Min Difference

問題文

それぞれ N 個、M 個の正整数からなる 2 つの数列 A=(A1,A2,…,AN) と B=(B1,…,BM) が与えられます。

それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差の最小値、すなわち、 min1≤i≤N min1≤j≤M |Ai−Bj| を求めてください。

制約

・1≤N,M≤2×10^5
・1≤Ai≤10^9
・1≤Bi≤10^9
・入力は全て整数である。

解答例

import bisect

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

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

B.sort()

ans  = int(1e9)
for i in range(n):
    point = bisect.bisect_left(B, A[i])
    if point != 0:
        tmp = abs(A[i] - B[point-1])
    else:
        tmp = abs(A[i] - B[point])
    if point != len(B):
        tmp2 = abs(A[i] - B[point])
    else:
        tmp2 = abs(A[i] - B[point-1])

    ans = min(ans, tmp)
    ans = min(ans, tmp2)

print(ans)

解説

ふたつの数列AとBから１つずつ要素を選んだとき、値の差の最小値を答える問題です。

Bをソートして、Aの各要素の挿入点を二分探索で求めました。

挿入点pointの前後の要素との差が最小値となり得るのでtmpおよびtmp2として計算しました。

この最小値をansとして更新することで求める答えとなりました。

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

AtCoder-ABC212 A - Alloy / B - Weak Password【Python解答例】

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

AtCoder Beginner Contest212 A - Alloy

A - Alloy

問題文

高橋くんは A グラムの純金と B グラムの純銀 ( 0 ≤ A , B , 0 < A + B ) をよく溶かした上で混ぜ合わせ、新たな金属を生成しました。

生成された金属は「純金」「純銀」「合金」のいずれでしょうか？

なお、生成された金属は
・0 < A かつ B = 0 なら「純金」
・A = 0 かつ 0 < B なら「純銀」
・0 < A かつ 0 < B なら「合金」
であるとみなします。

制約

・0 ≤ A , B ≤ 100
・0 < A + B
・A,B は整数

解答例

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

if A > 0 and B == 0:
    print("Gold")
elif A == 0 and B > 0:
    print("Silver")
else:
    print("Alloy")

解説

Aグラムの純金とBグラムの純銀を混ぜるとき、混ぜた金属が何になるか答える問題です。

純金と純銀の重さA,Bを受け取ったあと、問題文の通りに条件分けを行い答えを出力するとOKです。

AtCoder Beginner Contest212 B - Weak Password

B - Weak Password

問題文

4 桁の暗証番号 X1X2X3X4 が与えられます。 番号は先頭の桁が 0 であることもあり得ます。 暗証番号は以下のいずれかの条件をみたすとき弱い暗証番号と呼ばれます。

・4 桁とも同じ数字である。
・1≤i≤3 をみたす任意の整数 i について、 Xi+1 が、 Xi の次の数字である。 ただし、 0≤j≤8 について j の次の数字は j+1 であり、 9 の次の数字は 0 である。

与えられた暗証番号が弱い暗証番号ならば Weak を、そうでないならば Strong を出力してください。

制約

・0≤X1,X2,X3,X4≤9
・X1,X2,X3,X4 は整数である。

解答例

x = input()

flag = True
if x[0] == x[1] and x[1] == x[2] and x[2] == x[3]:
    flag = False

for i in range(3):
    if int(x[i]) >= 0 and int(x[i]) <= 8 and int(x[i]) == int(x[i+1]) - 1:
        continue
    elif int(x[i]) == 9 and int(x[i+1]) == 0:
        continue
    else:
        break
else:
    flag = False

if flag:
    print("Strong")
else:
    print("Weak")

解説

4桁の暗証番号が"弱い"パスワードか答える問題です。

flagで弱いパスワードか管理しました。

2つ判別を行い、ひとつめは4桁がすべて同じ数字かどうかを確認しました。
もし、4桁とも同じ数字ならflagをFalseにします。

次はXi+1がXiの次の数字かどうかです。
ループ文で次の数字Xi+1から1を引いた値とXiが等しいか判定し、連続した数字でなければループをbreakします。
berakできないままループが終われば、4桁とも連続した数字であることがわかりますので、同じくflagをfalseにしました。

最後にflagに合わせて答えを出力すればＯＫでした。

AtCoder-ABC211 D - Number of Shortest paths 【Python解答例】

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

AtCoder Beginner Contest211 D - Number of Shortest paths

D - Number of Shortest paths

問題文

AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。

道路 i を通ると都市 Ai と都市 Bi の間を双方向に 1 時間で移動することができます。

都市 1 から都市 N へ最も早く移動することができる経路は何通りありますか？
答えは非常に大きくなる可能性があるので (10^9+7) で割ったあまりを求めてください。

制約

・2 ≤ N ≤ 2×10^5
・0 ≤ M ≤ 2×10^5
・1 ≤ Ai < Bi ≤ N
・(Ai,Bi) は相異なる
・入力に含まれる値は全て整数である

解答例

import collections

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

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

mod = 10**9 + 7

que = collections.deque()
dist = [-1] * n
cnt = [0] * n
dist[0] = 0
cnt[0] = 1
que.append(0)

while len(que) != 0:
    p = que.popleft()
    for i in graph[p]:
        if dist[i] == -1:
            dist[i] = dist[p] + 1
            que.append(i)
            cnt[i] = cnt[p]
        elif dist[i] == dist[p] + 1:
            cnt[i] += cnt[p]
            cnt[i] %= mod

print(cnt[n-1])

解説

公式解説を見て解くことができました。

幅優先探索で最短距離を表すdist配列と経路の数を表すcnt配列を更新していきます。

道路によってつながっている都市AiとBiは、隣接リストgraphとして管理しました。

distの初期条件はスタート地点のdist[0]を0とします。
cntの初期条件はスタート時点では1通りなのでcnt[0]を1としました。

この条件で幅優先探索を行います。
キューからpopした都市から遷移できる都市iが未到達の場合は、最短距離を表すdist[i]に遷移前の距離に1を足して更新します。
経路の数cntは遷移前の数と同じ値で更新しました。

遷移できる都市jが到達済みであっても、最短距離distの値が同じであればcnt[j]に遷移前の数を足し合わせることで最短経路の数を更新していきました。

幅優先探索を行うことで都市Nまでの最短経路の数cnt[n-1]が求まりますので、これを出力すればOKでした。

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

AtCoder-ABC211 C - chokudai 【Python解答例】

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

AtCoder Beginner Contest211 C - chokudai

C - chokudai

問題文

文字列 S が与えられます。
このうち 8 文字を選び下線を引き、下線を引いた文字が左から順に c , h , o , k , u , d , a , i となるようにする方法は何通りありますか？
ただし答えは非常に大きくなる可能性があるので、(109+7) で割った余りを出力してください。

制約

・8≤|S|≤10^5
・S は英小文字からなる

解答例

S = input()

tar = "chokudai"

mod = 10**9 + 7

dp = [[0 for _ in range(len(tar)+1)] for _ in range(len(S)+1)]

for i in range(len(S)+1):
    dp[i][0] = 1

for i in range(len(S)):
    for j in range(len(tar)):
        if S[i] != tar[j]:
            dp[i+1][j+1] = dp[i][j+1]
        if S[i] == tar[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i][j]) % mod

print(dp[len(S)][8])

解説

動的計画法で答えを求めます。

dp[i][j]：Sのi番目の文字まででtar = "chokudai"のj文字目までをつくる組み合わせの数とおきます。

初期条件としてj = 0のときはd[i][0] =1とします。
また、i = 0ときはchokudaiから選択しようがないのでdp[0][j] =0とします。

この初期条件でiとjの2重ループでdpを更新していきます。

S[i] != tar[j]のとき、場合の数は増えることがありませんのでdp[i+1][j+1] = dp[i][j+1]としました。
S[i] = tar[j]のときは、Sのi番目の文字を使用しない場合は上記と同じでdp[i][j+1]通りです。
使用する場合は、Sがi-1番目の文字まででtarのj-1番目の文字をつくる組み合わせの数と同じdp[i][j]なのでこの２つの値を足し合わせます。

このようにdpを更新していき、最後にdp[len(S)][8]を出力すればＯＫでした。

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

AtCoder-ABC211 A - Blood Pressure / B - Cycle Hit【Python解答例】

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

AtCoder Beginner Contest211 A - Blood Pressure

A - Blood Pressure

問題文

収縮期血圧 A と拡張期血圧 B が与えられます。
平均血圧 C を求めてください。
ただし、平均血圧は以下のように定義されるとします。

C=A−B / 3+B

制約

・50≤B≤A≤300
・入力に含まれる値は全て整数である

解答例

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

ans = b + (a - b) / 3

print(ans)

解説

問題文の計算式の通りに平均血圧を答える問題です。

入力を受け取ってansに計算結果を代入します。

除算の計算の順序に注意して演算を行えばOKでした。

AtCoder Beginner Contest211 B - Cycle Hit

B - Cycle Hit

問題文

4 つの文字列 S1,S2,S3,S4 が与えられます。
この中に、H , 2B , 3B , HR がそれぞれ 1 つずつあるか判定してください。
ただし、全ての Si は H , 2B , 3B , HR のいずれかと一致します。

制約

・Si は H , 2B , 3B , HR のいずれかと一致する

解答例

S = []
for i in range(4):
    S.append(input())

S.sort()

flag = True
if S[0] != "2B":
    flag = False
if S[1] != "3B":
    flag = False
if S[2] != "H":
    flag = False
if S[3] != "HR":
    flag = False

if flag:
    print("Yes")
else:
    print("No")

解説

与えられる4つの文字列にH , 2B , 3B , HRがひとつずつあるか答える問題です。

入力をすべて配列Sに格納し、ソートします。

もし、サイクルヒットの条件が満たされていれば、2B,3B,H,HRの順にリストに格納されているので、順番に確かめていきます。

どこかで文字列が異なっていたらflagをFalseにして未達成を記録しておきます。

最後にflagにあわせて出力すればOKです。

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

AtCoder-ABC210 D - National Railway【Python解答例】

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

AtCoder Beginner Contest210 D - National Railway

D - National Railway

問題文

高橋王国は H 行 W 列のグリッドで表されます。北から i 行目、西から j 列目のマスを (i,j) で表します。

このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。
鉄道建設は以下の 2 つのステップからなります。

・まず、2 つの異なるマスを選び、それぞれに駅を建設する。マス (i,j) に駅を建設すると Ai,j 円の費用がかかる。
・その後、建設した 2 つの駅を結ぶ線路を建設する。2 つの駅がマス (i,j) とマス (i′,j′) にあるとき、これらを結ぶ線路の建設をすると C×(|i−i′|+|j−j′|) 円の費用がかかる。（ここで、|x| は x の絶対値を表す。）
高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています。
鉄道建設にかかる費用として考えられる最小値を出力してください。

制約

・2≤H,W≤1000
・1≤C≤10^9
・1≤Aij≤10^9
・入力はすべて整数

解答例

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

A = []
for i in range(h):
    array = list(map(int, input().split()))
    A.append(array)

INF = int(1e18)

ans = INF

for _ in range(2):
    # dp[i][j]はi,jのときのAij - c*(i+j)の最小値
    dp = [[INF for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
            ans = min(ans, A[i][j] + c*(i+j) + dp[i][j])

            dp[i][j] = min(dp[i][j], A[i][j] - c*(i+j))

    A.reverse()        

print(ans)

解説

こちらを参考にして書いたコードです。

リンク先の解説を参照したほうが良いと思いますが、一応こちらでも簡単に記載します。

絶対値を外すためマスi1,j1とi2,j2を考えるとき、i1>i2およびj1>j2の場面で考えることとしました。
このとき建設費用はA[i1][j1] + c*(i1 + j1) + A[i2][j2] - c*(i2 + j2)と変形できます。

このA[i2][j2] - c*(i2 + j2)の最小値ををdp配列に記録しながら探索を進め、dp配列を利用して建設費用を各マスで計算します。

この建設費用の最小値をansに代入することで、求める答えとなりました。

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

AtCoder-ABC210 C - Colorful Candies【Python解答例】

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

AtCoder Beginner Contest210 C - Colorful Candies

C - Colorful Candies

問題文

N 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色 1、色 2、…、色 10^9の、10^9 種類の色のうちいずれかの色をしています。
i=1,2,…,N について、左から i 番目のキャンディの色は色 ci です。

高橋君は並んでいるキャンディのうち、連続して並んだ K 個のキャンディをもらうことができます。
すなわち、1≤i≤N−K+1 を満たす整数 i を選んで、 左から i 番目、i+1 番目、i+2 番目、…、i+K−1 番目のキャンディをもらうことができます。

高橋君はいろいろな色のキャンディを食べたいので、 もらうキャンディに含まれる色の種類数が多いほどうれしい気持ちになります。
高橋君がもらうキャンディに含まれる色の種類数の最大値を出力してください。

制約

・1≤K≤N≤3×10^5
・1≤ci≤10^9
・入力はすべて整数

解答例

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

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

color = {}

for i in range(n):
    color.setdefault(C[i], 0)

tmp = 0
for i in range(k):
    if color[C[i]] == 0:
        tmp += 1
    color[C[i]] += 1

ans = tmp
for i in range(n-k):
    if color[C[i]] == 1:
        tmp -= 1
    color[C[i]] -= 1
    if color[C[i+k]] == 0:
        tmp += 1
    color[C[i+k]] += 1
    ans = max(ans, tmp)

print(ans)

解説

左からi番目のキャンディが色Ciとして、連続したK個のキャンディをもらうときに最大何色のキャンディをもらえるか答える問題です。

キャンディの色を辞書colorで管理していきます。

まず、キャンディの色をすべて辞書にキーとして登録しました。
tmpをある区間においてK個のアメをもらときの色の数とします。
ある色においてcolorの要素の数を調べて、要素数が0の新しい色が加わる場合はtmpに1を足します。
要素数が1の色が区間から抜ける場合はtmpから1を引きます。
このようにtmpを管理することですべての区間における色の数を把握することができました。

最後にtmpの最大値ansを解答することでACでした。

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