WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM675 Div1 Easy "TreeAndPathLength3"

考えた解法

0と1をとりあえず繋げる。
他の頂点は0または1にだけ繋げることを考えると、長さ3のシンプルパスの数は0に繋げた頂点の数 * 1に繋げた頂点の数になる。
9991とかの大きめの素数はこれだけだと丁度にならないので、0に繋げた頂点のどれかに直列に繋げて補完する。

例えばs = 19のとき、0に3つ、1に5つ繋げて3 * 5 = 15 残り4。あとは0に繋がっている頂点に直列に2つ繋げて3 + 1 = 4追加する。
イメージは以下のような感じ
f:id:Ekaing:20161010212244p:plain

事後

ソースコード

class TreeAndPathLength3 {
    public:
    vector<int> construct(int s) {
        // とりあえず0と1を繋げる
        vector<int> ans;
        ans.push_back(0);
        ans.push_back(1);

        for (int on0 = 1; on0 <= 200; on0++) {
            for (int on1 = 1; on1 <= 200; on1++) {
                int rem = s - on0 * on1;
                if (rem == 0 || (on0 <= rem && rem - on0 + 1 <= 500 - (on0 + on1 + 2))) {
                    int cur = 2;
                    // 1に繋げまくる
                    for (int i = 0; i < on1; i++) {
                        ans.push_back(1);
                        ans.push_back(cur++);
                    }
                    // 0に繋げまくる
                    for (int i = 0; i < on0; i++) {
                        ans.push_back(0);
                        ans.push_back(cur++);
                    }
                    // 残りを直列に繋げまくる
                    rem = rem - on0 + 1;
                    cur--;
                    for (int i = 0; i < rem; i++) {
                        ans.push_back(cur);
                        ans.push_back(++cur);
                    }
                    return ans;
                }
            }
        }
        return ans;
    }
};