kmjp's blog

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

8VC Venture Cup 2016 - Elimination Round: C. Block Towers

ABCDはすんなり解けたけどEF解けず。一応レートは維持。
http://codeforces.com/contest/626/problem/C

問題

2の倍数の正整数をN個、3の倍数の正整数をM個選びたい。
全てが異なるようにするとき、最大値を最小化せよ。

解法

最大値をXとすると、それで条件を満たせるかはO(1)で判定できる。

  • Xのうち2の倍数で6の倍数でないものは、N個取る2の倍数に回す。
  • Xのうち3の倍数で6の倍数でないものは、M個取る3の倍数に回す。
  • 6の倍数を残り取るべき2の倍数・3の倍数に回して、合計をN,M個以上に出来るかチェックする。

あとはXを1ずつ増やして判定しても良いし、二分探索しても良い。

int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	x=1;
	while(1) {
		int n6=x/6;
		int n2=x/2-n6;
		int n3=x/3-n6;
		
		int N2=max(0,N-n2);
		int M2=max(0,M-n3);
		if(N2+M2<=n6) {
			cout<<x<<endl;
			break;
		}
		x++;
	}
	
}

まとめ

他の人の怪しいコードは色々あったけど、うまくHack出来なかった。

広告を非表示にする