人権なし

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

競技プログラミング

AtCoder Beginner Contest 151:F - Enclose All

問題 解法 解答 問題 https://atcoder.jp/contests/abc151/tasks/abc151_f 解法 求める半径を二分探索で求める. 半径を r に決めたとき,任意の 2 点を円の中心,半径を r とした円の交点は 2 つに定まる.そして,この 2 点それぞれを円の中心,半径を r …

AtCoder Beginner Contest 148:D - Brick Break

問題 解法 解答 問題 https://atcoder.jp/contests/abc148/tasks/abc148_d 解法 壊すレンガの数を少なくするには残すレンガの数を増やせばよいので,できる限り 1, 2, 3, ... の列を長くすればよい.これは,次に残したい数字 k(最初は 1)を保持しながら左…

AtCoder Beginner Contest 148:E - Double Factorial

問題 解法 解答 問題 https://atcoder.jp/contests/abc148/tasks/abc148_e 解法 N が奇数のとき,答えは 0.なぜならば,f(N) は素因数に 2 と 5 を持たないから. N が偶数のとき,f(N) が 5 で割れる回数が答えとなる(正確には 2 で割れる回数との min に…

AtCoder Beginner Contest 148:F - Playing Tag on Tree

問題 解法 解答 問題 https://atcoder.jp/contests/abc148/tasks/abc148_f 解法 高橋君は木のどこかの葉に逃げるのが適切なので,それぞれの葉に逃げたときの青木君の移動回数を求め,それらの max を答えとすればよい. まず,ある葉(頂点 t)までの距離 d…

AtCoder Beginner Contest 144:F - Fork in the Road

問題 解法 解答 問題 https://atcoder.jp/contests/abc144/tasks/abc144_f 解法 M 本の辺それぞれをふさいだときの E を計算していては O(M^2) となり間に合わない.ここで,ある頂点 v から出る辺のうち 1 つを塞ぐとするとき,v とつながる先の頂点から頂…

AtCoder Beginner Contest 144:E - Gluttony

問題 解法 解答 問題 https://atcoder.jp/contests/abc144/tasks/abc144_e 解法 「チーム全体の成績を k 以下にすることが出来るか」を基準とする二分探索で答えを求める.これは A を昇順,F を降順にソートしておき,この順番で担当する食べ物を割り当て,…

AtCoder Beginner Contest 144:D - Water Bottle

問題 解法 解答 問題 https://atcoder.jp/contests/abc144/tasks/abc144_d 解法 底面の辺を軸として傾けているから,平面で考えてよい.ある角度より傾けると水がこぼれるという単調性があるから,「角度 θ 傾けたとき,水がこぼれるかどうか」を基準とした…

AtCoder Beginner Contest 145:F - Laminate

問題 解法 解答 問題 https://atcoder.jp/contests/abc145/tasks/abc145_f 解法 まず,数列 H を扱いやすいように座標圧縮しておく(最小を 1 としなければいけないことに注意).そうすることで H の要素は高々 N + 1 以下になる.また,H[k] < H[k + 1] と…

AtCoder Beginner Contest 145:E - All-you-can-eat

問題 解法 解答 問題 https://atcoder.jp/contests/abc145/tasks/abc145_e 解法 まず,食べることにした料理の中では食べるのに必要な時間が短い順に注文するのが最適なので,料理を食べるのに必要な時間が短い順にソートしておく.ここで以下の DP を考える…

AtCoder Beginner Contest 145:D - Knight

問題 解法 解答 問題 https://atcoder.jp/contests/abc145/tasks/abc145_d 解法 各移動で原点から x, y 座標合わせて 3 は増加するから,(X + Y) が 3 で割り切れないとき,答えは 0 通り. そうでないとき,操作の回数 n は (X + Y) / 3 回であると分かる.…

AtCoder Beginner Contest 146:F - Sugoroku

