Hatena::Grouptopcoder

yambe2002の日記

2016-05-04

SRM690 Div1 Easy: WolfCardGame

22:51

本番では解けなかった。

https://community.topcoder.com/stat?c=problem_statement&pm=14248&rd=16729

解法はこちらを参考にさせていただいた。

http://mayokoex.hatenablog.com/entry/2016/05/04/120006

1~100までの数字が書いてあるカードが100枚ある。ここからK枚を選んだとき、そのサブセットの合計がどうやってもNにならないようにしたい。その組み合わせを答えよ。不可能なときは空配列を返せ。ただし、数字は、合計する際にネゲートする(負にする)こともできる。

例:選ばれたカード{1,3,4,7}は、{-1,3,4,-7}で計算することも可能

N:1~100

K:1~15

方針

Nで場合分けすることで解ける。

1、Nが偶数のとき

 →3の倍数のカードだけ返す。そうすれば合計が3nにしかならない。なお、Nが6の倍数のときは別に場合分けする

2、Nが6の倍数のとき

 →5の倍数のカードだけ返す。そうすれば合計が5nにしかならない。なお、Nが30の倍数のときは別に場合分けする

3、Nが30か60のとき

 →1と、7の倍数のカードだけ返す。そうすれば、合計が7n+1または7n-1にしかならない。

4、Nが90のとき

 →2と、7の倍数のカードだけ返す。そうすれば、合計が7n+2または7n-2にしかならない。

5、Nが奇数のとき

 →偶数カードだけ返せば、合計が必ず偶数になる

不可能な場合は存在しない。


public class WolfCardGame {
    int[] GetRet(int additional, int seed, int K)
    {
        var ret = new List<int>();
        if (additional > 0) ret.Add(additional);

        var val = seed;
        while (ret.Count() < K)
        {
            ret.Add(val);
            val += seed;
        }

        return ret.ToArray();
    }

    public int[] createAnswer(int N, int K) {
        if (N % 90 == 0)
            return GetRet(2, 7, K);
        if (N % 30 == 0)
            return GetRet(1, 7, K);
        if (N % 6 == 0)
            return GetRet(-1, 5, K);
        if (N % 2 == 0)
            return GetRet(-1, 3, K);
        return GetRet(-1, 2, K);
    }
}

本番は解けなかったにも関わらずレートが増えた。Div1は不思議な場所だ・・・。