AtCoder-ABC222 C - Swiss-System Tournament【Python解答例】

AtCoder Beginner Contest222のC問題についてPythonの解答例を記事にしていきます。
Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） - AtCoder

AtCoder Beginner Contest222 C - Swiss-System Tournament

C - Swiss-System Tournament

問題文

1 から 2N の番号がついた 2N 人でじゃんけん大会をします。

大会は M ラウンドからなり、各ラウンドは、全ての人が 1 度ずつ参加するような 1 対 1 の N 試合からなります。

i=0,1,…,M について、i ラウンド目の終了時点での順位を次のように決めます。

・i ラウンド目までの勝数が多い方が上位
・i ラウンド目までの勝数が同じときは、番号が小さい方が上位
また、i=1,…,M について、i ラウンド目の各試合の組み合わせを次のように決めます。

・各 k=1,2,…,N について、i−1 ラウンド目終了時点の順位が 2k−1 位の人と 2k 位の人が試合をする
各試合では、対戦する 2 人がそれぞれ 1 度だけ手を出し、勝ち・負け・引き分けのいずれかの結果が発生します。

未来予知ができる高橋君は、人 i が j ラウンド目の試合で出す手が A i,j​ であることを知っています。
A i,j​ は G, C, P のいずれかであり、それぞれグー、チョキ、パーを表します。

M ラウンド目終了時点の順位を求めてください。

制約

・1≤N≤50
・1≤M≤100
・A i,j​ は G, C, P のいずれか

解答例

def judge(a,b):
    if a == "G" and b == "C":
        return True
    elif a == "C" and b == "P":
        return True
    elif a == "P" and b == "G":
        return True
    else:
        return False


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

A = []
for i in range(2*n):
    A.append(input())

rank = []
for i in range(2*n):
    rank.append([200,i])

for j in range(m):
    for i in range(n):
        num1 = rank[2*i][1]
        num2 = rank[2*i+1][1]
        if judge(A[num1][j],A[num2][j]):
            rank[2*i][0] -= 1
        elif judge(A[num2][j],A[num1][j]):
            rank[2*i+1][0] -= 1
    rank.sort()

for i in range(2*n):
    print(rank[i][1]+1)

解説

順位が2k-1位と2k位の人がMラウンドじゃんけんをおこない、Mラウンド終了後の順位を答える問題です。

じゃんけんの勝敗を判定するため、aとbという手のときaが勝てばTrue、引き分けか負けならFalseを返すjudge関数を作成しました。

順位の管理は初期スコアを200としたrank配列で行います。
ラウンドごとにスコアでソートするため、勝てばスコアを減らしていく方式にしました。
（わかりにくいですがスコアが低いほど順位が高い方式です (^_^;)）

あとはラウンドごとに2k-1と2k位の人の手を確認し、どちらかが勝つならば勝った方のスコアを1減らしていきました。
ラウンドが終わるとrank配列をソートし、順位を更新します。

このシミュレーションをMラウンド繰り返し、最後に順位を出力していけばOKでした。

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

AtCoder-ABC222 A - Four Digits / B - Failing Grade【Python解答例】

AtCoder Beginner Contest222のA とB問題についてPythonの解答例を記事にしていきます。
Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） - AtCoder

AtCoder Beginner Contest222 A - Four Digits

A - Four Digits

問題文

0 以上 9999 以下の整数 N が与えられます。

N の先頭に必要なだけ 0 をつけ、4 桁の文字列にしたものを出力してください。

制約

・0≤N≤9999
・N は整数

解答例

n = input()

N = len(n)

if N == 4:
    print(n)
elif N == 3:
    print("0"+n)
elif N == 2:
    print("00"+n)
else:
    print("000"+n)

解説

整数の桁数にあわせて先頭に必要なだけ0をつけて、4桁の文字列にして出力する問題です。

入力を文字列として受け取り、その文字列の長さをNに代入します。

これが入力の桁数になりますので、4桁の場合は0をつけずに、3・2・1桁の場合はそれぞれ1・2・3個0をつけて出力すればACでした。

AtCoder Beginner Contest222 B - Failing Grade

B - Failing Grade

問題文

N 人の学生が試験を受けました。学生には学生 1, 学生 2, …, 学生 N と番号がついていて、学生 i は a i​ 点を取りました。

P 点未満の点数を取った学生は "不可" となり単位を取得できません。 "不可" となった学生の人数を答えてください。

