おにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎり日記

 | 

2013-02-19

yet again SRM571

04:07

Medium 分かった。




Coding Phase に考えたこと。

clique 増やせるなら増やしたほうがいいから、max clique を求める。

一般に max clique なんて、NP-hard なのにいいのか、これ。

なんかの指数だなこれは。

stable set で考えよう。

3*m>=2*n が怪しすぎる。

50の時、34だから16ぐらい消える。

16だし適当に書いても通ったりするんかなぁ。

とりあえず、書いてみよう。

最初30個ぐらいが complete graph になってて、

あとの20個をまばらにした graph を適当につなぎ合わせると、

死ぬなこれ。

まぁいいや提出しちゃえ。


復習

16が怪しい過ぎる。

これは指数的な something。

stable set に変換して、0 から作っていくことばっか考えてたけど、

clique のままで50から減らしていくこと考えた方が分かりやすい。

全体から始める。

もし、complete でないなら、adjacent でないどちらかの点を省く必要がある。

両方試す。

return

これを繰り返す。

再帰は高々16ぐらいの深さ。

それぞれで、状態は2つに分かれる。

状態数は、1<<16 しかない。

解けた。


なんかの指数になることと、16は小さいは見えてたのに、

1<<16 になるんじゃないかとは思わなかった。

思ったところで何かがあったのかは知らない。




Medium

    int[] magicPower;
    string[] graph;
    int len;
    public int maxMagicPower(int[] magicPower, string[] magicBond)
    {
        len = magicPower.Length;
        this.graph = magicBond;
        this.magicPower = magicPower;
        bool[] unused = new bool[len];
        return DFS(len, unused);
    }

    private int DFS(int remainder, bool[] unused)
    {
        if (3 * remainder < 2 * len)
            return -1;
        int res = -1;
        for (int i = 0; i < len; i++)
        {
            for (int j = i + 1; j < len; j++)
            {
                if (!unused[i] && !unused[j] && graph[i][j] == 'N')
                {
                    unused[i] = true;
                    res = Math.Max(res, DFS(remainder - 1, unused));
                    unused[i] = false;
                    unused[j] = true;
                    res = Math.Max(res, DFS(remainder - 1, unused));
                    unused[j] = false;
                    return res;
                }//if
            }//for j
        }//for i
        res = 0;
        for (int i = 0; i < len; i++)
            if (!unused[i])
                res += magicPower[i];
        return res;
    }

ついでに、書き直した easy


    const int max = 50;
    const int digit = 10;
    int cnt;
    int len;
    string[] res;
    public string[] playList(int n)
    {
        len = Math.Min(n, max);
        cnt = 0;
        res = new string[len];
        DFS(0, n);
        return res;
    }

    private void DFS(long current, int n)
    {
        if (current > n || cnt >= len)
            return;
        if (current > 0)
            res[cnt++] = current.ToString() + ".mp3";
        for (int i = 0; i < digit; i++)
            if (current != 0 || i != 0)
                DFS(digit * current + i, n);
    }

DFS のエントリで for(int i=1;i<10;i++) 回すのと、

DFS のなかで current == 0 を省くの、どっちの方がいいんやろ。

practice room まだか。

SRM571

03:15

Medium 全く分からん。




Easy


1000以下全て作って、さらに、100**t (0<=t<=50) のやつ全部作った。

最初(1<=t<=50)にしててバグ取るの時間掛かった。

string 50 個出てくると、出力見るの大変。

DFS(n)

for(int i=0;i<10;i++)

DFS(10*n + i)

みたいに書いてもできる。

こっちの方が綺麗。

で。

DFS(10*n + i)の再帰で書いてる人がいて、

n が int のままの人がいたので challenge しました。

しかし、攻撃は外れた。

1e9 に 10 を掛けても int の世界ではわりと大きい数のままやた。

数え上げとかなら、オーバーフローしてたらまず変なこと起きるけど、

こういうオーバーフローしても大丈夫なパターンもあるらしい。

challenge でレートが減っていく。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/utmath/20130219
リンク元
 |