今日の13:00 ~ 16:00にあったので出てきました。提出ミスが無ければ、
20 + 20 + 20 + 8 + 20 + 0 = 88.
本選行けるといいんだけど……。
今回特に悔しいのが問4.コンテスト中にDPを思いつかなかった。DPホント苦手。
終わってチャットとかしてたら、みんな解けててびっくりした。
僕は何してたかっていうと、DP考える時間なくて5分くらいでDFS書き上げて[入力1,2]だけ提出した。
あとでみんなの話とか聞いて解いてみたら典型的DPだったぽい。なぜ気づかなかったんだ・・・。
コンテスト後、満点解法であろうものを自分でも書いてみた。
問4(C++)
#include <iostream> #include <vector> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) int main(){ long long dp[100][21] = {0}; int D; cin >> D; D--; vector<int> data(D); rep(i,D) cin >> data[i]; int n; cin >> n; dp[0][data[0]] = 1; for(int i = 1 ; i < D; i++){ rep(j,21){ if( j-data[i] >= 0 ) dp[i][ j-data[i] ] += dp[i-1][j]; if( j+data[i] <= 20) dp[i][ j+data[i] ] += dp[i-1][j]; } } cout << dp[D-1][n] << endl; }