WARush

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

SRM617 Div1 Medium "PieOrDolphin"

問題

まだ
(なぜ追加されない・・)

はるか遠い国、そこには50人のプログラマーが一緒のオフィスで働いていた。プログラマー達には0~49の番号が振られている。イワンは町の有名人である。プログラマーはイワンの事を尊敬していたため、彼を自分達のオフィスに招待した。そのことを嬉しく思ったイワンは、これからN日間、毎日訪れることに決めた。(順番に0~N-1日目と呼ぶことにする)

毎日イワンは1つはイルカの形でもう1つはパイの形をした2つのおもちゃを持っていくことにした。それぞれの日で、プログラマー達は最も生産的な話し合いができるような、2人のプログラマーを選出し、イワンと合うようにした。1人はイワンからイルカのおもちゃをもらい、もう1人はパイのおもちゃをもらっていた。(イワンがどちらのおもちゃをどちらのプログラマーに渡すかを決めていた)

イワンがオフィスを訪れる最後の日。最後のイルカとパイのおもちゃを彼が渡した後、プログラマーは彼をお別れ会のディナーに招待した。そのディナーの中で、それぞれのプログラマーが、受け取ったイルカのおもちゃの数と、パイのおもちゃの数の差の絶対値を計算した。それから、彼らはその合計値を計算した。驚いたことに、その値は最小値となっている事が判明した。プログラマー達はイワンのスキルに非常に驚き、どのようにやったかを尋ねたが、彼は幸運だったと控えめに答えただけだった。

あなたは2つのN個の要素を持つint[] choice1, choice2が与えられる。choice1[i], choice2はそれぞれi日目に何番目のプログラマーがイワンと会い、おもちゃを受け取っていたかを表す。上記の最小値を満たすためには、どのようにおもちゃを渡せばよいかを示して欲しい。N個の要素を持つvectorを返せ。それぞれの値には1か2とすること。choice1[i]のプログラマーがイルカを受け取り、choice2[i]のプログラマーがパイを受け取るのならば1とし、その反対であれば2とすること。

制約

1 <= choice1.size() <= 1000
choice1.size() == choice2.size()
0 <= choice1[i], choice2[i] <= 49
choice1[i] != choice2[i]


考えたこと

プログラマーを頂点としたグラフに置き換えて考えてみる。
それぞれの日に2人のプログラマーがイワンと会っているが、こいつらを辺で結ぶ。その時、イルカをもらったほうをfrom、パイをもらったほうをtoとして、有向な辺にしておく。

そう考えると、各頂点の入次数と出次数の差をなるべく少なくしたい。閉路にできる辺はコスト0となるので、どう閉路を作っていけばよいかが問題になりそう。

・・・だがしかし・・・

なんかどう閉路を作っても、問題なく最小値を作れるみたいだ・・。
なので、適当に閉路を作って、後は次数が1になってる辺を見つけて適当にパスを辿るのみ。

もっといい考え方

どこぞの赤コーダーさんのブログに書いてあったんですが、次数が奇数の頂点がコスト1(入次数・出次数の差が1)、次数が偶数の頂点がコスト0(入次数・出次数が同じ)となるのが最善で、こうなるように辺の向きを決めていけばよい。という考え方があるようで、断然こっちの方がいいな~と思いました。

なんかあと、オイラー路なるものと関連があるらしい・・

ソースコード

int n;
vector <int> c1, c2;
bool used[1050];
bool vis[55];
int cnt[55];
vector <int> ans;
bool isEnd;

class PieOrDolphin {
public:

    vector <int> Distribute(vector <int> choice1, vector <int> choice2) {
        n = choice1.size();
        c1 = choice1;
        c2 = choice2;
        ans.resize(n);
        memset(used, false, sizeof(used));
        memset(vis, false, sizeof(vis));

        // 閉路を見つけて使った辺を記録する
        for (int i = 0; i < 50; ) {
            isEnd = false;
            memset(vis, false, sizeof(vis));
            int r = dfs1(i);
            if (r == -1) i++;
        }

        // 各頂点の次数を数える
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            cnt[c1[i]]++;
            cnt[c2[i]]++;
        }

        // 次数が1となってる頂点を見つけ、パスを辿り、
        // 使った辺を記録する
        while (true) {
            bool end = true;
            for (int i = 0; i < 50; i++) {
                if (cnt[i] == 1) {
                    dfs2(i);
                    end = false;
                }
            }
            if (end) break;
        }

        return ans;
    }

    // 頂点sからdfsして閉路を見つける
    int dfs1(int s) {
        vis[s] = true;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (c1[i] != s && c2[i] != s) continue;
            int t;
            if (c1[i] == s) {
                t = c2[i]; ans[i] = 1;
            }
            else{
                t = c1[i]; ans[i] = 2;
            }
            used[i] = true;
            if (vis[t]) return t;
            int r = dfs1(t);
            if (r == -1) {
                used[i] = false;
            } else {
                if (isEnd) used[i] = false;
                if (s == r) isEnd = true;
                return r;
            }        
        }
        vis[s] = false;
        return -1;
    }

    // 頂点sからdfsしてパスを辿る
    void dfs2(int s) {
        int t = -1;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (c1[i] != s && c2[i] != s) continue;
            if (c1[i] == s) {
                ans[i] = 1;
                t = c2[i];
            }
            else{
                ans[i] = 2;
                t = c1[i];
            }
            used[i] = true;
            cnt[c1[i]]--;
            cnt[c2[i]]--;
            break;
        }
        if (t != -1) dfs2(t);
    }
};