問題 解法 解答 問題 https://atcoder.jp/contests/abc136/tasks/abc136_e 解法 最終的な答えを g，操作後の A_i の値を a_i とすると，a_i % g == 0 であるから，(a_1 + a_2 + ... + a_N) % g == 0 であり，A 全体の総和は操作によって変化しないから，(A_1…

問題 解法 解答 問題 https://atcoder.jp/contests/abc136/tasks/abc136_d 解法 操作の回数が十分に大きいので，子供たちは "RL" となっているような 2 つの連続するマスを行き来するようになる．子供のいるマスが R であるとき，そのマスより右にある最も近…

問題 解法 解答 問題 https://atcoder.jp/contests/abc136/tasks/abc136_c 解法 後ろのマスから見ていき，H_i > H_(i + 1) であるような箇所があったら H_i を 1 削る．それでも H_i が高いままであれば答えは No になる．逆に，このような箇所がなく，全て…

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

問題 解法 解答 問題 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 番…

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

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

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

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

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