JOI難易度６ アナグラム

問題原文

https://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day3_23.pdf

問題要旨

文字列 が与えられる。
の全てのアナグラムのうち、 は辞書順で何番目か？
ただし、 も のアナグラムとする。

• 

解法

全通り並べることはできないので、うまく数える必要がある。

sample1 の HEART をもとに考えることにする。
まず、先頭の文字が A または E ならば、必ず HEART より小さいことになる。
そしてそのようなものは、

• 先頭が A → 残ったEHRT の並べ方が 通り
• 先頭が E → 残った AHRT の並べ方が 通り

で、48通りある。
これで、「１文字目までの段階で よりも辞書順で小さくなるものの通り数」が出せた。
これを２文字目。。。３文字目。。。とやっていくと、答えがでる。

CROATIA のようなケースでは、 C より小さい A が２つあるが、それぞれのパターンを別のものとしてカウントしないように注意すること。

実装

煩雑になりそうだが、冷静になると短くかける。
の並べ方の通り数をメソッドとして外だししておくとデバッグが楽。

from collections import Counter
from math import factorial
S = list(input())

def calc(X):
    ret = factorial(len(X))
    for v in Counter(X).values():
        ret //= factorial(v)
    return ret

ans = 0
for i, s in enumerate(S):
    used = set()
    for j, t in enumerate(S[i:], start=i):
        if (t < s) and (t not in used):
            ans += calc(S[i: j] + S[j + 1:])
            used.add(t)

print(ans + 1)

感想

考察というよりは実装よりの問題。 はぁ〜〜〜〜〜〜めんどくせ〜〜〜〜と思って放置してたけどそうでもなかった。
CROATIA にはひっかかった（は？）