AtCoder ABC #140 : F - Many Slimes

ここ2回、ABCの最終問題の難易度が落ちたような。
https://atcoder.jp/contests/abc140/tasks/abc140_f

問題

初期状態で、任意の体力のスライムを1体準備できるとする。
1秒毎に、各スライムは自身の体力より小さな体力のスライムを生成できるとする。

2^N体のスライムの体力が与えられる。
初期のスライムの体力を適切に選んだ時、N秒後に指定した2^N体の体力のスライムを構成できるか。

解法

1秒ごとにスライムを倍にしなければならないので、各スライムは必ず1体スライムを生成しなければならない。
また、あとのことを考えると早めに生成するのはできるだけ体力が多いものが望ましい。

一旦生成したスライムの体力はいじれないので、最初の1体の体力は最大値の物一択である。
あとは貪欲で行ける。毎秒、スライムの体力に大きい順に次に生成するスライムを決めていく。
その際、未生成のうち生成可能な最大値の体力の物を生成しよう。
生成対象がいなければ、構築不可。

以下のコードは毎回ソートしているので計算量がO(N*2^N)だが、O(2^N)にも抑えられる様子。

int N;
ll S[1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,1<<N) cin>>S[i];
	sort(S,S+(1<<N));
	multiset<int> T;
	FOR(i,(1<<N)-1) T.insert(S[i]);
	
	vector<int> V;
	V.push_back(S[(1<<N)-1]);
	FOR(i,N) {
		vector<int> W=V;
		
		FORR(v,V) {
			auto it=T.lower_bound(v);
			if(it==T.begin()) return _P("No\n");
			it--;
			W.push_back(*it);
			T.erase(it);
		}
		
		sort(ALL(W));
		reverse(ALL(W));
		swap(V,W);
	}
	_P("Yes\n");
	
}

まとめ

スライム分裂・合体系の問題、大抵重さとか体積が対象となるので、体力値を題材にするのは珍しいね。
まぁ分裂だと、分裂元の大きさが減っちゃうってのもあるんだろうけども。

あと今回動画も撮ってみました。
www.youtube.com