2020年 10月 2日
まえがき
いろいろあった。
今日解いた問題
ABC178 D- Redistribution
- [数列の和,数え上げ,(動的計画),(DP)]
解説ではDPを使っていたけど、よく分からん。ってなって、ネットサーフィンを30秒しても良う分からん。だったので書く。
なんとなく、数列の長さを i と決めたとき、長さiの数列の全ての数の和がSとなるとき、条件を満たす長さiの数列は何通りあるかっていうのが楽に求められたらいいな。
って考えた。
長さiの数列は何通りあるかっていうのが分かれば、i(すなわち、数列の長さ)を1からnまで全部回してやればいいな。
で、とりあえず数式を書いてみる。
a[0] + a[1] + ... + a[i] = S
(条件) a[0], a[1], ... , a[i] >= 3
式変形をする（これは、マスターオブ場合の数とかやってたら割と出てくる)
(a[0] -2) + (a[1] - 2) + ... + (a[i] - 2) = S - 2n
a[k] - 2 = A[k] と置き換える。(0 <= k <= i)
すると...
A[0] + A[1] + ... + A[i] = S - 2n
(条件) A[0], A[1], ... , A[i] >= 1
まあなんかこれは、S-2n個のボールを i 人でわけたいです。一人1個は持ってたいね。
みたいになる。
これはあれだね、ボールをS-2n個並べて、そこに生まれるS-2n-1個の隙間のうち、i-1箇所に仕切りを入れよう！ってやつ。
(S-2n choose i-1)
俺は怠惰なので図解も何もしない。
ということで、数列の長さがiのときは、
S-2n-1個の隙間からi-1箇所を選ぶ組み合わせの数が、数列の和がSとなる組み合わせの数ってワケ（笑)
これをfor文で回してやれば終わりってワケ(笑)
あとがき
頭ピーナッツ
おまけ
9月18日にブログを出そうとして、途中で辞めていたので載せときます。
ここから下は、9月18日に書いた内容らしいです。
まえがき
久しぶりに競技プログラミングをしたので日記するよ
健康管理
無粋なことをお聞きにならないでください。
舌の裏に口内炎があります。
何した
確かずっと前に、この問題が出来ないって言ったと思うんですけど、それの解き方を頭に浮かべながら実装方法分からん。って言って写経してました。
その後、うん。平面操作をしよう、って言って蟻本をひらいているところでございます。
具体的に
蟻本P231,Coneologyをnow playingでございます。
これ、本に書いてある1つの円に対して、別の円の内部に含まれているかどうかをO(N)で判定する方法っていうのは、
円の中心が別の円の内側にあって、さらに（内包されているか知りたい）円の半径が、別の円の半径より小さい場合に内包されている。ってことでいいのかな？
とりあえずそれでコードを書いたら入力例に対しては正しい答えをだしていた。
