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

問題 解法 解答 問題 https://atcoder.jp/contests/abc133/tasks/abc133_e 解法 適当な頂点を根とする根付き木を考える．根から DFS をしていく．頂点 v にいるとき，その頂点の子の配色の通り数を考える．子は頂点 v の親と頂点 v の色それぞれと互いに異な…

問題 解法 解答 問題 https://atcoder.jp/contests/abc133/tasks/abc133_d 解法 各山に降った雨の総和 S は A_1 + A_2 + ... + A_N であり，山 i と i + 1 に降った雨の総和 x_i + x_(i + 1) は A_i * 2 である．よって，山 1 に降った雨の量 x_1 は S - (A_…

問題 解法 解答 問題 https://atcoder.jp/contests/abc133/tasks/abc133_c 解法 区間 [L, R] に 2019 の倍数が含まれているならば，答えは 0． そうでない場合，この区間の長さは 2019 未満であるから，i と j を全探索して答えを求めればよい． 解答 https:…

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1a/tasks/joi2020_yo1a_c 解法 動的配列（C++ では std::vector など）を用いる。数列 A, B が空であるかどうかは A.empty() が true であるかどうかで調べることができる。また、配列の末尾に要…

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1a/tasks/joi2020_yo1a_b 解法 文字列 S を先頭から 1 文字ずつ見ていき、'a', 'i', 'u', 'e', 'o' のどれか 1 つに当てはまるとき、答えに 1 加算すればよい。実装は for 文と if 文を用いれば…

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1a/tasks/joi2020_yo1a_a 解法 3 つの整数を受け取り、1, 2 の個数を if 文などを用いて数えればよい。計算量は O(1)。 解答 https://atcoder.jp/contests/joi2020-yo1a/submissions/7626706

問題 解法 解答 問題 https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_d 解法 各 X_i は何回か (0 回かもしれない) 2 個ずつ取ることができる．X_i を最大何回まで 2 ずつ引いていくことができるかをまず調べる．この回数 + 1 だけ各山に石があると問…

問題 解法 解答 問題 https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_c 解法 -1 でない a_i の xor を t，-1 である a_i の個数を cnt とすると，0 以上 X 以下の数 cnt 個の xor が X^t となればよい．これは X^t が X * 2 以上であるときは構成でき…

競技開始前 競技開始直前 問題１～３ 問題４ 問題５ 問題６ 問題７ 問題８ また問題６ 競技終了後 本選に 競技開始前 文化祭初日でした．極めて忙しかったので，全く競プロをやっていませんでした．直前にセグ木を数本書いて競プロとは何か思い出そうとして…

問題 解法 小課題１ 小課題３ 小課題５ 小課題６ 小課題７～９ 問題 https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2156 解法 小課題１ |H_1 - H_2| >= 2 を判定すればよい． 小課題３ N <= 2000, A_i <= 30 より全…

問題 解法 小課題１ 小課題２ 小課題３ 小課題４ 問題 https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2155 S 人の人と 2 種類のケーキがある．イチゴケーキは N 個に分かれていて，ショートケーキ M 個に分かれてい…

問題 解法 小課題１ 小課題２ 小課題３ 小課題４ 問題 https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2154 解法 小課題１ H, W == 2．なので，全てのマスが同じ文字であるか調べればよい． 小課題２ H, W <= 30 なの…

問題 解法 解答 問題 https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2153 解法 ビ太郎の左方向の動きを考える．これは，1 行を支配していると考えてよいので，1 行に複数個のビ太郎を置くことはできない． また，上…

問題 解法 解答 問題 https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2152 解法 正しいマルバツスタンプは 2 通りしかないので，この 2 つのうち操作が少ない方を採用すればよい． 解答 https://www.hackerrank.com/c…

問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g 解法 N が大きいので，P, Q, R, S, A_i, B_i, C_i, D_i を x, y 座標に分けて座標圧縮をする．また，上下・左右方向にワープ可能な領域をそれぞれ累積和で求めておく．この…

問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f 解法 以下の DP を考える． dp(i, j) := i 日目で右側に j 枚コインがあるとき，i + 1 日目以降のコストの和の最小値 遷移は，右側にのせるコインは j 枚のまま次の日にいく…

問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e 解法 参加者 i は (D_1 - 1) + (D_2 - 1) + ... + (D_i - 1) 秒後に動き始める．これを t_i とおく．なので，参加者 i が座標 1 に到達するのは t_i + (1 + i) 秒後になる．…

問題 解法 解答 問題 https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d 解法 以下の DP を考える． dp(i, j, k) := 上から i 桁目まで決めて，今まで j 回発言し，上から i 桁目までの整数を 3 で割った余りが k であるときの，i + 1 桁目以降の…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l 解法 以下の DP を考える． dp(i, j) := 頂点 i にいて，今 j 回まで操作が終わった時の，これから得られるスコアの総和の最大値 遷移は今いる頂点 i に留まるか，頂点 i につな…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k 解法 最終日には必ず写させてもらう必要がある．なぜならば，最終日分の宿題は N - 1 日までで写すことができないから．最終日で写せるページ数 (a_N) 日分は写すことができるの…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_j 解法 N, M <= 20 と小さいので，両校とも考えられる全てのチームの編成を列挙することができる．ここで，各校全ての生徒がどちらかのチームに入るので，A チームのレートの総和…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i 解法 A と B を昇順にソートしておき，各 A_i よりも真に大きい B_i の個数を調べる．これは std::upper_bound() を用いて各 A_i につき O(logM) で計算することができる．この…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_h 解法 各駅での乗り換え時間は，その駅につく路線の所要時間に加算してしまってよい．こうすることで，辺だけにコストを乗せることができたのでダイクストラ法を適用できる．ダイ…