読者です 読者をやめる 読者になる 読者になる

SRM 690(Div.1 Easyのみ)

ケアレスミスでEasyを落としました.(何やってんだか.)

解いた問題

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

問題概要

整数  NKが与えられる.( 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_iNにならないようにする.

解法

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

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

よって,adを変化させて適当な数列を作る.

念のため,NKを変化させて全通り試すと,N=60K=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については気が付いて,修正もすんでいたが,前のままでも問題ないと思って提出していなかった. 出力判定関数も書いていたのに,そもそもその判定関数が間違っているという...

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