「今週のお題:ホワイトデーのお返しの個数」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 標準入力から空白区切りで入力される自然数m,n ( $m \lt n \le 1000000$ ) に対し、次の条件を満たすホワイトデーのお返しの組み合わせ数を出力する
- 貰ったm個のバレンタインチョコに対し、合計n個のお返しをプレゼントする
- バレンタインチョコの種類 ( 義務/義理/本命 ) に対して、お返しの個数をそれぞれ 1,2,3 とする。
求める組み合わせの数は、あくまで1個/2個/3個それぞれ返す人数の組み合わせに対して、ですから、結局バレンタインチョコの種類の内訳としてありうるのは何通りか、を調べることになります。
解説
今回、次のRubyのコードを提出しました。
m,n=gets.split.map &:to_i p [m,(n-m)/2].min-[0,n-m*2].max+1
この問題で求めるのは、結局のところ
$$ a,b,c\ge 0 \\ a+b+c=m \\ a+2b+3c=n \\ $$
という整数方程式の解の個数なので、aを消去して
$$ b,c\ge 0 \\ b+c\le m \\ b+2c=n-m $$
とし、c を元にパラメタ化すると、
$$ c\ge 0 \\ c\ge n-2m \\ c\le m \\ c\le \frac{n-m}{2} \\ $$
なる範囲の c に対し、$b=n-m-2c,\,\,a=2m-n+c$ と a,b が一意に決まります。そのため、上述の範囲の c の個数がそのまま解となります。
終わりに
今回は簡単でしたね。さて、皆さまホワイトデーのお返しはちゃんとしましたでしょうか? まあ「個数で差をつける」ってのはないと思いますが、お返しは大事ですね。