AtCoder Beginner Contest (ABC) 185　PythonでC問題解いてみた

前回の解いたやつ

f:id:mery_poke:20211101223644p:plain

こんにちは。メリーです。

この度！！無事に！！！！Google Adsense通りました！！！！
いえい！！！！

前回申請したとき(9月初め)は、サイトが見つかりませんって連絡が来たので、記事をそれなりに書いてから改めて申請しよう、としたら成功しました！！
やっぱり、はてなブログの無料版でも通るんですね・・・。

というわけで今日も元気にAtCoder Beginner Contest (abc) 185 Ｃ問題解いていきます。

言語はPython、提出はPyPyです。

Problem C Act1. Challenge

問題文

ちょっとオシャンティーな感じのタイトルにしてみました。
タイトルの付け方がネタ切れ気味だったのでいい感じ。

閑話休題（それはさておき）

長さがLの直線状の物体を11か所で切断します。切断の仕方は何通りですか。
という問題。

なかなかに難しい問題ですね。

各切断の箇所をそれぞれ点P₁、P₂、・・・、P₁₁とします。
各点Pの取り得る範囲は、

0 < P₁ ≦ L-11
P₁ < P₂ ≦ L-10
:
:
:
P₁₀ < P₁₁ ≦ L-1

となるので、その範囲で全探索しようとなると、だいぶめんどくさい。
11重ループをぶん回していけば解けるけど、余裕のTLE。
計算量えぐいって・・・。

というわけで何かしらの方針の転換が必要。

うーん、どうしたもんかなーーと、手元のノートに問題文を図示していく。
やっぱりこういうのはノートに書きながらだよねーって感じで。

入力例3のL=17だとこんな感じだよね。

ん？？
これ、見覚えあるぞ？？？？
高校数学の順列と組み合わせの問題ってこんな感じだった気が・・・？？

というわけで、Googleで「順列　計算」、「組み合わせ　計算」で検索すると、_nP_rや、_nC_rを計算してくれる最高のサイトが存在したので、それで計算してみました。
~~べ、別に順列組み合わせの定義うろ覚えとかそんなんじゃ、ないんだからねッ！！！~~

というわけで、順列で計算した結果、174,356,582,400、組み合わせで計算した結果、4,368でした。
組み合わせで計算した結果と出力例3が一致したので、組み合わせっぽいですね。

順列で各点Pのパターンを調べようとすると、点P₁やP₂の位置がバラバラになるっぽいですね。

この2つが区別されると困る。というか、定義的に認めてない。(P₁は範囲的に、P₂よりも左に存在する。)

というわけで計算するときは順列ではなく組合わせで計算しましょうということでした。

というわけでコーディングです。

方針は、
1. Lをインプット
2. _L-1C₁₁を計算
3. 2の結果を出力

実際のコードがこちら。

import math

l = int(input())

ans = math.factorial(l-1) // (math.factorial(l-1 - 11) * math.factorial(11))

print(ans)

はい。これだけです。4行です。問題文はあんなに難しそうだったのに。拍子抜けです。

というわけで解説を。
~~解説することあるのか・・・？？~~

mathというライブラリはAtCoderで使えるので使って大丈夫です。

ans = math.factorial(l-1) // (math.factorial(l-1 - 11) * math.factorial(11))

でやってることは、 (L-1)! ÷ ((L-1-11)!×11!)の計算です。
math.factorial(n)でn!を計算できます。あとはそれを使って組み合わせの公式、

に突っ込むだけです。

最後に出力して終了です。

今回は組み合わせに気付くかどうかという問題でしたね。

やっぱり、問題を図で考えるのは大事なんだな～～と改めて実感しました。

それでは。