問題 解法 小課題１ 小課題３ 小課題５ 小課題６ 小課題７～９ 問題 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 解法 各駅での乗り換え時間は，その駅につく路線の所要時間に加算してしまってよい．こうすることで，辺だけにコストを乗せることができたのでダイクストラ法を適用できる．ダイ…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_g 解法 N_i <= 1 のとき，答えは N_i になる． そうでないとき，2 と 3 で分解するのが最適になる．具体的には，N_i % 3 == 1 のとき 3^(N_i / 3 - 1) * 4 とし，そうでないとき 3…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_f 解法 現在の時刻を t，今いる島を i とするとき，橋 (i, j) を使ったときに島 i + 1 にいる時刻は ceil(t / A_(i, j)) * A_(i, j) + B_(i, j) となる．各島においてどの橋を使っ…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_e 解法 まず A の和が E 以下であればエナジードリンクは飲まなくてもよい． そうでないとき，エナジードリンクを B_i が大きい順に飲んでいけばよい．B を降順にソートしておき，…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_d 解法 まず，要素が重複している連続する区間は 1 つの要素にまとめてしまってよい．なぜならば，このような区間でどこをスキップしてもスコアは増えないから．こうすることによ…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_g 解法 「平均値の最大化」における一般的なテクとして二分探索がある．具体的には，求める最大の平均値を二分探索し，平均値 m が実現可能かどうかの判定は (各要素の値 - m) を…

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_f 解法 前から要素を見ていく．a_i > 0 となっている要素があれば a_i, a_(i + 1), ... から 1, 4, ... を a_i 倍したものを引いていき，最終的に全ての要素が 0 になっているかど…