こういうのをスパッと解けるようになりたい
問題概要
以上 以下の整数の組 であって、
- の最上位の値と の一の位の値が等しい
- の最上位の値と の一の位の値が等しい
という条件を満たすものが何個あるかを求めよ。
制約
考えたこと
ペアリングの個数を数えよ、といわれたときの考察として、よくあるのが
- を固定して、それに応じた が何個あるかを高速に数える
という方法だと思う。だが今回はこの方針で突き進もうとすると辛い気持ちになる。少し考えてみると
を固定したときの の個数は、 の「最上位の値」と「一の位の値」のみに依存する
ということが見えてくる。 であっても、 であっても、それに対応する の個数は等しい。よって、方針を少し変形して、以下のようにすれば OK!!!
「最上位の値 」と「一の位の値 」を固定したときの、それを満たす 以上 以下の整数の個数 num[ ][ ] を求める (この個数は でも でも等しい)
の組としてありうる 通りの組合せそれぞれについて、num[ ][ ] × num[ ][ ] の値を合算する
num[ ][ ] は、単純に から までの値それぞれについて、「最上位の値」と「一の位の値」を求めてあげて、それに応じた num の値をインクリメントすれば OK。計算量は 。
#include <iostream> #include <vector> #include <string> using namespace std; #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl int main() { int N; cin >> N; long long res = 0; vector<vector<long long>> num(10, vector<long long>(10, 0)); for (int n = 1; n <= N; ++n) { vector<int> d; int nn = n; while (nn) { d.push_back(nn % 10); nn /= 10; } int a = d[0]; int b = d.back(); if (!a || !b) continue; ++num[a][b]; } for (int a = 1; a < 10; ++a) { for (int b = 1; b < 10; ++b) { res += num[a][b] * num[b][a]; } } cout << res << endl; }