質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.49%

AtCoderでの問題解決の糸口

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 393

score 3260

[コードレビュー]

/*
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 になる

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • BeatStar

    2020/09/15 21:56

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

    キャンセル

  • mjk

    2020/09/15 23:02 編集

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

    キャンセル

  • BeatStar

    2020/09/19 20:01

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

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

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

    キャンセル

回答 1

checkベストアンサー

0

INFが小さすぎます

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/15 21:57

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る