@chani

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

ABC420のB問題のコード修正をお願いします。

Q&A

Closed

ABC420のB問題について教えていただけないでしょうか?
テストケース27個中9個ACで、それ以外WAでした。

#include
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
using ll = long long; using ld = long double;

int main() {
ll n,m; cin >> n >> m;
vector point(n,0);
vector> masu(n,vector (m));
rep(i,0,n)rep(j,0,m) cin >> masu[i][j];
ll cnt1 = 0, cnt0 = 0;
vector index0,index1;
rep(j,0,m) {
index1.clear();
index0.clear();
cnt0 = 0;
cnt1 = 0;
rep(i,0,n) {
if(masu[i][j] == 0) cnt0++,index0.push_back(i);
else if(masu[i][j] == 1) cnt1++,index1.push_back(i);
}
if(cnt0 == 0 || cnt1 == 0) rep(i,0,point.size()) point[i]++;
else if(cnt0 < cnt1) rep(i,0,index0.size()) point[index0[i]]++;
else if(cnt0 > cnt1) rep(i,0,index1.size()) point[index1[i]]++;
}
//sort(point.begin(),point.end(),greater());
auto& ans = *max_element(point.begin(),point.end());
rep(i,0,point.size()) {
if(point[i] == ans) {
cout << i+1 << " ";
}
}
cout << endl;
return 0;
}

0 likes

2Answer

原因を一言で言うなら「データが正しく読み取れていない」からです。

今回の入力は[0 1 0 1]といった間隔をあけたデータではなく、[0101]という詰めた形で提示されています。
これをlong long型で読み取らせると{0,1,0,1}というバラバラのデータではなく{101}という1つの整数として格納されてしまいます。

なので今回は、バラバラの値として読み取らせる工夫をする必要がありました。
chaniさんのコードであればchar型で受け取るのがわかりやすいと思います。
char型であれば1文字ずつ読み取ってくれます。

要するに、1010を「1と0の整数のデータ」ととらえるのではなく「1と0の文字のデータ」としてとらえることで正しく入力を受け取ることができます。

事実、コードをlong long型かchar型に変えるだけでACできました。
ので理論の構築については全く問題ないようで、安心してください。

実装例
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
using ll = long long; using ld = long double;

int main() {
    ll n,m; cin >> n >> m;
    vector<ll> point(n,0);

    //ここの読み取りをlong longからcharに変更
    vector<vector<char>> masu(n,vector<char> (m));
    rep(i,0,n)rep(j,0,m) cin >> masu[i][j];

    ll cnt1 = 0, cnt0 = 0;
    vector<ll> index0,index1;
    rep(j,0,m) {
        index1.clear();
        index0.clear();
        cnt0 = 0;
        cnt1 = 0;
        rep(i,0,n) {
            //文字で受け取っているので''を付けて文字で比較
            if(masu[i][j] == '0') cnt0++,index0.push_back(i);
            else if(masu[i][j] == '1') cnt1++,index1.push_back(i);
        }
        if(cnt0 == 0 || cnt1 == 0) rep(i,0,point.size()) point[i]++;
        else if(cnt0 < cnt1) rep(i,0,index0.size()) point[index0[i]]++;
        else if(cnt0 > cnt1) rep(i,0,index1.size()) point[index1[i]]++;
    }

    //以降そのまま
    //sort(point.begin(),point.end(),greater<ll>());
    auto& ans = *max_element(point.begin(),point.end());
    rep(i,0,point.size()) {
        if(point[i] == ans) {
        cout << i+1 << " ";
      }
    }
    cout << endl;
    return 0;
}

1Like

Comments

  1. @chani

    Questioner

    入力の方に問題があったんですね!答えていただきありがとうございます!!

コードを見た感じ、いくつか修正ポイントがあります。

  1. vector point(n,0); の部分ですが、C++ では vector<int> point(n, 0); のように型を明示しないとコンパイル環境によってはエラーや挙動不安定になることがあります。
  2. vector> masu(n, vector<int>(m)); も同じで、vector<vector<int>> masu(n, vector<int>(m)); に修正した方が安全です。
  3. 最後の出力部分で auto& ans = *max_element(...) としていますが、auto ans = *max_element(...) にする方がわかりやすいです。参照でなくても問題ありません。
  4. ロジック的には「列ごとに 0 と 1 を数えて、多い方を選んで point に加点する」という方針だと思いますが、else if(cnt0 < cnt1)else if(cnt0 > cnt1) の場合、イコール(=)の時に何も処理されないので注意してください。ここは要件次第ですが、tie のときの扱いを決める必要があります。

この辺を直せば WA のテストケースが減ると思いますよ 👍

1Like

Comments

  1. @chani

    Questioner

    回答ありがとうございます!助かります(^v^)

Your answer might help someone💌