人権なし

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

競技プログラミング

AtCoder Beginner Contest 133:E - Virus Tree 2

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

AtCoder Beginner Contest 133:D - Rain Flows into Dams

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

AtCoder Beginner Contest 133:C - Remainder Minimization 2019

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

JOI '20 一次予選1回目:C - マージ (Merge)

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

JOI '20 一次予選1回目:B - 母音を数える (Counting Vowels)

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

JOI '20 一次予選1回目:A - 3 つの整数 (Three Integers)

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

東京工業大学プログラミングコンテスト2019:D - 素数取りゲーム

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

東京工業大学プログラミングコンテスト2019:C - XOR Filling

問題 解法 解答 問題 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 以上であるときは構成でき…

大手前プロコン 2019:G - 空をかけるピ太郎 (Pitaro, who Leaps through Air)

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

大手前プロコン 2019:F - 天秤とコイン (Balance and Coins)

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

大手前プロコン 2019:E - 最悪の教頭 (Worst Head Teacher)

問題 解法 解答 問題 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) 秒後になる.…

大手前プロコン 2019:D - FizzBuzz (FizzBuzz)

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

技術室奥プログラミングコンテスト#4 Day1:L - じゃんけん

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

技術室奥プログラミングコンテスト#4 Day1:K - 天使と宿題

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

技術室奥プログラミングコンテスト#4 Day1:J - school competition 2

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

技術室奥プログラミングコンテスト#4 Day1:I - school competition 1

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

技術室奥プログラミングコンテスト#4 Day1:H - don't be late

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

技術室奥プログラミングコンテスト#4 Day1:G - バラバラ掛け算

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

技術室奥プログラミングコンテスト#4 Day1:F - 不便な橋

問題 解法 解答 問題 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) となる.各島においてどの橋を使っ…

技術室奥プログラミングコンテスト#4 Day1:E - Osmium_1008と課題

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

技術室奥プログラミングコンテスト#4 Day1:D - スキップ

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

技術室奥プログラミングコンテスト#4 Day2:G - 平均レーティング

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

技術室奥プログラミングコンテスト#4 Day2:F - Segtree☆Magica

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

AtCoder Beginner Contest 135:E - Golf

問題 解法 解答 問題 https://atcoder.jp/contests/abc135/tasks/abc135_e 解法 考察をしやすくするため X >= Y >= 0 となるように X, Y を変換してしまう.変換した場合は,答えを出力する際に元の X, Y に当てはまるように再度復元する必要があるので注意…

技術室奥プログラミングコンテスト#4 Day2:E - 引きこもり

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_e 解法 まず,辺のコストを座標圧縮しておき扱いやすくしておく.また,辺を辺のコストが昇順になるようにソートしておく.その後 L を 0 から増やしていったときにどのように連結…

技術室奥プログラミングコンテスト#4 Day2:D - 新入生歓迎数列 2

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_d 解法 与えられた条件式を整理すると, 2 * A_x == P + Q 2 * (A_y + A_z) == P - Q となる (x, y, z) の組を見つければよいと分かる.前者は自明に判定できるので,後者を見つけ…

技術室奥プログラミングコンテスト#4 Day2:B - Stalker

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_b 解法 問題を整理すると,写真がある頂点は 1 つの枝分かれしない直線状のパス上にあるかどうかを判定する問題になる. 適当な頂点を根として DFS をする.DFS のときに「今いる…

技術室奥プログラミングコンテスト#4 Day2:A - Jumping!!

問題 解法 解答 問題 https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_a 解法 まず y 座標は 0 以上で偶数でなければならない.ここが一番引っかかるポイントだと思う. y 方向に + の方向にしか移動できないので,移動回数 t が求まる.この移動回数…

AtCoder Beginner Contest 135

結果 A - Harmony B - 0 or 1 Swap C - City Savers D - Digits Parade 結果 6 問中 3 問正解(600 / 2100 点, 6:57),4500 位中 983 位,パフォーマンス 1289,新レート 1462 (-18).A - C 問題を早く通すことができたのはよかったが,最後まで D 問題を通…

AtCoder Beginner Contest 135:D - Digits Parade

問題 解法 解答 問題 https://atcoder.jp/contests/abc135/tasks/abc135_d 解法 以下の DP を考える. dp(i, j) := 0 ~ i 桁目まで見て,13 で割った余りが j のとき,i + 1 桁目以降余りが 5 になるような ? の埋め方の通り数 i 桁目が ? であるときは 0 ~ …