C - 三つ組の積 / 第13回 アルゴリズム実技検定 (PAST13)

問題

長さ の整数列 が与えられる。

このとき、次の条件を満たす整数 の個数を求めよ。

• かつ を満たす が存在する。

入力

まず最初の1行目に整数 が与えられる。

次の1行に、 個の整数 が順に与えられる。

条件

• 
• 

出力

答えとなる個数を1行で出力すること。

解法

問題としては「整数 の個数を求める」というものなので、単純に に関してforループを回して積を求め、求めた積が既出かどうかで判断を行い個数を数えるという方法で解くことができます。

3重のforループを回すため、 の計算量がかかりますが、 であるので、最大でも約 回程度の計算で済むことから、実行時間制限にも十分に間に合うと考えられます。

ソースコード

main() 関数の中に、直接答えを出力する部分を実装しました。

int n, a[105], ans = 0; // ans は答えとなる個数を表す
map<int, bool> used; // used は既に積の値があるかどうかを管理する map

int main() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) { // i < j より、 j = i + 1 からループを回す
      for (int k = j + 1; k <= n; k++) { // j < k より、 k = j + 1 からループを回す
        int now = a[i] * a[j] * a[k];
        if (!used[now]) { // もし積の値として既出でないならば、答えとなる個数を1つ増やす
          used[now] = true;
          ans++;
        }
      }
    }
  }

  cout << ans << endl; // 答えの出力

  return 0;
}

• 提出したコード: https://atcoder.jp/contests/past202212-open/submissions/48227444
• GitHub

感想

問題文の書き方的に、「 が与えられてそれを満たす の値の個数を求めよ」という問題かと思ってしまいそうになりました。