制約

・1≤N≤10 ^5
・1≤P≤100
・0≤a i​ ≤100 (1 ≤ i ≤ N)
・入力はすべて整数である。

解答例

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

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

ans = 0
for i in range(n):
    if A[i] < p:
        ans += 1

print(ans)

解説

制約がきびしくないので全探索で不可の人数を数えます。

i番目の学生の点数はA[i]になるのでA[i] < p（pは判定基準点）となる条件を満たした数だけansに1を足していきます。

p点未満が不可なので<= としないよう注意しました。

ループを抜けて全探索を終えた後にansを出力すればＯＫでした。

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

AtCoder-ABC221 D - Online games【Python解答例】

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

AtCoder Beginner Contest221 D - Online games

D - Online games

問題文

あるオンラインゲームがあり、 N 人のプレイヤーが登録しています。
サービス開始日から 10 ^ 100 日を迎えた今日、 開発者である高橋君がログイン履歴を調べたところ、 i 番目のプレイヤーはサービス開始日を 1 日目として、 A i​ 日目から B i​ 日間連続でログインし、 それ以外の日はログインしていなかったことが判明しました。 すなわち、i 番目のプレイヤーはサービス開始日から、A i​ , A i​ +1 , … , A i​ +B i​ −1 日目に、 かつそれらの日にのみログインしていたことが分かりました。
1≤k≤N をみたす各整数 k について、 サービス開始日から今日までの間で、ちょうど k 人がログインしていた日数を答えてください。

制約

・1≤N≤2×10 ^5
・1≤A i​ ≤10 ^9
・1≤B i​ ≤10 ^9
・入力は全て整数である。

解答例

n = int(input())

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

X.sort()

ans = [0] * (n+1)
cnt = 0
for i in range(len(X)-1):
    cnt += X[i][1]
    tmp = X[i+1][0] - X[i][0]
    ans[cnt] += tmp

ans = ans[1:]
print(*ans)

解説

公式解説をみてACできましたので、公式解説をおすすめします。

ログイン日と人数を管理するための配列Xを用意し、ログイン人数が増えるAi日に[Ai,1]を、人数が減るAi+Bi日に[Ai+Bi,-1]を追加していき、Xをソートします。

ログイン人数を管理するans配列と、現在のログイン人数のcnt変数を用意します。
X[i][0]日目に増減したログイン人数分だけcntを変化させ、そのときのログイン人数を求めました。
このときの人数cnt 人だけログインしている日数をX[i+1][0]-X[i][0]分増加させます。

このループを抜けて、ansのログイン0人分の要素を削除することで、求めたい答えとなりました。

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

AtCoder-ABC221 C - Select Mul【Python解答例】

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

AtCoder Beginner Contest221 C - Select Mul

C - Select Mul

問題文

整数 N が与えられます。N の各桁の数字を取り出して並べ（並べる順序は好きに変えてよい）、2 つの正整数に分離することを考えましょう。

例えば、123 という整数に対しては以下の 6 通りの分離の仕方が考えられます。

・12 と 3
・21 と 3
・13 と 2
・31 と 2
・23 と 1
・32 と 1
なお、ここで分離されたあとの 2 整数に leading zero が含まれていてはなりません。例えば、101 という整数を 1 と 01 の 2 つに分離することはできません。また上述の「正整数に分離する」という条件より、101 を 11 と 0 の 2 つに分離することもできません。

適切に N を分離したとき、分離後の 2 数の積の最大値はいくらになりますか？

制約

・N は 1 以上 10 ^9 以下の整数
・N には 0 でない桁が 2 つ以上含まれる

解答例

n = input()

ans = 0
# bit全探索
for i in range(2**(len(n)-1)):
    tmp1 = []
    tmp2 = []
    # bitに応じてtmp1とtmp2に振り分け
    for j in range(len(n)):
        if (i >> j) & 1:
            tmp1.append(n[j])
        else:
            tmp2.append(n[j])
    # 振り分けされていなければスキップ
    if len(tmp1) == 0 or len(tmp2) == 0:
        continue
    
    # tmp1を最大の値に
    tmp1.sort(reverse=True)
    num1 = ""
    for i in range(len(tmp1)):
        num1 += tmp1[i]
    
    # tmp2を最大の値に
    tmp2.sort(reverse=True)
    num2 = ""
    for j in range(len(tmp2)):
        num2 += tmp2[j]

    # 最大値をメモ
    ans = max(ans,int(num1)*int(num2))

