「今週のお題:一発で決まる多数決」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。 …なお、その前の船の問題は見事に不正解でした…。ちょっと余り吟味する余裕が無かったので、記事は断念です。
問題
問題については、次の記事をご覧ください。簡単に言うと、GCPを皆で出して多数決単独トップが生まれる場合の数 ( 「誰が出したか」は区別せず ) を求める問題です。
解答
提出解は、以下のRuby(30)でした。
n=eval *$< p ~n**2/2+n%2-n%3/2
解説については、提出時のコメントの流用で。
方針
全ケースから、多数決が決まらない ( トップで引き分けが発生する ) ケースを差し引くことで答えを求めます。
各ケース
全部で n人参加の場合のケースを挙げ、それぞれ何通りかを計算します。
全ケース
GCPに各人数を割り振るため ( 「誰が」は区別しないため )、重複組み合わせ 3Hn=(n+1)(n+2)/2 通りです。2種以上がトップ
残り1種に着目します。- まず、トップ2種で引き分けなので残り1種の人数の偶奇は nの偶奇と一致。
- 人数の上限は、引き分け以下になるために [n/3]人。
- 最小の人数は、nが偶数なら0人、nが奇数なら1人。つまり mod(n,2)人。
かつ残りがGCPのどれになるか3通りなので、( [([n/3]-mod(n,2))/2] + 1 )*3 通りです。
- 全種トップ これは1通りしかありませんが、nが3の倍数の時に限り、他では0通りです。敢えて書けば 1-|sgn(mod(n,3))| 通りです。
2番目のケースは3番目のケースを包含しているため、結局、解を f(n) としたとき、
f(n) = (n+1)(n+2)/2 - ( [([n/3]-mod(n,2))/2] + 1 )*3 + ( 1-|sgn(mod(n,3))| )*2
という計算になります。
実装
ただ、上の計算では や mod等が出てきてすっきりしません。ただ、mod 6 での周期的な性質が期待できること、 定数項を除けば [(n+1)2/2] で近似できることを元に、f(n)-[(n+1)2/2] を計算すると、 mod(n,6)の値、0~5 に応じて、0,1,-1,1,0,0 であり、これはさらに、周期2の 0,1 と、周期3の 0,0,-1 の 合計です。 そのため、f(n)=[(n+1)2/2] + mod(n,2) - [mod(n,3)/2] として計算できます。
終わりに
書いててよかった提出時コメント!! なお、 や || が入るとtexで書くのが面倒になるので数式の表現はちょっと手抜きです。悪しからず。