SRM 690(Div.1 Easyのみ) - blue

ケアレスミスでEasyを落としました．（何やってんだか．）

解いた問題

Easyのみ.120点ぐらいでの提出だった．

問題概要

整数 $N$ と $K$ が与えられる．（ $1\le N\le 100, 1\le K\le 15$ ）

1 ~ 100 までの整数のうち， $K$ 個の数 $u_1, u_2, ..., u_K$ を選び，どのように $v\in \{-1,0,1\}^K$ を選んでも， $\sum_i u_i v_i$ が $N$ にならないようにする．

解法

等差数列 $a + d(i-1)$ でよさそう．

このように数列をとると，どう選んでも， $b a + c d$ （ $b,c\in \mathbb{Z}$ ）にしかならない．この形では， $\operatorname{gcd}(a,d)$ の倍数しか作れないということは一般常識．

よって， $a$ と $d$ を変化させて適当な数列を作る．

念のため， $N$ と $K$ を変化させて全通り試すと， $N=60$ ， $K=15$ でこの方法ではうまくいかない．最も長く作れて，14個（ $a=7,d=7$ とする)．よって，この時だけ1を追加すればよい．．．はずだった．

ミスしたところ

初項 $a$ ，公差 $d$ の等差数列の $a$ 以上 $e$ 以下の項の個数は， $\lfloor (e-a)/c\rfloor+1$ でえられる．

int k = (100 - a) / d ;

はい．見事に+1を忘れました．

解法では， $N=60,K=15$ がコーナーケースと言いましたが，これだと $K=14$ の場合もできないと判定してしまいます．

それだけだったらよかったのだが， $N=60,K\ge 14$ のときに，1と""2""を加えるようにしてしまった．この2つを足すと3になって， $-3 \equiv 60 \pmod{7}$ となってしまう．加えるのであれば，8（7を法として1と合同）とかにすべきだった．．．

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(c) (c).begin(),(c).end()

ll gcd(ll x, ll y){
    return y == 0 ? x:gcd(y, x % y);
}

struct WolfCardGame {
  int N;
  int K;
  vector<int> createAnswer(int _N, int _K) {
    N = _N, K = _K;
    for(int a = 1; a <= 100; ++a){
        for(int d = 1; d <= 100; ++d){
            if(N % gcd(a,d)){
                int k = (100 - a) / d; //ミス その1
                if(k >= K){
                    vector<int> ret(K);
                    for(int i = 0; i < K; ++i){
                        ret[i] = a + d * i;
                        if(ret[i] >= 100) cout << "oops" << endl;
                    }
                    return ret;
                }
            }
        }
    }
// ミス その2
    vector<int> ret(K);
    for(int i = 0; i < 13; ++i) ret[i] = 7 + 7 * i;
    ret[13] = 1;
    if(K == 15){
        ret[14] = 2;
    }
    return ret;
  }
};

// Powered by Greed 2.0-RC

実は，ミスその1については気が付いて，修正もすんでいたが，前のままでも問題ないと思って提出していなかった．出力判定関数も書いていたのに，そもそもその判定関数が間違っているという．．．

もっと落ち着いて問題を解こうな．