「AOJ0557 A First Grader」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*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;
}
||<
*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;
}
||<
