人権なし

競プロで解いた問題や開発の進捗などの記録です

HackerRank 問題

Kodaman コンテスト:M - Mad Time Traveler

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/mad-time-traveler 解法 行先の候補にコスト 0 の有向辺を張ったグラフを考える.そして,各頂点に世界線変動率を 7 で割った余りごとに状態を持たせる拡張ダイクス…

Kodaman コンテスト:L - Let's Shoot!

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/lets-shoot/problem 解法 以下の DP を考える. dp(i, a, b, c) := i - 1 番目まで見て Type 1 に a 回,Type 2 に b 回,Type 3 に c 回トレーニングしたとき,i 番…

Kodaman コンテスト:K - Customers

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/k-customers-2 解法 一つ目のクエリは,各お客さんの入店・出店時刻を独立に考えることが出来るから,X と Y を昇順にソートしておき,std::upper_bound() を用いる…

Kodaman コンテスト:J - 異世界転生2

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/2-82 解法 まず,仕事を開始時刻が早い順にソートしておく.次に,以下の DP を考える. dp(i) := 次に i 番目の仕事をすることが可能な時,i 番目以降の仕事で得ら…

Kodaman コンテスト:I - is this tournament correct?

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/i-is-this-tournament-correct 解法 チームを試合数の少ない順にソートしておく.試合数が 1 であるもの(同率が複数ある場合は適当な 1 チーム)をその次に試合数の…

Kodaman コンテスト:G - Osmium_1008と時間旅行

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/osmium1008-and-timetravel 解法 年数が負の値になりうるので,全て 2*10^5 を加算して考える.ここで以下の DP を考える. dp(i, j) := i - 1 個目までの飴を使い,…

Kodaman コンテスト:F - disastrous gemini

問題 解法 解答 問題 https://www.hackerrank.com/contests/kodamanwithothers/challenges/disastrous-gemini 解法 A_i - B_i の差が大きい問題の時にクーラーを使うのが最適.初めに A_i の和と A_i - B_i の値を降順にソートしておき,A_i の和から A_i - …