この記事で扱う3問では、方法を選ぶ条件がそれぞれ異なります。ABC225 Aは文字列の長さが3なので、位置の並べ方を最大6通り全て作れます。ABC150 CはN ≤ 8なので公式の全順列法も成立しますが、異なる順列の順位だけなら位置ごとにまとめて数える別解も使えます。ABC185 Cは、正整数の長さを持つ12本への分割を、11個の内部切断位置の選択へ一対一に対応させます。
ABC225 A、ABC150 C、ABC185 Cの順に、小さい入力を追ってから完全なPython参考コードへ進みます。各問題で、全列挙や数え上げが成り立つ定義と制約を分けて確認します。
ABC225 A：3文字なら全列挙して重複を消せる
ABC225 A – Distinct Stringsの問題文では、長さ3の英小文字列を並べ替えてできる異なる文字列の数を求めます。位置の並べ方は最大でも3! = 6通りなので、全て生成しても候補は6個です。ABC225 Aの公式解説にも場合分けと全列挙の方針が示されています。
abaを位置で区別して並べると、生成順の一例はaba, aab, baa, baa, aab, abaです。位置の選び方は6通りありますが、同じ文字列が重複しています。集合setへ入れるとaab, aba, baaだけが残るため、答えは3です。ここでは「位置の順列は全て作る」「同じ完成文字列は集合で一つにする」という二段階を分けて考えます。
以下は問題の入力仕様に合わせて組み立てた完全なPython参考コードです。公式コードの転載ではなく、提出結果・AC記録・実測性能を示すものでもありません。
import sys
from itertools import permutations
def main():
s = sys.stdin.readline().strip()
distinct = {''.join(order) for order in permutations(s)}
print(len(distinct))
if __name__ == '__main__':
main()公式サンプルは次の3組です。入力と期待出力は公式問題ページのものをそのまま記載しています。
| 入力 | 期待出力 |
|---|---|
aba | 3 |
ccc | 1 |
xyz | 6 |
正しさは、permutations(s)が3つの位置の全順列を生成することから分かります。得られる全ての並べ替えは一度以上生成され、集合は同じ完成文字列だけを一つにまとめます。したがって、集合の要素数が異なる並べ替え文字列の数と一致します。
境界と計算量も制約と一緒に見ます。公式制約では長さが常に3なので、生成数は最大6、集合の要素数も最大6です。長さを一般にnとみなすと、文字列の生成まで含む時間計算量はO(n! × n)です。異なる長さnの文字列を集合が最悪n!個保持するため、追加メモリも最悪O(n! × n)相当になります。nが大きい問題へ、この全列挙をそのまま持ち込むことはできません。
ABC150 C：全順列法と位置別順位を区別する
ABC150 C – Count Orderの問題文では、1からNまでを一度ずつ使う二つの順列PとQについて、辞書順の順位の差を求めます。制約は2 ≤ N ≤ 8です。最大でも8! = 40320通りなので、ABC150 Cの公式解説PDFは全順列を生成し、PとQより小さい順列を数える方法を示しています。この制約なら、全列挙は公式の解法として十分に成立します。
ただし、辞書順順位だけが必要なら、全順列を保存せずに数えることもできます。先頭から順に見て、現在の値より小さい未使用の値を置いた場合を考えます。その候補を一つ置くごとに、残りの要素は自由に並べられるため、残りがk個ならk!通りをまとめて飛ばせます。この位置別順位は、要素が全て異なるというABC150 Cの条件で使う方法です。
例としてP = (2, 3, 1)の0始まり順位を追います。最初の未使用要素は[1, 2, 3]です。2より小さい候補は1の一つで、その後の2要素には2! = 2通りあるため、ここで2通りを飛ばします。次の未使用要素は[1, 3]で、3より小さい候補は1の一つ、残りは1! = 1通りなので1を加えます。最後の1では小さい未使用要素がなく、合計は2 + 1 + 0 = 3です。
| 現在の値 | 未使用要素 | 小さい候補数 | 残りの並べ方 | 加える数 |
|---|---|---|---|---|
2 | [1, 2, 3] | 1 | 2! | 2 |
3 | [1, 3] | 1 | 1! | 1 |
1 | [1] | 0 | 0! | 0 |
全順列を辞書順に並べると(1,2,3), (1,3,2), (2,1,3), (2,3,1), ...なので、(2,3,1)は0始まりで3、公式の1始まりでは4番目です。二つの順位へ同じ1を足しても差は変わりません。つまりabs((rankP + 1) - (rankQ + 1)) = abs(rankP - rankQ)です。
以下は、この0始まりの位置別順位を使う完全なPython参考コードです。公式解説の全順列コードではなく、問題の定義から組み立てた別解です。公式コード・提出結果・AC記録・実測性能を示すものではありません。
import math
import sys
def rank_zero_based(perm, factorial):
unused = list(range(1, len(perm) + 1))
rank = 0
for i, value in enumerate(perm):
smaller = sum(candidate < value for candidate in unused)
rank += smaller * factorial[len(perm) - 1 - i]
unused.remove(value)
return rank
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
p = data[1:1 + n]
q = data[1 + n:1 + 2 * n]
factorial = [1] * (n + 1)
for i in range(1, n + 1):
factorial[i] = factorial[i - 1] * i
print(abs(rank_zero_based(p, factorial) - rank_zero_based(q, factorial)))
if __name__ == '__main__':
main()公式サンプルは次の3組です。
| 入力 | 期待出力 |
|---|---|
3 | 3 |
8 | 17517 |
3 | 0 |
正しさを位置ごとに確認します。ある位置で現在の値より小さい未使用要素を置いた順列は、その位置が最初の相違点になるため、元の順列より必ず辞書順で小さくなります。小さい候補一つにつき、残りの異なる要素の並べ方は残り要素数の階乗だけあります。各位置で先頭が一致する範囲へ進みながらこの個数を足すと、元の順列より小さい順列を重複なく全て数えられます。したがって、合計は0始まりの辞書順順位です。
境界と計算量は、この別解の適用条件を決めます。未使用リストから小さい要素を数え、使った値を削除するため、時間計算量はO(N^2)、追加メモリはO(N)です。この順位計算はPとQが異なる要素だけからなる順列だから成り立ちます。重複要素を含む並びの順位へは、そのまま一般化できません。
ABC185 C：12本への分割を11個の切断位置選びに変える
ABC185 C – Duodecim Ferraの問題文では、長さLの鉄棒を11箇所で切り、正整数の長さを持つ12本へ分ける方法を数えます。公式制約は12 ≤ L ≤ 200です。長さを12個並べて試す代わりに、鉄棒の内部にある整数位置から切断位置を選びます。
端からの距離が1, 2, ..., L - 1となる内部位置はL - 1個です。ここから異なる11箇所を選べば、隣り合う切断位置の間隔は必ず正整数になり、12本の長さが一つに決まります。反対に、正整数の長さを持つ12本への分割からは、左から長さを累積することで11箇所の内部位置が一意に決まります。したがって答えはC(L - 1, 11)です。ABC185 Cの公式解説も、この切断位置の選択と、各段階で割りながら組合せを計算する方法を示しています。
L = 13なら内部位置は1から12までの12個で、そのうち11個を選びます。選ばない位置を一つ決めることと同じなのでC(12, 11) = 12です。境界のL = 12では内部位置が11個しかなく、全て選ぶ一通りだけなのでC(11, 11) = 1になります。
以下は、組合せを各段階で割りながら求める完全なPython参考コードです。公式コードの転載ではなく、提出結果・AC記録・実測性能を示すものでもありません。
import sys
def combination(n, r):
if r < 0 or r > n:
return 0
r = min(r, n - r)
value = 1
for i in range(1, r + 1):
value = value * (n - r + i) // i
return value
def main():
l = int(sys.stdin.buffer.readline())
print(combination(l - 1, 11))
if __name__ == '__main__':
main()公式サンプルは次の3組です。
| 入力 | 期待出力 |
|---|---|
12 | 1 |
13 | 12 |
17 | 4368 |
正しさは、切断位置と分割の一対一対応に加え、combinationの更新で確認できます。対称性C(n, r) = C(n, n - r)を使って小さい方のrを選び、ループのi回目には直前の組合せ数から次の組合せ数へ進みます。value * (n - r + i) // iは各段階で割り切れ、ループ終了時にC(n, r)となります。
境界と計算量では、まず問題文にmodがないことを確認します。答えは2^63未満と保証されているため、法を取ったり逆元を使ったりせず、正確な整数をそのまま出力します。ループ回数は高々11回なので時間計算量はO(11)、追加メモリはO(1)です。Pythonの整数は任意精度ですが、このコードも分子を全て掛けてから割るのではなく、各段階で割りながら進めます。
次の問題で方法を選ぶための判断
ABC225 Aでは、候補数が固定の6通りなので、全列挙して重複を集合で消せました。ABC150 Cでは公式のN ≤ 8なら全順列法が使えますが、異なる順列の順位だけなら、各位置で残りの階乗分をまとめて数えられます。ABC185 Cでは完成した12本を列挙せず、分割と一対一に対応する11個の内部位置を選びました。
別の問題で方法を選ぶときは、候補数だけで全列挙の可否を決めず、数える対象と候補1件あたりの処理を確認し、制約から総時間とメモリを見積もります。そのうえで、重複する要素を区別するか、順位が0始まりか1始まりか、分割で長さ0を許すか、modを取る指定があるかを問題ごとに確かめます。3問の方法は、それぞれの定義と制約が一致する場合に使えます。
