yukicoder : No.1803 Remainder of Sum

なるほど。
https://yukicoder.me/problems/no/1803

問題

整数N,Mが与えられる。
1～Nを1つずつ含む整数集合Sを考える。
Sから異なる2値x,yを選び、コスト(x+y)%Mを掛けてyをSから取り除くことを繰り返し、最終的にSの要素を1つにしたい。
総コストの最小値を求めよ。

解法

問題を言い換えると、1～Nのラベルを張った頂点に対し、xとyのラベルの頂点の間にコスト(x+y)%Mで辺を張れる場合、最小全域木のコストを求める問題となる。

N≧Mの場合を考える。
まず(aM+x)と(bM-x)の形の頂点はコスト0で連結できる。
この時点で連結成分数はfloor(M/2)+1
次に、(aM+x+1)と(bM-x)の頂点をコスト1でつなげられることを考えると、総コストfloor(M/2)で最小全域木を作れる。

N＜Mの場合、M/2未満の小さいxに対してはx+1とM-xをコスト1で連結したくても、後者がが存在しないかもしれない。
その場合は1とxをコスト(x+1)で連結しよう。
その総コストは(M-N)*(M-N+1)/2-2+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;
		
		if(N>=M) {
			cout<<M/2<<endl;
		}
		else {
			ll D=M-N;
			ll ret=D*(D+1)/2-2+M/2;
			cout<<ret<<endl;
		}
		
	}
}

まとめ

参加が遅かったこともあり、Nが微妙に小さい場合を時間内に詰め切れなかった。