naoya_t@topcoder

SRM361 Div1 Easy: WhiteHats

過去問, 練習 | 02:10 |

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

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

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

{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;
  }
};