水色プログラミング

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

AtCoder その他の問題

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 個あり,それらからいくつか両端以外で重ならないように選ぶとき,最大でいくつ選べるかを求め,辞書順最小の組み合わせを求める問題. 解法 区間をソートし,時間を後ろから見てい…