print(ans)

解説

与えられた整数Nを2つに分離し、分離後の数（並び替えてもよい）の積の最大値を求める問題です。

2つに分離する分け方をbit全探索で求めました。

tmp1とtmp2配列を用意し、bitに応じてNを2つに振り分けていきます。
もし、tmp1あるいはtmp2が空なら条件を満たさないのでスキップします。

tmp1が空でなければ、最大の値となるようにソートして順にnum1に足していきました。
tmp2も同様に最大の値にします。

最後にnum1×num2とansを比較し、最大値をメモしていきました。

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

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

AtCoder-ABC221 A - Seismic magnitude scales / B - typo【Python解答例】

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

AtCoder Beginner Contest221 A - Seismic magnitude scales

A - Seismic magnitude scales

問題文

地震のマグニチュードは、その地震のエネルギーの大きさを対数で表した値です。マグニチュードが 1 増える度にエネルギーは約 32 倍になることが知られています。
ここではマグニチュードが 1 増える度に地震のエネルギーがちょうど 32 倍になるとします。このとき、マグニチュード A の地震のエネルギーの大きさはマグニチュード B の地震のエネルギーの大きさの何倍ですか?

制約

・3≤B≤A≤9
・A , B は整数

解答例

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

ans = pow(32,a-b)

print(ans)

解説

マグニチュードAの地震とマグニチュードBの地震のエネルギーでは何倍違うかを答える問題です。

問題文にマグニチュードが1増えるごとにエネルギーは32倍になるとしていますので、答えは32のA-B乗です。

ansにこの値を計算し出力すればOKでした。

AtCoder Beginner Contest221 B - typo

B - typo

問題文

文字列 S, T が与えられます。以下の操作を高々 1 回行うことで、S を T と一致させることができるかを判定してください。

S の隣り合う 2 文字を選び、入れ替える。
なお、上記の操作を一度も行わないことも可能です。

制約

・S, T はそれぞれ英小文字のみからなる、長さ 2 以上 100 以下の文字列
・S の長さと T の長さは等しい

解答例

s = input()

t = input()

flag = True
count = 0
i = 0
while i < (len(s)-1):
    if s[i] == t[i]:
        i += 1
        continue
    elif s[i] != t[i] and s[i] == t[i+1] and t[i] == s[i+1] and count ==0:
        count += 1
        i += 2
        continue
    else:
        flag = False
        break

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

解説

Sの隣り合う文字を最大1回入れ替えることで、Tと一致するかを答える問題です。

Sの文字列の先頭からTと一致しているか、確認していきました。

もしSとTが異なっていたら、次の文字と比較し S[i]とT[i+1]が、T[i]とS[i+1]が一致していたら探索を続けます。
ただし、入れ替えは1回までなのでcount変数を1を足して、入れ替え回数を管理します。

もし2回以上入れ替えの必要があったり、文字を入れ替えても一致しない場合はflagをFalseにして、flagの状況にあわせて答えを出力すればOKです。

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

AtCoder-ABC220 D - FG operation【Python解答例】

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

AtCoder Beginner Contest220 D - FG operation

D - FG operation

問題文

0 以上 9 以下の整数からなる長さ N の数列 A=(A 1​ ,…,A N​ ) があり、この順に左から右に並んでいます。

数列の長さが 1 になるまで、操作 F または操作 G を繰り返し行います。

操作 F ：左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x+y)%10 を挿入する
操作 G ：左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x×y)%10 を挿入する
なお、a%b は a を b で割った余りを意味します。

K=0,1,…,9 について、以下の問題に答えてください。

操作手順としてあり得るものは 2 N−1 通りありますが、このうち最終的に残る値が K となる操作手順は何通りありますか？
ただし答えは非常に大きくなる可能性があるので、998244353 で割った余りを求めてください。

制約

・2≤N≤10 ^5
・0≤A i​ ≤9
・入力は全て整数

解答例

mod = 998244353

n = int(input())

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

dp = [[0]*10 for _ in range(n+1)]

dp[0][A[0]] = 1
for i in range(n-1):
    y = A[i+1]
    for j in range(10):
        if dp[i][j] != 0:
            x = j
            xf = (x+y) % 10
            xg = (x*y) % 10

            dp[i+1][xf] = (dp[i+1][xf] + dp[i][x]) % mod
            dp[i+1][xg] = (dp[i+1][xg] + dp[i][x]) % mod

