kmjp's blog

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

yukicoder : No.1571 All Your Cycles Are Same Lengths

この問題名、AYBABTUと関係あるのかな。ちょっと離れてるかな。
https://yukicoder.me/problems/no/1571

問題

正整数N・整数Tが与えられる。
N頂点の完全無向グラフにおいて、各辺に非負整数のコストを割り当てる。
全頂点を1回ずつたどる閉路において、常にコストの総和がTとなるものを構築せよ。

解法

N,Tの値で分類する。

  • Tが偶数の場合
    • 頂点1から延びる辺のコストをT/2にすればよい。
  • Tが奇数の場合
    • Nが3の時、どこか1辺をコストTにすればよい。
    • Nが偶数の時解なし。
    • 以下、Nが5,7の例を考える。
      • T=1の時解なし。
      • Tが3以上の場合、T=3のケースを解いたうえで、頂点1から延びる辺のコストに(T-3)/2を追加すればよい。
      • T=3の場合は総当たりしてよい。
int N,T;
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>N>>T;
		
		if(N==3) {
			cout<<"Yes"<<endl;
			for(x=1;x<=N;x++) {
				for(y=x+1;y<=N;y++) {
					if(x==1&&y==2) cout<<x<<" "<<y<<" "<<T<<endl;
					else cout<<x<<" "<<y<<" "<<0<<endl;
				}
			}
		}
		else if(T%2==0) {
			cout<<"Yes"<<endl;
			for(x=1;x<=N;x++) {
				for(y=x+1;y<=N;y++) {
					if(x==1) cout<<x<<" "<<y<<" "<<T/2<<endl;
					else cout<<x<<" "<<y<<" "<<0<<endl;
				}
			}
		}
		else if(N%2==0 || T==1) {
			cout<<"No"<<endl;
		}
		else if(T>=5) {
			cout<<"Yes"<<endl;
			for(x=1;x<=N;x++) {
				for(y=x+1;y<=N;y++) {
					if(x==1) cout<<x<<" "<<y<<" "<<(T-N+2)/2<<endl;
					else cout<<x<<" "<<y<<" "<<1<<endl;
				}
			}
		}
		else if(N==5) {
			cout<<"Yes"<<endl;
			for(x=1;x<=N;x++) {
				for(y=x+1;y<=N;y++) {
					if(x==1) cout<<x<<" "<<y<<" "<<0<<endl;
					else cout<<x<<" "<<y<<" "<<1<<endl;
				}
			}
			
		}
		else {
			cout<<"No"<<endl;
		}
	}
}

まとめ

短い時間で詰め切るのしんどそう。