TopCoder SRM 675 Div1 Easy: TreeAndPathLength3

,

$2\cdot{}_aC_2$であるところを${}_aC_2$にしてWA。 紙の上で考えてたときは分かっていたのに、何時の間にか頭から消えてしまっていた。 0完で青に落ちた。

Easy: TreeAndPathLength3

解法

0 -- 1 -- 2 -- 3の部分を中心に、i -- i+1 -- 0を$a$本、3 -- jを$b$本生やすと、頂点数$2a+4+b$、長さ3の道数$a(a+1) + (b+1)$のグラフになる。 これで、制約を満たすものは全て作れる。

実装

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

class TreeAndPathLength3 {
public:
    vector<int> construct(int s) {
        repeat (a,500) {
            int b = s - (a*(a+1) + 1);
            if (0 <= b and 2*a + 4 + b <= 500) {
                return construct(a,b);
            }
        }
        assert (false);
    }
    vector<int> construct(int a, int b) {
        vector<int> g;
        std::function<void (int,int)> e = [&](int v, int w) {
            g.push_back(v);
            g.push_back(w);
        };
        e(0,1);
        e(1,2);
        e(2,3);
        repeat (i,a) {
            int j = 4+2*i;
            e(j,0);
            e(j,j+1);
        }
        repeat (i,b) {
            int j = 4+2*a+i;
            e(j,3);
        }
        return g;
    }
};