WARush

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

SRM690 Div1 Easy "WolfCardGame"

問題

リンク無し!

狼のSotheと猫のSnukeがカードゲームで遊んでいる。このゲームはちょうど100枚のカードを使う。カードには1から100の数字が書かれている。ゲームの遊び方については以下の通り。

1. 初めに、猫のSnukeが1から100の中から数字のNを選び、これをゴールとする。
2. それから、狼のSotheが100枚のカードからちょうどK枚選び、Snukeに渡す。
3. 次に、猫のSnukeが渡されたK枚のカードから何枚かカードを捨てる。
   彼は渡されたカードの任意のサブセットを捨てるカードとして選ぶことができ、
   それはカードをまったく捨てなくてもよいし、全てのカードを捨ててもよい。
4. 最後に、猫のSnukeは、彼がまだ持っているカードのうち、
   任意のサブセットのカードを選び、そこにマイナスの記号を書く。
   例えば彼が{1, 3, 4, 7}のカードを持っていたとしたら、
   {-1, 3, 4, -7}などとなる。

このゲームの終わりでは、Snukeが持っているカードに書かれている数字の合計を計算する(この時、追加されたマイナスの記号を考慮する)。それがゴールであるNと等しいならば、Snukeの勝ちである。そうでなければSotheの勝ちである。

あなたには狼のSotheがゲームに勝つための手助けをしてもらいたい。今、ゲームはStep2の局面である。あなたには、Snukeが決めたint Nと、Snukeに渡すカードの枚数であるint Kが与えられる。Snukeがゲームに勝つ事ができないように、K枚のカードを選んでほしい。もし複数の答えがあるのであれば、どれを返してもよい。答えがないのであれば、空のリストを返すこと。

解法

dの倍数の数字同士で、それらを足し引きすると必ずdの倍数となる。
この性質を踏まえると、Nがdの倍数でないときは、{d * 1, d * 2, ... , d * K}のカードを選べばよいことになる。
ただし、N = 60の時だけは2, 3, 4, 5, 6の何れも倍数となり、7がdとなる。
7 * 15 = 105であり、N = 60, K = 15のときにまずいので、リストには105の代わりに1などを追加してあげる必要がある。

ソースコード

bool P[101];

class WolfCardGame {
    public:
    vector<int> createAnswer(int N, int K) {

        if (N == 60 && K == 15) {
            int data[] = {7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 1};
            vector<int> ans(data, data + K);
            return ans;
        }

        int d = 0;
        for (int i = 2; i <= 7; i++) {
            if (N % i != 0) {
                d = i;
                break;
            }
        }

        vector<int> ans;
        for (int i = 1; i <= K; i++) {
            ans.push_back(d * i);
        }
        return ans;
    }
};