ABC046を解いてみた
A問題
内包表現を使って入力を受けとり、set関数で重複を削除した配列の長さをlen()で数えました。
print(len(list(set([int(i) for i in input().split()]))))
B問題
一番左のボールに塗る色がk種類あり、その右のボールの色はk-1種類、その右のボールの色もk-1種類とボールがn個続いていくので結果はk*(k-1)^(n-1)となります。あとは実装するだけです。
n, k = map(int, input().split()) ans = k for _ in range(n-1): ans *= (k-1) print(ans)
C問題
得票数がそれぞれt, aで次の票数の比がi:jとすると ni >= t and nj >= a となるnを探し、得票数は t=ni, a=njとすれば求めることができます。tとaについて無駄に計算する方法しか思い浮かばず解法を考えつくのに時間がかかってしまいました…
import math n = int(input()) ta = [[int(i) for i in input().split()] for j in range(n)] a = 1 b = 1 for i in range(n): #n = max(math.floor(a/ta[i][0]), math.floor(b/ta[i][1])) n = max(~-a//ta[i][0] + 1, ~-b//ta[i][1] + 1) a = n * ta[i][0] b = n * ta[i][1] print(a+b)
D問題
答えとなる文字列をまず全てgと仮定します。そしてgからpに変えるとき、その箇所の入力がgであっても0→1で+1点、pであっても-1→0で+1点で等しいため、位置にかかわらず可能な限り多くの数のgをpに置き換えれば求めることができます。答えとなる文字列を求め、入力と照らし合わせて点数を確かめていけばO(N)=O(10^5)で時間内に答えを求めることができます。
s = input() t = int(len(s)/2) ans_left = 'g' * (len(s)-t) ans_right = 'p' * t ans = ans_left + ans_right ret = 0 for i in range(len(s)-t): if(s[i:i+1] == 'p'): ret -= 1 for i in range(len(s)-t, len(s)): if(s[i:i+1] == 'g'): ret += 1 print(ret)