AOJ0262 Making Sugoroku
問題リンク Making Sugoroku
- 解法
マスを頂点にした有向グラフを作ります。
マスiからサイコロを振って進み、マスの指示に従って辿りつけるマスjに向かって有向辺を張ります。あがりマスから逆辺を辿ると、訪問したマスはあがることができるマスになります。あとは、ふりだしマスから有向辺を辿り、辿りついたマス全てがあがりに行けるマスならばOKと判定できます。
- ソース
AOJ0261 Mayan Crucial Prediction
問題リンク Mayan Crucial Prediction
- 解法
入力された日が基準日(0.0.0.0.0 or 2012/12/21)から何日離れているかを計算して、もう片方の暦の上でその日数分、日にちを進めました。
1日ずつカウントするとえらいことになるので、1周期(マヤなら13*20*20*18*20日、西暦なら(365or366)日)まとめて動かしてやれば速く計算できます。
- ソース
AOJ0099 Surf Smelt Fishing Contest II
問題リンク Surf Smelt Fishing Contest II
- 解法
最初はPriorityQueueでゴリオシできると思ったのですが無情のTLE。
なのでセグメント木っぽいの作って解きました。
木のノードには、その区間の最大匹数とそのidを持たせておき、クエリが来るたびに更新します。
解は常に根のノードに入っているので、検索処理は省略できます。
- ソース
AOJ0098 Maximum Sum Sequence II
問題リンク Maximum Sum Sequence II
- 解法
よくある総和の問題です。
(1, 1)-(i, j)の部分行列の総和S[i][j]を前計算しておくと、
(y, x)-(i, j)は
S[i][j] - S[y-1][j] - S[i][x-1] + S[y-1][x-1]
で求められます。
- ソース
AOJ0097 Sum of Integers II
問題リンク Sum of Integers II
- 解法
DPです。
dp[N][X][S]: X以下の数字から異なるN個を選んで、和がSになる組み合わせ数
という表を埋めれば解けます。
- 解法2
DPですが、
dp[N]: 2個の数字を使って和がNになる組み合わせ
という表を用意して
dp[i] * dp[N-i]
の総和を取る方が断然簡単ですね
- ソース
AOJ0096 Sum of 4 Integers II
問題リンク Sum of 4 Integers II
- 解法
よくあるタイプの数え上げ問題です。
(a, b)と(c, d)の組に分け、(a, b)で和sを作る組み合わせ数、(c, d)で和n-sを作る組み合わせ数を掛け合わせていけば解けます。
- ソース
