ABC175 C問題

Question

前提・実現したいこと

ABC175 C問題をbit全探索で回答を作ってみました。

発生している問題・エラーメッセージ

制約上TLEになるのは分かるが、WAも複数回出る理由がわからない
コードのどの点にその原因があるのか知りたい

該当のソースコード

include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
  int64_t x, k, d, ans = 10000000000000000; cin >> x >> k >> d;
  int64_t y = x;
  rep(i, 1 << k){
    rep(j, k){
      if((i >> j) & 1) y += d;
      else y -= d;
      //cout << y << endl;
    }
    //cout << y << endl;
    if(y < 0) y = -y;
    if(ans > y) ans = y;
    y = x; 
  }
  cout << ans << endl;
  return 0;
}

試したこと

サンプルコードを入力してテスト

補足情報（FW/ツールのバージョンなど）

入力される値は最大値10の15乗

Answer 1

入力される値は最大値10の15乗

でしたら、1 << kという値はkビット必要ですので、64ビットしかないint64_tでは全く足りません。

Comments

[lygumi]

理解できました！
ありがとうございます！

Answer 2

kが64を超えるとき、1 << kが0になり、10000000000000000が出力されて終了する為です。
なので、WAになります。

大抵このような実験をする時は、assertを使って考慮していないケースを排除します。

cin >> x >> k >> d;
assert(k < 20);  // 20未満でない場合はREにしてもらう

Comments

[lygumi]

理解できました！ありがとうございます！
知識不足で申し訳ないのですが、
REにしてもらうというのはどういうことなのかご教授願います。

[maai]

想定していない入力→RE
想定した入力かつ正答→AC
想定した入力かつ誤答→WA

想定した入力かつ誤答が無い、つまり書いたコードが想定通りなら、ACとREだけになります

[lygumi]

ありがとうございます！