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

 | 

2012-02-10

SRM532

| 10:57

0点。



Easy

右端に来る3つ組み、左端に来る三つ組み(相異なる)を決めて、

その2つの間には、残ってる奴の中で、

3つとも数字のやつを全てつっこめばいい。

O(n^3)になる。

ここで問題になるのが、

右端、左端が相異なるようにできないとき、

つまり、1つの3つ組みから選ぶとき。

本番ではこのコーナーケースの処理が適当で死んだ。

目先の早い提出に目がくらんだ。

    public int maxBeauty(string[] chains)
    {
        int len = chains.Length;
        int res = 0;

    //corner case
        for (int i = 0; i < len; i++) for (int j = 0; j < 3; j++) if (chains[i][j] != '.')
                {
                    int cnt = 0;
                    for (int k = j; k < 3 && chains[i][k] != '.'; k++) cnt += chains[i][k] - '0';
                    res = Math.Max(res, cnt);
                }

        //I'm greedy.
        for (int i = 0; i < len; i++) for (int j = 0; j < len; j++) if (i != j)
                {
                    int cnt = 0;
                    for (int k = 0; k < len; k++) if (k != i && k != j && !chains[k].Contains(".")) for (int p = 0; p < 3; p++) cnt += chains[k][p] - '0';
                    for (int pos = 2; pos >= 0 && chains[i][pos] != '.'; pos--) cnt += chains[i][pos] - '0';
                    for (int pos = 0; pos < 3 && chains[j][pos] != '.'; pos++) cnt += chains[j][pos] - '0';
                    res = Math.Max(res, cnt);
                }
        return res;
    }//maxBeauty

Medium

DP.

解法はすぐに浮かぶが実装ができない。

配列の再利用をして計算時間を減らせば間に合うようになる。

ただ、DAG?とかいうのか、順序がよく分からんくなってかけなかった。

こういうときはメモ化再帰すればいいけど、

なぜかDPで解こうとばっかりして、はまってった。

ここまで求めればこれを求めれる、というのをしっかり意識しないと。

今回は、i番目、それのペア、j個まで使った、maskの順。

更新は、f(j+1)<-f(j) の形になって、j以降のループは干渉しない。

ということを考えればまだましだったか。


    public int numWays(int N, int M, int K)
    {
        int max = 1 << K + 1;
        int[, ,] dp = new int[N + 1, M + 1, max];
        dp[0, 0, 0] = 1;
        for (int i = 0; i < N; i++)
        {
      //組み合わせを数えるDP
            for (int p = 1; p <= K && i + p < N; p++) for (int j = 0; j < M; j++) for (int mask = 0; mask < max; mask++) dp[i, j + 1, mask ^ 1 ^ 1 << p] = (dp[i, j + 1, mask ^ 1 ^ 1 << p] + dp[i, j, mask]) % mod;
          
            //maskをずらす処理
            for (int j = 0; j <= M; j++) for (int mask = 0; mask < max; mask++) if ((mask & 1) == 0) dp[i + 1, j, mask >> 1] = dp[i, j, mask];
        }//for i
        return dp[N, M, 0];
    }//numWays




久々に横に長いコード書いた。

 |