[ARC136] D - Without Carry

[Q] https://atcoder.jp/contests/arc136/tasks/arc136_d

解説ACする。多次元累積和。
考察

 a   x
04 | 95
08 | 91
12 | 87
16 | 83

99 - a = xとしたときに、
04の相方は、9以下 * 5以下の2桁になるべき。

・++DP[9][5]にマーキング(いもす)

  0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 ...
2 0 0 0 0 ...
3 0 0 0 0 ...
4 0 0 0 0 ...
5 0 0 0 0 0 0 0 0 0 1
6
7
8
9


・二次元累積和をとれば、04とのペアになる値をマっピングできる。

  0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1 1 
3 1 1 1 1 1 1 1 1 1 1 
4 1 1 1 1 1 1 1 1 1 1 
5 1 1 1 1 1 1 1 1 1 1 
6 0 0 0 0 0 0 0 0 0 0 
7
8
9

1. 入力値aに対して、999999 - a を、6次元DP[a][b][c][d][e][f]にマーキングする
2. 6次元累積和を、9から0に集めるようにとる。
DP[0][0][0][0][0][0] = Nになるはず。
3. DP[a]が、そのaの相方の数になる。
4. 減算すべきものが2つ
(a) 444444以下は、自身とのペアを加算してしまっているので、-1する
(b) ペアを2回加算することになるので、最後に/2する

Q. 6次元累積和？
A. 1から3まで考える

・1次元なら、
0 0 1 0 0 1 0
<------------
2 2 2 1 1 1 0

・2次元なら、
  0 1 2 3 4
0 0 0 1 0 0
1 0 1 0 0 0
2 1 0 0 0 0

1. まず<-
  0 1 2 3 4
0 1 1 1 0 0
1 1 1 0 0 0
2 1 0 0 0 0
 
2. つぎ↓
  0 1 2 3 4
0 1 1 1 0 0
1 2 2 1 0 0
2 3 2 1 0 0

Q. 3次元

if(i == 0){}
else if (i==1){} ... 
else if (i==2){} ... 
をやめたい

実装

ll DP[10][10][10][10][10][10];
ll A[1000010];

void acc_init(ll &a, ll &b, ll &c, ll &d, ll &e, ll &i) {
 // 04|95 なら95以下に加算させたい
 // 9から0におろす
 if (i == 0) {
   for (ll j = 9; j > 0; --j) {
     DP[j - 1][a][b][c][d][e] += DP[j][a][b][c][d][e];
   }
 } else if (i == 1) {
   for (ll j = 9; j > 0; --j) {
     DP[a][j - 1][b][c][d][e] += DP[a][j][b][c][d][e];
   }
 } else if (i == 2) {
   for (ll j = 9; j > 0; --j) {
     DP[a][b][j - 1][c][d][e] += DP[a][b][j][c][d][e];
   }
 } else if (i == 3) {
   for (ll j = 9; j > 0; --j) {
     DP[a][b][c][j - 1][d][e] += DP[a][b][c][j][d][e];
   }
 } else if (i == 4) {
   for (ll j = 9; j > 0; --j) {
     DP[a][b][c][d][j - 1][e] += DP[a][b][c][d][j][e];
   }
 } else if (i == 5) {
   for (ll j = 9; j > 0; --j) {
     DP[a][b][c][d][e][j - 1] += DP[a][b][c][d][e][j];
   }
 }
}

int main() {
 cincout();

 ll N;
 cin >> N;

 ll k[6];
 rep(i, N) {
   ll a;
   cin >> a;
   A[i] = a;

   // 自分自身の反対をマッピングする
   ll x = 999999 - a;
   rep(j, 6) {
     k[j] = x % 10;
     x /= 10;
   }
   ++DP[k[0]][k[1]][k[2]][k[3]][k[4]][k[5]];
 }

 // 6次元の累積和をとる
 rep(i, 6) {
   rep(a, 10) rep(b, 10) rep(c, 10) rep(d, 10) rep(e, 10) {
     acc_init(a, b, c, d, e, i);
   }
 }

 ll ans = 0;
 rep(i, N) {
   ll a = A[i];
   bool dup = true;
   rep(j, 6) {
     // 自分自身で判定する
     k[j] = a % 10;
     a /= 10;
     if (k[j] >= 5) dup = false; // 5以上を含むなら、自身との重複なし
   }
   ans += DP[k[0]][k[1]][k[2]][k[3]][k[4]][k[5]];
   if (dup) --ans; // 全部が4以下なら、自身が重複
 }
 cout << ans / 2 << endl;
}

https://atcoder.jp/contests/arc136/submissions/30988333