「今週のお題:一発で決まる多数決」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。 …なお、その前の船の問題は見事に不正解でした…。ちょっと余り吟味する余裕が無かったので、記事は断念です。

codeiq.jp

問題

問題については、次の記事をご覧ください。簡単に言うと、GCPを皆で出して多数決単独トップが生まれる場合の数 ( 「誰が出したか」は区別せず ) を求める問題です。

codeiq.jp

解答

提出解は、以下の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で書くのが面倒になるので数式の表現はちょっと手抜きです。悪しからず。