AtCoder-ABC227 A - Last Card / B - KEYENCE building【Python解答例】
キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)のA とB問題についてPythonの解答例を記事にしていきます。
KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) - AtCoder
AtCoder Beginner Contest227 A - Last Card
問題文
1,2,…,N の番号のついた N 人の人に合計 K 枚のカードを配ります。
人 A から始めて 人 A,A+1,A+2,…,N,1,2,… の順に 1 枚ずつカードを配るとき、最後のカードは誰に配られるでしょうか？
厳密には、人 x(1≤x
制約
・1≤N,K≤1000
・1≤A≤N
・入力は全て整数
解答例
n, k, a = map(int,input().split()) ans = (k+a-1) % n if ans == 0: print(n) else: print(ans)
解説
N人の人に対してK枚のカードをA番目の人から一枚ずつ配るときに、何番目の人に最後のカードが配られるか答える問題です。
K + A - 1をNで割った余りが答えansになりますが、番号が0番の人はいないのでansが0ときはN番目の人が答えとなります。
この結果を出力すればOKでした。
AtCoder Beginner Contest227 B - KEYENCE building
問題文
1 から N の番号がついた N 人の人がいます。
人 i はキーエンス本社ビルの建築面積を S i 平方メートルであると予想しました。
キーエンス本社ビルは下図のような形をしています。ただし、a,b はある 正の整数 です。
つまり、キーエンス本社ビルの建築面積は 4ab+3a+3b 平方メートルと表されます。
N 人のうち、この情報のみによって、予想した面積が確実に誤りであるとわかる人数を求めてください。
制約
・1≤N≤20
・1≤S i ≤1000
・入力に含まれる値は全て整数である
解答例
n = int(input()) S = list(map(int, input().split())) ans = 0 for i in range(n): flag = False for a in range(1,S[i]): for b in range(1,S[i]): if 4*a*b + 3*a + 3*b == S[i]: flag = True if not flag: ans += 1 print(ans)
解説
Siを満たす正の整数a,bが存在するか全探索する問題です。
N人の予想をひとつずつ調べます。
aとbが存在する場合、その値はS[i]以下なので探索範囲はそこまでとします。
S[i]を満たす組み合わせがあればflagをTrueにして管理し、a,bの探索後もflagがFalseのままであればansに1を足しました。
ループを抜けたあとにansを出力すればACです。
AtCoder-ABC226 A - Round decimals / B - Counting Arrays【Python解答例】
AtCoder Beginner Contest226のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 226 - AtCoder
AtCoder Beginner Contest226 A - Round decimals
問題文
小数第三位までで表すことのできる実数 X が、小数第三位まで入力されます。
X を小数第一位で四捨五入した結果として得られる整数を出力してください。
制約
・0≤X<100
・X は小数第三位までで表現可能である。
・X は小数第三位まで与えられる。
解答例
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN x = float(input()) ans = Decimal(str(x)).quantize(Decimal('0'), rounding=ROUND_HALF_UP) print(ans)
解説
小数第三位まで与えられたとき、小数第一位で四捨五入した結果を答える問題です。
Pythonで四捨五入をするためにdecimalモジュールをインポートします。
解答例のコードで小数第一位を四捨五入することができ、ansを出力してACでした。
AtCoder Beginner Contest226 B - Counting Arrays
問題文
1 から N までの番号がついた N 個の数列が与えられます。
数列 i は、長さが L i で j (1≤j≤L i ) 番目の要素が a i,j であるような数列です。
数列 i と 数列 j は、 L i =L j かつすべての k (1≤k≤L i ) に対して a i,k =a j,k が成り立つ時に同じであるとみなします。
同じ数列は 1 種類として数えるとき、数列 1 から 数列 N の中に全部で何種類の数列がありますか？
制約
・1≤N≤2×10 ^5
・1≤L i ≤2×10 ^5 (1≤i≤N)
・0≤a i,j ≤10 ^9 (1≤i≤N,1≤j≤L i )
・すべての数列の要素の個数の和、すなわち ∑ i=1N L i は 2×10 ^5 を超えない。
・入力はすべて整数である。
解答例
n = int(input()) A = set() for i in range(n): array = input() A.add(array) print(len(A))
解説
N個の数列が与えられたとき異なる数列が何個あるか答える問題です。
数列を文字列で受け取り、setを使うことで同じ数列を除去していきます。
すべての重複を確認したあとで、Aの長さ（個数）を出力すればOKでした。
AtCoder-ABC225 A - Distinct Strings / B - Star or Not【Python解答例】
AtCoder Beginner Contest225のA とB問題についてPythonの解答例を記事にしていきます。
UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) - AtCoder
AtCoder Beginner Contest225 A - Distinct Strings
問題文
英小文字のみからなる長さ 3 の文字列 S が与えられます。
S の各文字を並び替えて得られる文字列は、何種類ありますか？
制約
・S は英小文字のみからなる長さ 3 の文字列
解答例
S = input() if S[0] == S[1] and S[1] == S[2]: print(1) elif S[0] != S[1] and S[1] != S[2] and S[2] != S[0]: print(6) else: print(3)
解説
3文字の英子文字から何通りの文字列がつくれるか答える問題です。
3文字のなかに同じ文字があるかで場合分けを行いました。
3文字がすべて同じ文字の場合は、できる文字列は1通りだけです。
すべて文字が異なれば、文字列は6通りできます。
そうでなければ、おなじ文字が2つの場合になりますので、そのときは3通りです。
この場合分けで答えを出力すればOKでした。
AtCoder Beginner Contest225 B - Star or Not
問題文
N 頂点 N−1 辺の木が与えられます。
頂点には 1,2,…,N の番号がついており、i 本目の辺は頂点 a i と頂点 b i を結んでいます。
この木がスターであるか判定してください。
ただしスターとは、1 つの頂点から、他の全ての頂点に 1 本ずつ辺が出ている木のことです。
制約
・3≤N≤10 ^5
・1≤a i
解答例
n = int(input()) graph = [[] for _ in range(n)] for i in range(n-1): a, b = map(int,input().split()) a -= 1 b -= 1 graph[a].append(b) graph[b].append(a) res = 0 for i in range(n): res = max(res,len(graph[i])) if res == n-1: print("Yes") else: print("No")
解説
N頂点N-1辺の木が与えられ、その木がスターか判別する問題です。
スターとは問題文にあるように、１つの頂点からほかのすべての頂点に1本ずつ辺がでている木のことです。
配列graphを用意して、各頂点から出ている辺を格納していきます。
graph[i]には頂点iから辺でつながっているほかの頂点が保存されています。
したがって、変数resを用意し、ひとつの頂点から出ている辺の最大値を求めました。
このresがn-1ならばその木はスターで、そうでなければスターでないと判別できました。
AtCoder-ABC224 C - Triangle?【Python解答例】
AtCoder Beginner Contest224のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 224 - AtCoder
AtCoder Beginner Contest224 C - Triangle?
問題文
xy 平面上に 1 から N までの番号が付いた N 個の点があります。
点 i は座標 (X i ,Y i ) にあり、相異なる 2 点は異なる位置に存在します。
この N 点から 3 点を選ぶとき、選ばれた 3 点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めてください。
制約
・入力は全て整数である
・3≤N≤300
・−10 9 ≤X i ,Y i ≤10 ^9
・i≠j ならば (X i ,Y i )≠(X j ,Y j )
解答例
n = int(input()) X = [] Y = [] for i in range(n): x, y = map(int,input().split()) X.append(x) Y.append(y) ans = 0 for i in range(n-2): for j in range(i,n-1): for k in range(j,n): tmp = (X[i]-X[k])*(Y[j]-Y[k]) - (X[j]-X[k])*(Y[i]-Y[k]) if tmp != 0: ans += 1 print(ans)
解説
N点から3点を選んで三角形をつくるとき、正の面積を持つ三角形が何個あるか答える問題です。
3点の選び方は全探索して、正の面積（＝面積が0でない）の三角形の数を数えました。
こちらの記事から、座標平面上の三角形の面積は1/2|(x1-x3)(y2-y3)-(x2-x3)(y1-y3)|で求まります。
つまり、|(x1-x3)(y2-y3)-(x2-x3)(y1-y3)|が0でない組み合わせの数をansで数えて、ループを抜けたあとにansを出力すればOKでした。
ABC224の関連記事はこちら
ebisuke33.hatenablog.com
AtCoder-ABC224 A - Tires / B - Mongeness【Python解答例】
AtCoder Beginner Contest224のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 224 - AtCoder
AtCoder Beginner Contest224 A - Tires
問題文
末尾が er または ist であるような文字列 S が与えられます。
S の末尾が er である場合は er を、 ist である場合は ist を出力してください。
制約
・2≤∣S∣≤20
・S は英小文字のみからなる。
・S の末尾は er または ist である。
解答例
s = input() if s[-1] == "r": print("er") else: print("ist")
解説
与えられた文字列の末尾にあわせて、er か ist を出力する問題です。
文字列の末尾はer か istしかないので、文字列の最後の文字がrならerを、そうでなければistを出力すればOKでした。
AtCoder Beginner Contest224 B - Mongeness
問題文
縦 H 行、横 W 列のマス目があり、各マスには 1 つの整数が書かれています。 上から i 行目、左から j 列目のマスに書かれている整数は A i,j です。
マス目が下記の条件を満たすかどうかを判定してください。
1≤i 1
制約
・2≤H,W≤50
・1≤A i,j ≤10 ^9
・入力はすべて整数
解答例
h, w = map(int,input().split()) A = [] for i in range(h): array = list(map(int, input().split())) A.append(array) flag = True for i in range(h-1): for ii in range(i,h): for j in range(w-1): for jj in range(j,w): tmp1 = A[i][j] + A[ii][jj] tmp2 = A[ii][j] + A[i][jj] if tmp1 > tmp2: flag = False if flag: print("Yes") else: print("No")
解説
与えられたマス目で問題文の条件を満たすか答える問題です。
4重ループで全探索して条件を満たすか確認します。
問題文のi1はi、i2をii、 j1をj、j2をjjとしてループを回しました。
左辺をtmp1、右辺をtmp2として、tmp1>tmp2があればflagをFalseとして管理します。
ループを抜けたあとにflagにあわえて答えを出力すればOKでした。
ABC224の関連記事はこちら
ebisuke33.hatenablog.com
AtCoder-ABC223 C - Doukasen【Python解答例】
AtCoder Beginner Contest223のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 223 - AtCoder
AtCoder Beginner Contest223 C - Doukasen
問題文
N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが A i cm で、 1 秒あたり B i cm の一定の速さで燃えます。
この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。
制約
・1≤N≤10 ^5
・1≤A i ,B i ≤1000
・入力は全て整数
解答例
n = int(input()) A = [] B = [] for i in range(n): a, b = map(int,input().split()) A.append(a) B.append(b) time = 0 for i in range(n): tmp = A[i] / B[i] time += tmp time /= 2 ans = 0 for i in range(n): if A[i] / B[i] <= time: ans += A[i] time -= A[i] / B[i] else: ans += B[i] * time break print(ans)
解説
左端と右端から着火したとき、導火線のどの位置で2つの火がぶつかるか答える問題です。
ふたつの火がぶつかる時間は、片側から火をつけて燃え尽きるまでの時間の半分になりますのでこれをtimeとしました。
あとは左端からの距離をansとして、左からtimeになるまでの距離を足していき、timeとなったときのansを出力すればＯＫでした。
ABC223の関連記事はこちら
ebisuke33.hatenablog.com
AtCoder-ABC223 A - Exact Price / B - String Shifting【Python解答例】
AtCoder Beginner Contest223のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 223 - AtCoder
AtCoder Beginner Contest223 A - Exact Price
問題文
高橋君の財布の中には 100 円硬貨が 1 枚以上入っており、それ以外には何も入っていません。
高橋君の財布の中の合計金額が X 円である可能性はありますか？
制約
・0≤X≤1000
・入力は全て整数
解答例
x = int(input()) if x > 0 and x % 100 == 0: print("Yes") else: print("No")
解説
X円が100の倍数か判定する問題です。
Xが100の倍数かどうかは、Xを100で割った余りが0かどうかでわかります。
ただし、Xは0である可能性があり、そのときの余りも0になることに注意します。
Xが0より大きく、100で割った余りが0のときはYesを、そうでなければNoを出力すればOKでした。
AtCoder Beginner Contest223 B - String Shifting
問題文
空でない文字列に対し、先頭の文字を末尾に移動する操作を左シフト、末尾の文字を先頭に移動する操作を右シフトと呼びます。
例えば、abcde に対して左シフトを 1 回行うと bcdea となり、右シフトを 2 回行うと deabc となります。
英小文字からなる空でない文字列 S が与えられます。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものを求めてください。
制約
・S は英小文字からなる。
・S の長さは 1 以上 1000 以下である。
解答例
s = input() List = [] for i in range(len(s)): tmp = s[i:] + s[:i] List.append(tmp) List.sort() print(List[0]) print(List[-1])
解説
与えられた文字列を右シフト、あるいは左シフトすることでできる文字列の辞書順最小と最大のものを答える問題です。
シフトしてできる文字列をすべて作成し、Listに格納していきます。
スライスを使ってシフトした文字列を作成しました。
すべての文字列を作成したあとにListをソートします。
ソート後の最初の文字列が辞書順最小に、最後の文字列が最大になりますので、それぞれ出力すればACでした！
AtCoder-ABC222 D - Between Two Arrays【Python解答例】
AtCoder Beginner Contest222のC問題についてPythonの解答例を記事にしていきます。
Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） - AtCoder
AtCoder Beginner Contest222 D - Between Two Arrays
問題文
長さ n の数列 S=(s 1 ,s 2 ,…,s n ) がすべての i (1≤i≤n−1) に対して s i ≤s i+1 を満たすとき、かつそのときに限り「数列 S は広義単調増加である」と呼びます。
広義単調増加な長さ N の整数列 A=(a 1 ,a 2 ,…,a N ),B=(b 1 ,b 2 ,…,b N ) が与えられます。
このとき、次の条件を満たす広義単調増加な長さ N の整数列 C=(c 1 ,c 2 ,…,c N ) を考えます。
・すべての i (1≤i≤N) に対して a i ≤c i ≤b i が成り立つ。
整数列 C としてあり得る数列の個数を 998244353 で割ったあまりを求めてください。
制約
・1 ≤ N ≤ 3000
・0 ≤ a i ≤ b i ≤ 3000 (1 ≤ i ≤ N)
・整数列 A,B は広義単調増加である。
・入力はすべて整数である。
解答例
mod = 998244353 n = int(input()) m = 3005 A = list(map(int, input().split())) B = list(map(int, input().split())) dp = [[0]*m for _ in range(n)] for j in range(A[0], B[0]+1): dp[0][j] += 1 for i in range(n): for j in range(A[i],B[i]+1): if i > 0: dp[i][j] = dp[i-1][j] for j in range(m-1): dp[i][j+1] += dp[i][j] dp[i][j+1] %= mod print(dp[n-1][B[n-1]])
解説
公式解説をみてACできました。
動的計画法で数列Cの組み合わせの数を求めていきます。
dp[i][j]：i番目の要素でci = j のときの組み合わせの数 として更新していきました。
dp[i][j]はdp[i-1][j]とdp[i][j-1]の和で更新していけばOKで、最後にdp[n-1][B[n-1]]が求めたい数列の個数になるので出力すればACです。
ABC222の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
