読者です 読者をやめる 読者になる 読者になる

LoL/LJL好きのエンジニアのブログ

技術的な話やら、最近はLoLやLJLの話など。

AtCoder Beginner Contest #023 C - 収集王 が通った(追記)

はじめに

通ったコード

  • コードの中ではstoneとなってますが、これは飴のことです。
int main(int argc, const char * argv[]){
    int R, C, k, n, r[100000], c[100000];
    cin >> R >> C >> k >> n;
    
    int stone_in_r[100000], stone_in_c[100000];
    REP(i,100000){
        stone_in_r[i] = 0;
        stone_in_c[i] = 0;
    }
    
    REP(i,n){
        cin >> r[i] >> c[i];
        r[i]--, c[i]--; // インデックスを-1するあたり間違えないように
        
        // r[i]列にあるストーン、c[i]行にあるストーンの数を加算
        stone_in_r[r[i]]++;
        stone_in_c[c[i]]++;
    }
    

    // i個飴がある row, col の数を記録しておく
    int rcount_with_stones[100001], ccount_with_stones[100001];
    REP(i,100001){
        rcount_with_stones[i] = 0;
        ccount_with_stones[i] = 0;
    }

    REP(i,R) rcount_with_stones[stone_in_r[i]]++;
    REP(i,C) ccount_with_stones[stone_in_c[i]]++;
    
    long long cnt = 0;
    REP(i,k+1){
        cnt += rcount_with_stones[i] * ccount_with_stones[k-i];
    }
    
    REP(i,n){
        // r[i] c[i] の石を重複すてカウントしているので、
        // 合計がkなら実は間違っている -> 引き
        // 合計がk+1なら実は正しい -> 足す
        int sum = stone_in_r[r[i]] + stone_in_c[c[i]];
        if(sum == k) cnt--;
        if(sum == k+1) cnt++;
    }
    
    cout << cnt << endl;
}

つまづき点

  • マス目は 0 - 99999 のインデックスを持った配列でいいけど、石の数は 0 - 100000 個を考えなくてはいけないので、配列を 100001 確保しなければいけない
  • 以下の「通らなかったコード」参照

通らなかったコード

通らなかった原因

答えの数字は最大 100000*100000 = 1010あるので、これは int の最大値 2147483648 を超えますね。109 を超えたらintではヤバイと覚えておきましょう。

このご指摘は @nola_suz さんにいただきました。ありがとうございます。

以下、過去のブログの内容

f:id:yoshiki_utakata:20150519123145p:plain

何か引っかかってるケースが存在しているっぽい?

以下メイン部分のソースコード

int main(int argc, const char * argv[]){
    int R, C, k, n, r[100000], c[100000];
    cin >> R >> C >> k >> n;
    
    int stone_in_r[100000], stone_in_c[100000];
    REP(i,100000){
        stone_in_r[i] = 0;
        stone_in_c[i] = 0;
    }
    
    REP(i,n){
        cin >> r[i] >> c[i];
        r[i]--, c[i]--;
        
        // r[i]列にあるストーン、c[i]行にあるストーンの数を加算
        stone_in_r[r[i]]++;
        stone_in_c[c[i]]++;
    }
    
    int rcount_with_stones[100001], ccount_with_stones[100001];
    REP(i,100001){
        rcount_with_stones[i] = 0;
        ccount_with_stones[i] = 0;
    }
   
    // i個飴がある row, col の数を記録しておく
    REP(i,R) rcount_with_stones[stone_in_r[i]]++;
    REP(i,C) ccount_with_stones[stone_in_c[i]]++;
    
    int cnt = 0;
    REP(i,k+1){
        cnt += rcount_with_stones[i] * ccount_with_stones[k-i];
    }
    
    REP(i,n){
        // r[i] c[i] の石を重複すてカウントしているので、
        // 合計がkなら実は間違っている -> 引き
        // 合計がk+1なら実は正しい -> 足す
        int sum = stone_in_r[r[i]] + stone_in_c[c[i]];
        if(sum == k) cnt--;
        if(sum == k+1) cnt++;
    }
    
    cout << cnt << endl;
}