Official

D - 9x9 Sum Editorial by Nyaan


この問題は for 文の練習問題です。この問題が解けなかった方は、for 文の機能や使い方を復習してみましょう。
解法を説明します。方針はいくつかありますが、グリッドを 1 マスずつ走査して今見ている数が \(X\) でなければ答えに足す、という方針がシンプルでしょう。すなわち、以下のアルゴリズムを実装すればよいです。

  • \(\mathrm{ans}\) を答えを格納する変数とする。はじめ \(\mathrm{ans}\)\(0\) で初期化されている。
  • \(i = 1, 2, \dots, 9\) の順に以下の操作を行う。
    • \(j = 1, 2, \dots, 9\) の順に以下の操作を行う。
      • 今、上から \(i\) 行目、左から \(j\) 列目のマスを見ているとする。マスに書かれている整数は \(i \times j\) である。この値が \(X\) でなければ、\(\mathrm{ans}\)\(i \times j\) を足す。
  • 操作を全て終了した時点での \(\mathrm{ans}\) の値がこの問題の答えとなる。

計算量はグリッドの縦横の長さを \(N\) として \(\mathrm{O}(N^2)\) となり、今回は \(N = 9\) なので十分高速に動作します。

  • 実装例 (C++)
#include <iostream>
using namespace std;
int main() {
  int X;
  cin >> X;
  int ans = 0;
  for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) {
      if (i * j != X) ans += i * j;
    }
  }
  cout << ans << endl;
}

posted:
last update: