2017-2018 ICPC Central Quarter Final of Northeastern European F-Spying Game

問題のリンク

問題概要

次の条件を満たす有向グラフを一つ出力せよ。ただし解の存在は保証される。

• $N$ 頂点のDAGである
• 多重辺や自己ループは含まれない
• 頂点 $ M $ から頂点 $i$ への経路の総数は $D _ {i}$ に等しい

制約

• $1 \leq N \leq 60$
• $1 \leq M \leq N$
• $0 \leq D _ {i} \leq 2^{62}$

解法

まず $D _ {i}$ の値でソートしておく。

入力では $D _ {M - 1}=0$ となっているが、以下これを1として扱う。

大まかな方針としては、$D _ {0}$ から $D _ {i-1}$ の部分和で $D _ {i}$ に等しくなるような集合を1つ求めて、それらの集合から辺を張っていけば良い。

この時、$D _ {i} $ の大きい方から見て貪欲に採用するという解法が正当となる。

以下その証明

始めに各 $i$ に対して $\sum_{j=0}^i D _ {j}$ 以下の任意の自然数は、$i$ 番目までの部分和として表せることを示す。

$D _ {0} =1$ より、$i=0$ の時成立。

問題の条件(解の存在の保証)より、$D _ {i+1} \leq \sum_{j=0}^i D _ {j}$ が成り立つ。$i$ において命題の成立を仮定すると、

$$\sum _ {j=0}^i D _ {j}+1 \leq x \leq \sum _ {j=0}^{i+1} D _ {j}$$

を満たす自然数 $x$ が部分和として表せることを示せれば良い。

$$\sum _ {j=0}^i D _ {j}+1 - D _ {i+1} \leq y \leq \sum _ {j=0}^{i+1} D _ {j} - D _ {i+1}$$

を満たす自然数 $y$ と $D _ {i+1}$ を組み合わせることで $x$ を得ることが出来るが、上で述べた条件より $y$ は非負整数であり、$y$ は $i$ までの部分和として表せることが仮定より言えるので、$i+1$ においても命題が成立する。

この結果を用いることで、貪欲な操作によって構築が不可能にならないこと(=貪欲解の正当性)が導かれる。

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    m--;
    vector<pair<ll,int>> v(n);
    for(int i=0;i<n;i++){
        ll x; cin >> x;
        v[i]=make_pair(x,i+1);
    }
    sort(v.begin(), v.end());
    vector<pair<int,int>> res;
    v[0].first=1;
    for(int i=1;i<n;i++){
        ll rem=v[i].first;
        int j=i-1;
        while(j>=0 and rem>0){
            if(rem-v[j].first>=0){
                rem-=v[j].first;
                res.push_back({v[j].second,v[i].second});
            }
            j--;
        }
    }
    printf("%d\n",res.size());
    for(auto p:res){
        printf("%d %d\n",p.first,p.second);
    }
}