AOJ0557 A First Grader


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

AOJ0557 A First Grader

サイト

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557

参考サイト

http://d.hatena.ne.jp/Respect2D/20110212/1297501157

https://speakerdeck.com/kagamiz/aoj-0557-a-first-grader-jie-shuo

解説

+と-の2択を選びつつ様々な制限の元ansに一致する場合数を列挙します。

2択で処理を進めるので全探索するとO(2^n)です。取りあえず再帰で全探索コードを考えてみましょう。

数列の今見ている項とそこまでの計算結果の2つの状態が必要です。

終了条件でansと計算結果が一致していれば場合の数が1つ生じます。以下のコード上では例外処理が省略されています。

int rec(int index, int sum) {
  if(index == tail) return sum == ans;
  return rec(index+1, sum + seq[index+1]) + rec(index+1, sum - seq[index+1]);
}

同じ項を見ているときそこまでの計算結果も同じなら、その後の計算にダブりが生じます。何度も同じ計算をしないよう、計算結果の再利用をしましょう。メモ化再帰です。

int rec(int index, int sum) {
  if(memo[index][sum] != -1) return memo[index][sum];
  if(index == tail) return sum == ans;
  return memo[index][sum] = rec(index+1, sum + seq[index+1]) + rec(index+1, sum - seq[index+1]);
}

これで無駄な計算が無くなり、O(ns) 100*21 = 2100通りとなりました。

再帰を考えることでindexやsumという状態を持つことが分かったので今度はDPしてみましょう。高校数学の漸化式のと同じようにDPには「初期条件」と「式そのもの」が必要です。

DPの式は以下です。

dp[今見ている数列のi番目][計算結果] := 場合の数

漸化式について帰納的に遷移を考えましょう。「計算結果」は「i-1番目の計算結果にseq[i]を足したものか、seq[i]を引いたもの」です。場合の数はその状態に辿り着くまでの経路数の和です。

初期条件を考えましょう。漸化式の計算が起こる前に予め場合の数が決まる状態が1つ存在します。場合の数は各項で+か-の二択を選択することで増加していきますが、数列の先頭ではその選択が起こりません。(「必ず+が選択される」とも言い換えられます)すなわち dp[0][seq[0]] = 1 を必ず言うことができるので、これが初期条件となります。

解答コード

#include <iostream>
using namespace std;
long long dp[101][21]; // 0で初期化済み
int main() {
  int n, ans;
  int seq[100];
   
  cin >> n;
  for(int i=0; i<n-1; i++) {
    cin >> seq[i];
  }
  cin >> ans;
 
  dp[0][seq[0]] = 1;
  for(int i=1; i<n-1; i++) {
    for(int j=0; j<=20; j++) {
      if(j+seq[i]<=20) dp[i][j+seq[i]] += dp[i-1][j];
      if(j-seq[i]>=0)  dp[i][j-seq[i]] += dp[i-1][j];
    }
  }
 
  cout << dp[n-2][ans] << endl;
  return 0;
}