for i in range(10):
    print(dp[n-1][i])

解説

操作Fと操作Gを数列Aが最後に1項だけ残るまで繰り返したとき、最後の値がKになる操作手順がそれぞれ何通りか答える問題です。

動的計画法DPを用いて解きました。

dp[i][j]：i回操作を行ったとき最も左の値がjとなる操作手順のパターン数 としました。

初期条件として数列Aの左端がA[0]なのでdp[0][A[0]を1通りとします。

この条件で左からN-1までループさせました。
yはA[i+1]で、dp[i][j]が0でないときのみx = jとして処理を続けます。

処理Fを行ったときの値をxf、処理Gはxgとして計算します。
処理Ｆについてはdp[i+1][xf] = (dp[i+1][xf] + dp[i][x]) % modと、処理Ｇはdp[i+1][xg] = (dp[i+1][xg] + dp[i][x]) % modと更新していきました。

このループを抜けたあとに各Ｋの値を出力すればＡＣです！

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

AtCoder-ABC220 C - Long Sequence【Python解答例】

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

AtCoder Beginner Contest220 C - Long Sequence

C - Long Sequence

問題文

長さ N の正整数のみからなる数列 A=(A 1​ ,…,A N​ ) があります。
A を 10 ^ 100 回連結した数列を数列 B とします。

B の項を前から順に足したとき、和が初めて X を超えるのは何項目まで足したときですか？
すなわち、以下の式を満たす最小の整数 k を求めてください。

i=1
∑ ​ B i​ >X
k

制約

・1≤N≤10 ^5
・1≤A i​ ≤10 ^9
・1≤X≤10 ^18
・入力は全て整数

解答例

n = int(input())

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

x = int(input())

sum_a = 0
for i in range(n):
    sum_a += A[i]

ans = 0
ans += n * (x // sum_a)
SUM = sum_a * (x // sum_a)
i = 0
while x >= SUM:
    SUM += A[i]
    ans += 1
    i += 1

print(ans)

解説

数列Aの10^100回連結した数列Bの項を左から順に足していき、その和がXを超えるのが何項目か答える問題です。

1項ずつ最初から順番に足していくとTLEになりますので、数列Aの総和sum_aを求めて計算量を少なくしました。

答えとなる項数をansと置き、Xをsum_aで割った商にNをかけた値を代入します。
もとめる項数ansはこの値から数列Aの項数以下の範囲にあることになります。

数列Bを左から足していった総和SUMも数列Aの総和sum_aにXをsum_aで割った商をかけた値なので同時に計算しておきました。

あとはSUMがXを超えるまでwhile文でSUMに項を足し続けます。
足すたびにansに1を足し、SUMがXを超えたときのansを出力すればOKでした。

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

AtCoder-ABC220 A - AtCoder Quiz 2 / B - Base K【Python解答例】

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

AtCoder Beginner Contest220 A - Find Multiple

A - Find Multiple

問題文

A 以上 B 以下であるような C の倍数を、1 つ出力してください。

条件を満たす数が存在しない場合は -1 を出力してください。

制約

・1≤A≤B≤1000
・1≤C≤1000
・入力は全て整数

解答例

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

ans = c * (b // c)

if ans >= a:
    print(ans)
else:
    print(-1)

解説

A以上B以下のCの倍数が存在すれば出力する問題です。

B以下の最大のCの倍数は、BをCで除算した商にCをかけた値でansとしました。

これがA以上であればansを出力し、そうでなければ求める値は存在しないので-1を出力すればACです！

AtCoder Beginner Contest220 B - Base K

B - Base K

問題文

整数 A,B が K 進法表記で与えられます。
A×B を 10 進法表記で出力してください。

制約

・2 ≤ K ≤ 10
・1 ≤ A,B ≤ 10 ^5
・A,B は K 進法表記で与えられる

解答例

k = int(input())

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

a_10 = int(str(a),k)
b_10 = int(str(b),k)

ans = a_10 * b_10

print(ans)

解説

K進数のA,Bをかけた値を10進数表記で答える問題です。

int(str(a),k)でk進数のaを10進数に変換することができます。
これでa_10,b_10にk進数のa, b をそれぞれ代入しました。

ansにa_10×b_10を計算した値をいれて出力すればOKでした。

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