読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC046を解いてみた

競技プログラミング ABC

abc046.contest.atcoder.jp

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)