Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-01-20

SRM361 Div1 Easy: WhiteHats

| 02:10 | SRM361 Div1 Easy: WhiteHats - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM361 Div1 Easy: WhiteHats - naoya_t@topcoder SRM361 Div1 Easy: WhiteHats - naoya_t@topcoder のブックマークコメント

ごめんなさい2度再挑戦しました

  • (白帽子数)≦(人数)

さっと書いて投稿したコードは

{7, 8, 7, 8, 8, 7, 8, 7, 8, 7, 8, 7, 7, 8, 7, 8} => 8

でコケた。

  • 白帽子の人自身はその白帽子を勘定に入れられないので、合計で(白帽子数)だけのカウント漏れが発生
  • 従って (投票数の合計) = (白帽子数)×(人数)-(白帽子数) = (白帽子数)×(人数 - 1)
  • ∴(投票数の合計)/(人数 - 1) = (白帽子数)

再投稿したコードは

{1, 1, 1, 1, 1, 1, 1, 1, 8} => -1

でコケた。うん、それ無理

  • 各人のカウントが (白帽子数) または (白帽子数-1) になっていることを確認。そうでなければ -1 を返す。
#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class WhiteHats {
 public:
  int whiteNumber(vector <int> count) {
    int n=sz(count);
    int w=0;
    tr(count,it){
      w+=*it;
    }
    if(w%(n-1)>0) return -1;
    int c=w/(n-1);
    if(c>n) return -1;
    tr(count,it){
      if(*it<c-1 || c<*it) return -1;
    }
    return c;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090120