kmjp's blog

競技プログラミング参加記です

yukicoder : No.625 ソンタクロース

yukicoder

シンプルな問題設定で良い。
https://yukicoder.me/problems/no/625

問題

N人のサンタクロースでM個のプレゼントを分け合う。
サンタクロースは1番から順に並んでいる。

サンタクロースは以下の手順で配り方を決める。

  • 残っているサンタクロースのうち最も若い番号のサンタクロースが配り方を提案する。
  • 配り方を提案後、本人を含め全員が賛否を投じる。
    • 過半数が賛成すればその配り方で決まる。
    • そうでない場合、そのサンタクロースは退場し、改めて次のサンタクロースが提案を行う。

各自、以下を達成するように配り方提案や賛否投票を行う。

  • 自身の配布数を最大化する。
  • 退場は最悪ケースである。
  • 自身の配布数が等しいなら、残ったサンタクロースを最小化したい。
  • 自身の配布数が等しく、残ったサンタクロースが最小化される案が複数あるなら、後ろのサンタクロースに多く配られることを望む。

全員が最適化を目指し行動する場合、配り方はどうなるか。

解法

  • 1人なら自分に配って終わり。
  • 2人なら、2番の人が必ず反対するので、1番は退場確定で2番が総取りする。
  • 3人なら、2番の人が退場を避けるため必ず賛成するので、1番の人が総取りする。

4人以上のケースを考えよう。
1番の人は、退場を避けるためには自身の配布数を削ってでも過半数の賛成を得なければならない。
そのために、仮に自分が退場した場合の(N-1)人の場合の配り方がわかっているとする。

N人について改めて考えると、(N-1)人のケースに対し、半数にそれ以上の配布数を達成できる場合、自分に賛成してもらえる。
よって(N-1)人のケースにおける配布数が少ない半数に先に1余分に配布しよう。
それが可能ならそれがベストで、残りは0個配布でよい。
半数に1余分に配布できないなら、どうやっても過半数得られないので自身は退場するしかない。

そんな感じで少ない人数から順に求めていけばよい。

int N,M;
int P[1010][1010];

int R[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	MINUS(P);
	if(N==1) return _P("%d\n",M);
	if(N==2) return _P("-1 %d\n",M);
	if(N==3) return _P("%d 0 0\n",M);
	P[3][0]=P[3][1]=0;
	P[3][2]=M;
	for(i=4;i<=N;i++) {
		vector<pair<int,int>> cand;
		FOR(j,i-1) cand.push_back({P[i-1][j],j});
		sort(ALL(cand));
		FOR(j,i-1) P[i][j]=0;
		int left=M;
		FOR(j,i/2) {
			x=cand[j].second;
			P[i][x]=P[i-1][x]+1;
			left-=P[i][x];
		}
		P[i][i-1]=left;
		if(P[i][i-1]<0) break;
	}
	
	x=N;
	while(P[x][x-1]<0) x--;
	
	FOR(i,N) _P("%d%c",P[x][N-1-i],(i==N-1)?'\n':' ');
}

まとめ

シンプルな設定ながら面白い問題でした。