Topcoder SRM 721 Div1 Medium - GraphAndPairs

問題概要

整数d, kが与えられる。最短距離がdであるような頂点のペアがちょうどk個あるような無向グラフを構成せよ。ただしすべての辺の距離は1とし、辺・頂点とも最大で1000個までとする。

2 <= d <= 50

1 <= k <= 50000

解法

(D-1)個の頂点を一直線につないだグラフを考える。このグラフの両端にn個ずつ頂点をくっつけると両側の距離がちょうどdになるので、条件を満たすペアはn2個になる。このようなグラフを独立に何個も作っていくことにすれば、結局kを平方数の和で表す問題に帰着する。貪欲でやっても最大ケースで800個程度しか頂点を使わないので十分収まる。ただしd=2がコーナーケースで、ひとつの頂点を中心に他の点をくっつけていく形になるので、その場合の処理は分けて書く必要がある。

感想

なんか全然思いつかなかったです

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

class GraphAndPairs  {
public:
    vector<int> construct(int D, int K) {
        vector<int> ans;
        
        if (D == 2) {
            for (int n = 0; n < 1000 && K > 0; ++n) {
                int m = n;
                int s = 0;
                for (n = n + 1; n < 1000 && s <= K; ++n) {
                    ans.push_back(m);
                    ans.push_back(n);
                    K -= s;
                    s += 1;
                }
            }
        } else {
            for (int n = 0; n < 1000 && K > 0; ) {
                int m1 = n;
                int m2 = n + D - 2;
                for (n = n + 1; n <= m2; ++n) {
                    ans.push_back(n - 1);
                    ans.push_back(n);
                }
                int cnt;
                for (cnt = 1; n < 1000 && K - cnt * cnt >= 0; cnt += 1, n += 2) {
                    ans.push_back(n);
                    ans.push_back(m1);
                    ans.push_back(n + 1);
                    ans.push_back(m2);
                }
                cnt -= 1;
                K -= cnt * cnt;
            }
        }

        int mx = 0; for (auto a: ans) mx = max(mx, a);
        ans.push_back(mx + 1);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};