問題 解法 解答 問題 https://atcoder.jp/contests/abc146/tasks/abc146_f 解法 辞書順最小にしたいので,マス N からマス 0 に向かって「ゲームオーバーマス」を避けながら,すごろくの目を最大化しながら進んでいけばよい.途中「ゲームオーバーマス」が M…

AtCoder Beginner Contest 146:E - Rem of Sum is Num

問題 解法 解答 問題 https://atcoder.jp/contests/abc146/tasks/abc146_e 解法 K = 1 のとき,答えは 0. そうでないとき,各 A_i から 1 を引き,累積和を求めておくと,「A の空でなく,長さが K 未満である連続する部分列で,要素の和を K で割った余り…

AtCoder Beginner Contest 146:D - Coloring Edges on Tree

問題 解法 解答 問題 https://atcoder.jp/contests/abc146/tasks/abc146_d 解法 まず,最も多くの辺が繋がっている頂点がもつ辺の数が必要となる色の数になる.また,ある 1 つの頂点を木の根とし,そこから辺を塗っていく DFS をする.具体的には,(今いる…

AtCoder Beginner Contest 147:E - Balanced Path

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_e 解法 dp(i, j, k) := マス (0, 0) から マス (i, j) までのパスで「偏り」が(以上でも以下でもなく)k となるかどうか という DP を考えると,遷移は (0, 0, |A[0][0] - B[0][0]|) …

AtCoder Beginner Contest 147:D - Xor Sum 4

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_d 解法 bit ごとに操作は独立なので,A の中で 2^k 桁目が 1 であるものの数をそれぞれ数えておき,この数を用いて答えを計算する.各 2^k 桁目について(1 の個数)*(0 の個数)* 2^…

AtCoder Beginner Contest 147:C - HonestOrUnkind2

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_c 解法 N 人それぞれが「正直者」かそうでないかを 2^N 通りすべて試し,与えられた情報に合致する組み合わせの中で最も「正直者」の数が多いものを答えにすればよい.O(2^N * N). 解…

JOI '20 一次予選2回目:C - 最頻値 (Mode)

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1b/tasks/joi2020_yo1b_c 解法 問題文を言い換えると「数列 A の中で最も多く含まれる数字の含まれる回数」を求めればよいと分かる.これは 1 ~ M それぞれについて A の中で登場する回数を数え…

JOI '20 一次予選2回目:B - 文字列の反転 (Inversion of a String)

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1b/tasks/joi2020_yo1b_b 解法 1 ~ A - 1 文字目と A ~ B 文字目と B + 1 ~ N 文字目をそれぞれ別の文字列に分ける.このうち A ~ B 文字目のものを反転させればよい.これは std::string の sub…

JOI '20 一次予選2回目:A - 試験 (Exam)

問題 解法 解答 問題 https://atcoder.jp/contests/joi2020-yo1b/tasks/joi2020_yo1b_a 解法 3 つの値のうち大きいもの 2 つの和は 3 つの和から最も小さいもの 1 つを引いたものと等しいから,答えは A + B + C - min({A, B, C}) となる.O(1). 解答 https…

yukicoder:No.915 Plus Or Multiple Operation

問題 解法 解答 問題 https://yukicoder.me/problems/no/915 解法 まず C が 1 であるときはクッキーを増やすことが出来ないので,答えは -1 となる.そうでないときは必ず A 枚まで増やすことが出来る. 操作を逆に考え,A 枚あるクッキーを 0 枚まで減らす…

yukicoder:No.914 Omiyage

問題 解法 解答 問題 https://yukicoder.me/problems/no/914 解法 国 [1, N / 2) での買い物の仕方と,国 [N / 2, N] での買い物の仕方をそれぞれ全列挙し,前者のそれぞれの金額について,後者との和が最も K に近くなるような後者の買い物の仕方を二分探索…

AtCoder Beginner Contest 136:E - Max GCD

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

AtCoder Beginner Contest 136:D - Gathering Children

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

AtCoder Beginner Contest 136:C - Build Stairs

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

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 個目までの飴を使い,…