AtCoder Beginner Contest 200 C - Ringo's Favorite Numbers 2
問題
200という整数が大好きなりんごさんのために、次の問題を解いてください。
N個の正整数からなる数列Aが与えられるので、以下の条件をすべて満たす整数の組(i,j)の個数を求めてください。
- <
制約
- 入力は全て整数
考えたこと
(i,j) = (1,3),(1,4)ならば、(3,4)も該当し、かつ3と4は調べなくてよさそうです。というおそらくそうだろうでゴリ押しました。
コード
#define _GIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) #define all(v) v.begin(), v.end() using namespace std; using ll = long long; bool b[2 * 100000 + 10]; int main(void) { int N; cin >> N; vector<ll> A(N); rep(i, N) cin >> A[i]; ll ans = 0; for (int i = 0; i < A.size() - 1; ++i) { if (b[i]) continue; ll count = 0; for (int j = i + 1; j < A.size(); ++j) { if ((A[i] - A[j]) % 200 == 0) { ++count; ++ans; ans += count - 1; b[j] = true; } } } cout << ans << endl; return 0; }
解説を読んで
計算式が条件にあり、全探索でだめなら計算式の変換が必要のようです。