roiti46's blog

主に競プロ問題の解説を載せてます

yukicoder No.169, 170, 171

ボーナスステージだった

問題はこちら

No.169 何分かかるの!?

あるデータのコピーがK%まで進んでいて残り時間がS分である。全体のコピーにかかる時間を小数切り捨てで答えよ。

解法

小数が出てくると誤差の問題が出てくるので整数の範囲で計算を終わらせる。分母分子を100倍して計算を行っていけばいい。

K = int(raw_input())
S = int(raw_input())
print 100*S/(100-K)

No.170, 171 スワップ文字列(Easy), (Med)

英大文字からなる文字列Sが与えられる。となりあう文字通しをスワップしていったとき、S以外の文字列を何種類作ることができるか答えよ。(Easy N ≦ 8, Med N ≦ 1000)。

解法

となりあう文字をスワップできるなら任意の文字列を作ることができる。

長さLの文字列があり、各アルファベットがそれぞれN1,N2,N3,...個あった時、作ることのできる文字列の種類はL!/(N1! N2! N3! ... )である。 多倍長に対応してるならそのまま計算してしまえばいい(No.170なら最後の%573を取り除く)。

C++での解説はkmjpさんの解説記事を参照してください。

def fact(n):
    res = 1
    while n > 0:
        res *= n
        n -= 1
    return res
    
S = raw_input()
hist = [0]*26
pfor s in S:
    hist[ord(s)-ord("A")] += 1
ans = fact(len(S))
for i in hist:
    ans /= fact(i)
print (ans-1)%573
広告を非表示にする