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;
}