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

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

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1324閲覧

AtCoderでの問題解決の糸口

BeatStar

総合スコア4958

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2020/09/15 10:15

[コードレビュー]

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

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

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

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

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

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

自分なりのコード:

C++

1#include<iostream> 2#include<vector> 3#include<cstring> 4#include<sstream> 5#include<algorithm> 6#include<iomanip> 7 8using std::cout; 9using std::endl; 10using std::flush; 11using std::cin; 12 13namespace Util{ 14 using StringVector = std::vector<std::string>; 15 16 /* 17 @ 目的: 文字列分割 18 */ 19 StringVector split( const std::string &s, const std::string &delim = std::string(" ") ){ 20 const int len = s.size(); 21 char tmp[len+1]; 22 strcpy( tmp, s.c_str() ); 23 24 std::vector<std::string> res; 25 26 char *tmpStr = std::strtok( tmp, delim.c_str() ); 27 if( tmpStr == NULL ) return res; 28 29 while( tmpStr != NULL ){ 30 //cout << tmpStr << endl; 31 res.push_back( tmpStr ); 32 tmpStr = NULL; 33 tmpStr = std::strtok( NULL, " " ); 34 } 35 return res; 36 } 37 38 /* 39 @ 目的: 数字等を文字列に固める 40 */ 41 template<typename T> 42 std::string toString( T data, int width = 0 ){ 43 std::stringstream ss; 44 ss << std::setw(width) << data; 45 return ss.str(); 46 } 47 template<> std::string toString( bool flg, int width ){ 48 if( width == 1 && flg ) return std::string("T"); 49 if( width == 1 && !flg ) return std::string("F"); 50 if( flg ) return std::string("true"); 51 return std::string("false"); 52 } 53} 54 55 56namespace Original{ 57 using Data = std::vector<int>; 58 using Table = std::vector< Data >; 59} 60 61int main( void ){ 62 cin.tie(0); 63 std::ios::sync_with_stdio(false); 64 65 // めちゃくちゃな値をセットしておく 66 const int INF = 100001; 67 68 // n, m, x をそれぞれ取得 69 std::string tmpNum; 70 std::getline( cin, tmpNum ); 71 Util::StringVector t = Util::split( tmpNum ); 72 int n = std::atoi( t[0].c_str() ); 73 int m = std::atoi( t[1].c_str() ); 74 int x = std::atoi( t[2].c_str() ); 75 76 // テーブルとして取得( 二次元配列風 ) 77 Original::Table table; 78 for( int i = 0; i < n; i++ ){ 79 std::string s; 80 getline( cin, s ); 81 Util::StringVector sv = Util::split( s ); 82 Original::Data d; 83 for( int j = 0; j < m+1; j++ ){ 84 d.push_back( std::atoi( sv[j].c_str() ) ); 85 } 86 table.push_back( d ); 87 } 88 89 // 初期値は INFとする 90 int ans = INF; 91 92 // bit全探索 93 for( int bit = 0; bit < (1 << n); bit++ ){ 94 std::vector<int> vec(m+1,0); 95 for( int i = 0; i < n; i++ ){ 96 if( (bit >> i) & 1 ){ 97 vec[0] += table[i][0]; 98 for( int j = 1; j <= m; j++ ) vec[j] += table[i][j]; 99 } 100 } 101 102 bool isAllowed = true; 103 for( int i = 1; i <= m; i++ ){ 104 // todo: もしエラーなら "<=" とかにしてみる 105 if( vec[i] < x ){ isAllowed = false; break; } 106 } 107 108 if( isAllowed ) ans = std::min( ans, vec[0] ); 109 } 110 111 if( ans == INF ) cout << -1 << endl; 112 else cout << ans << endl; 113return 0; 114}

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

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

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

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

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

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

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

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

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mjk

2020/09/15 12:05

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

2020/09/15 12:56

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

2020/09/15 18:33 編集

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

2020/09/19 11:01

mjkさん、ありがとうございます。 後から問題文での定義(条件)を確認したら、確かにINFが小さかったようです。(10^5とか言われても…) また、競技プログラミングのアドバイス、ほんとにありがとうございます。 そういう情報ってあまり目にしないので参考になりますっ! あと、上記でのDropBoxは公式のでしょうか。 もしそうじゃないのなら、どうやってそういうデータを引っ張り出してきたのでしょうか。 後学のためにお願います。
guest

回答1

0

ベストアンサー

INFが小さすぎます

投稿2020/09/15 12:18

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

BeatStar

2020/09/15 12:57

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問