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の文字列があり、各アルファベットがそれぞれN₁,N₂,N₃,...個あった時、作ることのできる文字列の種類はL!/(N₁! N₂! N₃! ... )である。 多倍長に対応してるならそのまま計算してしまえばいい（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