AOJ2332 Space-Time Sugoroku Road
問題概要
1~Nのマスとサイコロがある。各マスには数字が書き込まれている。
・ が正数の時、駒をだけ進める。
・ が負数の時、駒をだけ戻す。
・ が0の時、サイコロを振りのいずれかに移動する。
このとき1からNに到達するために必要なサイコロの振る回数は何回か?
考えたこと
説明文通りであるが、無限ループに気を付ける。
サイコロの振ることを重み1、マスによる移動を重み0としたときのダイクストラ法を考える。
各マスを頂点とすると各頂点から出る辺はせいぜい1か6なので十分間に合う。
最短経路を考えることでループを枝刈りできるのもうれしい。
最初、メモ化再帰で通そうとしたがsample12で落ちた。しばらく考えたが分からなかったので諦めた。(ループ判定で引っかかってそう)
ACコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,s,n) for(int i=s;i<(int)n;++i) #define REP(i,n) FOR(i,0,n) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() int dist[100010][2]; int P[100010]; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12); int N; cin >> N; REP(i,N) cin >> P[i]; REP(i,N) dist[i][0] = dist[i][1] = INT_MAX; priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q; q.push(make_pair(0, make_pair(0, 0))); dist[0][0] = 0; while(q.size()){ auto p = q.top(); q.pop(); int d = p.first, v = p.second.first; int f = p.second.second; if(dist[v][f] < d) continue; if(f){ int u = v + P[v]; if(P[u] == 0){ if(dist[u][0] > dist[v][1]){ dist[u][0] = dist[v][1]; q.push(make_pair(dist[u][0], make_pair(u, 0))); } }else{ if(dist[u][1] > dist[v][1]) { dist[u][1] = dist[v][1]; q.push(make_pair(dist[u][1], make_pair(u, 1))); } } }else{ for(int i=1; i<=6; i++){ int u = min(i+v, N-1); if(P[u] == 0){ if(dist[u][0] > dist[v][0] + 1){ dist[u][0] = dist[v][0] + 1; q.push(make_pair(dist[u][0], make_pair(u, 0))); } }else{ if(dist[u][1] > dist[v][0] + 1) { dist[u][1] = dist[v][0] + 1; q.push(make_pair(dist[u][1], make_pair(u, 1))); } } } } } cout << min(dist[N-1][0], dist[N-1][1]) << endl; return 0; }
AOJ 1249 Make a Sequence(AOJ ICPC 200)
問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1249
問題概要
3次元空間でTic-Tac-Toe(マルバツゲーム)を行う。x座標, y座標, z座標のそれぞれの方向ベクトルについてM個以上同じ色が隣接している場合その手を打った色が勝ちとなる。
毎ターンごとにx座標とy座標の情報が与えられるので、勝敗の判定を行う。勝敗が決まらなかった場合、Drawを出力する。
LeetCode 1335. Minimum Difficulty of a Job Schedule
問題:https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
概要:配列aが与えられる. これをd分割したときの区間ごとの最大値の和の最小値を求める
考えたこと:区間分割なので「どこで区切ったか」、「どこまで区切ったのか」という情報を扱いたくなる。今回の場合、これは次のように添え字を持つことで動的計画法で実現できる。
dp[i][j] = i番目まで見て、j個の集合が存在する
次に遷移について考える。
i-1番目までを見たとき, 次の分割の番地はi
int minDifficulty(vector<int>& jobDifficulty, int d) { long dp[310][15]; for(int i=0; i<310; i++){ for(int k=0; k<15; k++){ dp[i][k] = INT_MAX; } } dp[0][0] = 0; int n = jobDifficulty.size(); for(int i=0; i<n; i++){ for(int j=i; j<n; j++){ long maxV = 0; for(int k=i; k<=j; k++){ maxV = max(maxV, (long)jobDifficulty[k]); } for(int k=d; k>0; k--){ if(dp[i][k-1] == INT_MAX) continue; dp[j+1][k] = min(dp[j+1][k], dp[i][k-1] + maxV); } } } if(dp[n][d] == INT_MAX) return -1; return dp[n][d]; }
AtCoder Beginner Contest 029 D - 1
問題リンク
atcoder.jp
考えたこと
1以上N以下の自然数に含まれる1の数を数え上げればよいためこれは桁dpで解くことができる.
状態の持ち方としては,
dp[i][j][k] := i番目までを見た時, (jはtightかどうか)1をk個もつような数字の個数
とする. なお, 桁数はせいぜい9なので, ある数字がもつ1の数も9が最大.
#include <bits/stdc++.h> int main() { cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15); string s; cin >> s; ll dp[15][2][10]={0}; dp[0][0][0]=1; for(int i=0; i<s.size(); i++){ int num = s[i] - '0'; for(int j=0; j<2; j++){ int ma = 10; if(j == 0){ ma = num + 1; } for(int d=0; d<ma; d++){ for(int k=0; k<10; k++){ dp[i+1][j | (d != num)][k + (d == 1)] += dp[i][j][k]; } } } } int ans = 0; for(int i=0; i<10; i++){ ans += (dp[s.size()][0][i]+dp[s.size()][1][i])*i; } cout << ans << endl; return 0; }