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

はじめに

• C++で実装しました
• 解説は公式解説がわかりやすいので公式解説を見ましょう
  • http://www.slideshare.net/chokudai/abc023
• その列とその行の飴の数を足してKにするのが基本方針。
• ただし、自分が立っているマスに飴がある場合は重複して計算してしまうので、そこだけ特殊ケースとして考える。
• http://abc023.contest.atcoder.jp/submissions/408334

通ったコード

• コードの中では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 = 10¹⁰あるので、これは int の最大値 2147483648 を超えますね。10⁹ を超えたらintではヤバイと覚えておきましょう。

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

@yoshiki_utakata cntをintではなくlong longに変えたら通ると思います。

— のらスズ (@nola_suz) 2015, 5月 19

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

• 考え方はあっている気がするけど…？
• 提出ページ: http://abc023.contest.atcoder.jp/submissions/408322

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

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

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;
}