AtCoderでの問題解決の糸口

Question

[コードレビュー]

/*
CAUTION:
再度AtCoderで試してみて、それでもだめなら"todo:" の部分を修正してみて、
それでもだめなら質問する
*/

私は趣味でC++やっています。

AtCoderに挑戦中なのですが、わからないところがあります。

Searching:bit全探索 → C - Skill Up
をやってみました。

「bit全探索」を使うそうなのでbit全探索の基本的な部分を学んで試してみました。
ですが、なぜか常にエラーです。

自分のPC上で MinGW を使ってコンパイルし、試してみると問題文にある出力例と一致します。
ですが提出するとなぜか最初のテストが失敗します。

自分なりのコード:

#include<iostream>
#include<vector>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<iomanip>

using std::cout;
using std::endl;
using std::flush;
using std::cin;

namespace Util{
    using StringVector = std::vector<std::string>;
    
    /*
       @ 目的: 文字列分割
    */
    StringVector split( const std::string &s, const std::string &delim = std::string(" ") ){
       const int len = s.size();
       char tmp[len+1];
       strcpy( tmp, s.c_str() );
       
       std::vector<std::string> res;
       
       char *tmpStr = std::strtok( tmp, delim.c_str() );
       if( tmpStr == NULL ) return res;
       
       while( tmpStr != NULL ){
           //cout << tmpStr << endl;
           res.push_back( tmpStr );
           tmpStr = NULL;
           tmpStr = std::strtok( NULL, " " );
       }
    return res;
    }
    
    /*
       @ 目的: 数字等を文字列に固める
    */
    template<typename T>
    std::string toString( T data, int width = 0 ){
       std::stringstream ss;
       ss << std::setw(width) << data;
    return ss.str();
    }
    template<> std::string toString( bool flg, int width ){
       if( width == 1 && flg ) return std::string("T");
       if( width == 1 && !flg ) return std::string("F");
       if( flg ) return std::string("true");
    return std::string("false");
    }
}


namespace Original{
    using Data  = std::vector<int>;
    using Table = std::vector< Data >;
}

int main( void ){
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    
    // めちゃくちゃな値をセットしておく
    const int INF = 100001;
    
    // n, m, x をそれぞれ取得
    std::string tmpNum;
    std::getline( cin, tmpNum );
    Util::StringVector t = Util::split( tmpNum );
    int n = std::atoi( t[0].c_str() );
    int m = std::atoi( t[1].c_str() );
    int x = std::atoi( t[2].c_str() );
    
    // テーブルとして取得( 二次元配列風 )
    Original::Table table;
    for( int i = 0; i < n; i++ ){
         std::string s;
         getline( cin, s );
         Util::StringVector sv = Util::split( s );
         Original::Data d;
         for( int j = 0; j < m+1; j++ ){
              d.push_back( std::atoi( sv[j].c_str() ) );
         }
         table.push_back( d );
    }
    
    // 初期値は INFとする
    int ans = INF;
    
    // bit全探索
    for( int bit = 0; bit < (1 << n); bit++ ){
         std::vector<int> vec(m+1,0);
         for( int i = 0; i < n; i++ ){
              if( (bit >> i) & 1 ){
                  vec[0] += table[i][0];
                  for( int j = 1; j <= m; j++ ) vec[j] += table[i][j];
              }
         }
         
         bool isAllowed = true;
         for( int i = 1; i <= m; i++ ){
              // todo: もしエラーなら "<=" とかにしてみる
              if( vec[i] < x ){ isAllowed = false; break; }
         }
         
         if( isAllowed ) ans = std::min( ans, vec[0] );
    }
    
    if( ans == INF ) cout << -1 << endl;
    else             cout << ans << endl;
return 0;
}

MinGW上でも失敗するのならわかりますが、MinGWでは成功するがAtCoderでは失敗するのが…不明…
(どこか間違っている気がするが…自分の凝り固まった頭では見つけられない…)

もちろんデバッガ(GDB)を使ってデバッグもしてみました。
ですがそれでも原因が見つからず…

AtCoder内にある、実装例のコードを参照してみましたが、発想自体は大体同じで、単に

{ コスト, Alg1, Alg2, Alg3 ... } という風にレコード(?)を抽出するのか、

cost と { Alg1, Alg2, Alg3 ... } という風に 分離するのかの違いしかないようです。

なぜこんなにも差が出るのでしょうか…

コードレビュー、お願いします…

[情報]
言語: C++
(PC上の)コンパイラ: MinGW
AtCoder上で試したコンパイラ: // todo: ここに記述

値: { border1,2 とhand3, large4-8 } が WA になる

Comments

[mjk]

問題だけ見て解説は見ずにbit全探索で検索してどういうものか調べて実装したら初見の私でもあっさり解けました。
とても分かりやすいbit全探索のやり方なのでご参考までに。
https://drken1215.hatenablog.com/entry/2019/12/14/171657

[mjk]

解法的なことは理解しているということなら・・・
テストケースの存在はご存知ですか？
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
こちらでWAになった時のデバッグしてみたらどうでしょう結果一覧だとWAたくさん出てるようなので。

[BeatStar]

mjkさん、ありがとうございます。
他の方が仰っているように、『INFの値が小さすぎる』のが原因のようでした…

[mjk]

原因が分かってしまえばそんなとこだったかというのは自分でもよくあります。
WAの時はテストケースが公開されていればダウンロードしてデバッグすると速いですよ。
大きいサイズだとコピペ出来ないのでファイルからの入力でテスト出来る環境や関数作っておくと便利らしいです。
コンテスト本番中はWAでも当然見えないのでそこを想定して探るのが難しいです。
本番のテストケースを想定する練習としてもWAの時に確認で覗いておくと経験になると思います。

[BeatStar]

mjkさん、ありがとうございます。
後から問題文での定義(条件)を確認したら、確かにINFが小さかったようです。(10^5とか言われても…)

また、競技プログラミングのアドバイス、ほんとにありがとうございます。
そういう情報ってあまり目にしないので参考になりますっ!

あと、上記でのDropBoxは公式のでしょうか。
もしそうじゃないのなら、どうやってそういうデータを引っ張り出してきたのでしょうか。
後学のためにお願います。

Answer 1

INFが小さすぎます

Comments

[BeatStar]

ご回答ありがとうございます。
その可能性もありそうなので試してみると、ちゃんとACになりました!
(AtCoderのテストケースってサンプルのやつ違うのか…)