AtCoder ARC #203 : A - All Winners

まぁ悪くはない結果。
https://atcoder.jp/contests/arc203/tasks/arc203_a

問題

正整数N,Mが与えられる。
Nチームが総当たり戦を行う。その際、各チームにはM人がいる。
チーム同士の試合では、両チームのM人同士が1:1で戦い、いずれもどちらかが勝ちどちらかが負ける。
全勝する最大人数は何名か。

解法

ある2チームで見ると、全勝する人は最大M人である。
仮に全勝者が最大のチームにおいて、全勝者がm人の場合、他チームはmin(M-m,M/2)人しか全勝にならない。
この場合に全勝する人を最大にする場合、

• 1チームはceil(M/2)人全勝
• 残りはfloor(M/2)人全勝

が最大となる。

int T;
ll N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		ll ret=(M+1)/2+(N-1)*(M/2);
		cout<<ret<<endl;
	}
}

まとめ

最初どこから手を付けようか迷ったが、まぁそこそこの時間で解けて良かった。