8VC Venture Cup 2016 - Elimination Round C. Block Towers
手を抜いた感じのする実装。 もっと速く解法思いつくべきだなあと思った。
C. Block Towers
解法
貪欲。$6$の倍数を使わずに塔を作り、高いものから順に空けておいた$6$の倍数の枠に入れていく。$O(n + m)$あるいは$O((n + m) \log{(n + m)})$。
実装
#include <iostream>
#include <set>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
int n, m; cin >> n >> m;
set<int> s;
{
int j = 2;
repeat (i,n) {
s.insert(j);
j += 2;
if (j % 3 == 0) j += 2;
}
}
{
int j = 3;
repeat (i,m) {
s.insert(j);
j += 6;
}
}
{
int i = 6;
while (true) {
int j = *s.rbegin();
if (j <= i) break;
s.erase(j);
s.insert(i);
i += 6;
}
}
cout << *s.rbegin() << endl;
return 0;
}