水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder その他の問題

Typical DP Contest:D - サイコロ

問題 解法 解答 問題 beta.atcoder.jp 解法 まず,D を素因数分解し,2, 3, 5 以外の素因数があった場合は,答えは 0 と決まる. そうでないとき,「dp(i, tw, th, fi) := i 回サイコロを振り,素因数 2 が tw 回,素因数 3 が th 回,素因数 5 が fi 回出た…

Typical DP Contest:C - トーナメント

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j) := 人 i が j 回戦目で勝つ確率」と DP を立てる.人 i と j 回戦目で当たる可能性がある人を人 l, l + 1, l + 2, ... , r とし,人 a が人 b に勝つ確率を p_(a, b) とすると, dp(i, j) = dp(i, j - …

Typical DP Contest:B - ゲーム

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j, f) := 左の山から i 個,右の山から j 個取られていて今のターンが f の時のすぬけ君の取るものの価値の合計の最大値」と DP を立てる.DP 内で f に応じて処理を変える.具体的には,f がすぬけ君の場…

Typical DP Contest:A - コンテスト

問題 解法 解答 問題 beta.atcoder.jp 解法 N <= 100 なので,(i - 1) 番目までの要素でできた点数それぞれに対して i 番目の要素を足し合わせたものを新しく答えに追加すればよい.重複が生じるものがあるので,set を使って処理する.O(N^2 * logN). 解答…

AtCoder Regular Contest 033:D - 見たことのない多項式

問題 解法 解答 問題 D - 見たことのない多項式 N 次多項式 P(x) があり,P(0), P(1), ... , P(N) が分かっているとき,P(T) を求める問題. 解法 さっぱり分からないので解説を読んだところ,ラグランジュ補間というものを使うらしいと分かった.これは,P(…

AtCoder Regular Contest 032 : D - アットコーダーモンスターズ

問題 解法 解答 問題 D - アットコーダーモンスターズ N 匹のモンスターには攻撃値と防御値がそれぞれ決まっていて,この中から K 匹選んでチームを作りたい.このチームの「不安定度」はチーム内のモンスター同士の攻撃値の差と防御値の差の min の max で…

AtCoder Regular Contest 035:C - アットコーダー王国の交通事情

問題 解法 解答 問題 C - アットコーダー王国の交通事情 全ての頂点が連結であるグラフがあり,この全頂点間の最短距離の和を S とする.「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので,K 回それぞれに対して S を求める問題…

AtCoder Regular Contest 032:C - 仕事計画

問題 解法 解答 問題 C - 仕事計画 a_i と b_i を始点・終点とする区間が N 個あり,それらからいくつか両端以外で重ならないように選ぶとき,最大でいくつ選べるかを求め,辞書順最小の組み合わせを求める問題. 解法 区間をソートし,時間を後ろから見てい…