競プロ典型90問 046(★3) 組合せの問題

046 - I Love 46（★3）

問題

3つの長さ N の数列 A, B, C が与えられる。

が46の倍数となるの選び方の総数を求める。

解法

3つの数列が最大10⁵と制約が厳しいため全探索ではTLEになってしまう。

そのため、最初にmodを取ることで、0〜45の46種類に絞る。

46³ = 97336通りしかないので、これで全探索が可能になる。

所感

制約を見て実直に全探索ではなく、条件を絞ることは早めに気づけた。

式があっていたのにWAが出てしまい、30分くらい悩んだ。

mapをint型にしていたので、オーバーフローしていたのが原因だった。

少しでもオーバーフローのリスクがある場合は迷わず long long を使おうと思う。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main()
{
    int    n, x, y, z;
    ll ans = 0;
    cin >> n;
    map<ll, ll> a, b, c;

    rep(i,n)
    {
        cin >> x;
        a[x % 46]++;
    }
    rep(i,n)
    {
        cin >> y;
        b[y % 46]++;
    }
    rep(i,n)
    {
        cin >> z;
        c[z % 46]++;
    }

    for (int i = 0; i < 46; i++) {
        for (int j = 0; j < 46; j++) {
            for (int k = 0; k < 46; k++) {
                if ((i + j + k) % 46 == 0)
                    ans += a[i] * b[j] * c[k];
            }
        }
    }
    cout << ans << endl;
    return 0;
}