SRM 720 Div1 - ei1333の日記

-o- 323.21pts. 107th. 1686 -> 1703(+17).

easy 3 分だけ間に合わなかった, 悲しいね(悲しいので.

easy と med の順番警察.

Easy (250) Sum Product

問題概要

0-9 の数字がそれぞれ ${\mathrm{amount}[i](1 \le \mathrm{amount}[i] \le 100)}$ 個ある.

これらの数字を使って ${\mathrm{blank1}(1 \le \mathrm{blank1} \le 100)}$ 桁の値と ${\mathrm{blank2}(1 \le \mathrm{blank2} \le 100)}$ 桁の値の組 ${(A, B)}$ を構成する. ここで reading-0 を許容する.

考えられるすべての相異なる組 ${(A, B)}$ それぞれに対して ${A \times B}$ を計算し, その総和を ${10^9 + 7}$ で割った余りで求めよ.

解法

DPをします(なんですぐDPをしなかったんだろう).

${A}$ の ${x}$ 桁目を ${i}$ にして, ${B}$ の ${y}$ 桁目を ${j}$ にすると仮定する. これを満たす組 ${(A, B)}$ の個数は, 以下の問題を解くことでわかる.

0-9の数字がそれぞれ ${\mathrm{a}[i]}$ 個ある. これらの数字から ${k}$ 個を選んで ${k}$ 桁の値を構成する. 考えられる値の個数を求めよ.

これは重複順列っぽい問題であり, DPで求めることができる.

dp[idx][rest] := ${0}$ から ${idx}$ までの数字のみを使うものうち, rest 桁からなる相異なる値の個数

遷移は次の通り.

dp[idx][rest + j] += dp[idx - 1][rest] * ${{}_{rest + j} \mathrm{ C }_{j} }$ (数字 ${idx}$ を ${j}$ 個加えて ${rest + j}$ 桁からなる値をつくるのは, ${rest + j}$ 個のうち ${j}$ 箇所選んで数字 ${idx}$ を挿入するような操作なのでまあはい.)

DP をして ${(A, B)}$ の組の個数 ${p}$ が求まったとする. このようなアが最終的な解に影響するのは ${10^x * i * 10^y * j * p}$ みたいな雰囲気になるので, あとは適当にえいしてえいして足せば解ける.

DP の計算量は ${O(10 (\sum \mathrm{amount}[i]) \mathrm{amount}[i])}$ なので, 全体の計算量は ${O(1000 (\sum \mathrm{amount}[i]) \mathrm{amount}[i])}$ ??.

なんかDP部分がアレなのでもっとはやくなりそうだけどこれで十分.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int mod = 1e9 + 7;

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return(1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return(ret);
}
inline int64 modInv(int64 a)
{
  return(modPow(a, mod - 2));
}
inline int64 modCombination(int p, int q)
{
  static int64 fact[202020], rfact[202020];
  if(fact[0] == 0) {
    fact[0] = rfact[0] = 1;
    for(int i = 1; i < 102020; i++) {
      fact[i] = fact[i - 1] * i % mod;
      rfact[i] = modInv(fact[i]);
    }
  }
  if(q < 0 || p < q) return(0);
  return(fact[p] * rfact[q] % mod * rfact[p - q] % mod);
}


int dp[1001];

int64 solve(vector< int >& amount, int rest)
{
  vector< int > dp(rest + 1, 0);
  dp[0] = 1;
  for(int l = 0; l < 10; l++) {
    for(int i = rest; i >= 0; i--) {
      for(int j = amount[l]; j >= 1; j--) {
        if(i + j > rest) continue;
        (dp[i + j] += dp[i] * modCombination(i + j, j) % mod) %= mod;
      }
    }
  }
  return(dp[rest]);
}

class SumProduct
{
public:
  int findSum(vector<int> amount, int blank1, int blank2)
  {
    int64 Asum = 0, Bsum = 0;
    for(int64 i = 0, fact = 1; i < blank1; i++) {
      (Asum += fact) %= mod;
      (fact *= 10) %= mod;
    }
    for(int64 i = 0, fact = 1; i < blank2; i++) {
      (Bsum += fact) %= mod;
      (fact *= 10) %= mod;
    }

    int64 ret = 0;
    for(int i = 1; i < 10; i++) {
      if(amount[i] == 0) continue;
      amount[i]--;
      for(int j = 1; j < 10; j++) {
        if(amount[j] == 0) continue;
        amount[j]--;
        (ret += i * j * solve(amount, blank1 + blank2 - 2) % mod * Asum % mod * Bsum % mod) %= mod;
        amount[j]++;
      }
      amount[i]++;
    }
    return ret;
  }
};

Med (450) Distinct Grid

問題概要

各行, 各列の異なる値の数が最大でちょうど ${k(1 \le k \le \frac {n} {2})}$ 個となり, 行列全体で異なる値の個数が最大となるような ${n \times n(3 \le n \le 50)}$ 行列を構成せよ.

解法

なんかINF人解かれていることを信じるとよくわからないけど解けた気持ちになる問題.

${n}$ 個異なる行列は

みたいに構成できる. ここで ${k}$ 個異なるようにしたいときは, ${k}$ 以上の要素を ${k}$ にすればよい. たとえば ${k = 3}$ のとき,

で, この行列の ${k - 1}$ 以下の要素に着目する.

12****
2****1
****12
***12*
**12**
*12***

各行各列をみたときに相異なる値が ${1}$ つのみなので影響している範囲はそれぞれ独立. 適当に番号を振りなおしても答えは変わらない.

ab****
c****d
****ef
***gh*
**ij**
*kl***

なんとなく最大な気がするので信じてこれを出すと通る(最大の証明してないね, 雰囲気で競プロをしている).

ソース

えぇ…

#include <bits/stdc++.h>
using namespace std;

class DistinctGrid
{
public:
  vector<int> findGrid(int n, int k)
  {
    vector< vector< int > > mat(n, vector< int >(n, 0));
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) mat[i][j] = (i + j) % n;
    }

    int ptr = 114514;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        if(mat[i][j] >= k - 1) mat[i][j] = k - 1;
        else mat[i][j] = ptr++;
      } 
    }

    vector< int > vs;
    for(int i = 0; i < mat.size(); i++) for(int j = 0; j < mat.size(); j++) vs.push_back(mat[i][j]);
    return(vs);
  }
};