人権なし

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

AtCoder 400 点問題

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_…

技術室奥プログラミングコンテスト#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 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 のときに「今いる…

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 ~ …

AtCoder Beginner Contest 134:D - Preparing Boxes

問題 解法 解答 問題 https://atcoder.jp/contests/abc134/tasks/abc134_d 解法 i = N, (N - 1), (N - 2), ... の倍数の順番に考えていく.そうすると i 番目の箱にボールを入れるかどうか決める際 i * 2, i * 3, ... 番目の箱にボールを入れるかどうかは既…

AtCoder Beginner Contest 132:D - Blue and Red Balls

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_d 解法 i 回操作が必要なとき,青玉が連続している区間が i 個あるということなので,(N - K) 個ある赤玉の間と左端と右端の (N - K + 1) 個の隙間に青玉の区間を i 個当てはめればよ…

AtCoder Beginner Contest 130:D - Enough Array

問題 解法 解答 問題 atcoder.jp 解法 ある区間 [l, r] の和が K 以上であるとき,区間 [l, r + 1], [l, r + 2], ... , [l, N] のそれぞれの和も当然 K 以上なので,各 l について最初に区間の和が K 以上となる r が分かればよい.この l, r は尺取り法によ…

AtCoder Beginner Contest 131:D - Megalomania

問題 解法 解答 問題 atcoder.jp 解法 期限 B が小さいものから順に仕事をこなしていくのが最適になる.B を昇順にソートした後の A において,A_1 + A_2 + ... + A_i <= B_i ならば i 番目の仕事はクリアとなるので,この不等式の左辺をできるだけ小さくす…

AtCoder Beginner Contest 129:D - Lamp

問題 解法 解答 問題 atcoder.jp 解法 各行・列について障害物がある x, y 座標をソートして配列に持っておく.これを前処理として行っておく. 各マスについて,そのマスから見て上下左右の最も近い障害物の座標は,前処理で求めておいた配列上で二分探索を…

AtCoder Beginner Contest 126:D - Even Relation

問題 解法 解答 問題 atcoder.jp 解法 ある任意の頂点を 1 つ選び,その選んだ頂点からほかの全頂点との間の距離の偶奇で色を分ければよい.なぜならば,ある頂点 v, u と最初に選んだ頂点 r との距離がそれぞれ偶奇が等しければ, v -> r -> u の距離は当然…

AtCoder Grand Contest 034:A - Kenken Race

問題 解法 解答 問題 atcoder.jp 解法 まず,それぞれ 2 人がもう一方がいなかった場合にゴールまでたどり着けるかを調べる.これは,[A, C], [B, D] 中に岩が 2 つ以上連続している箇所があったら乗り越えられないので,到達不可能となる.この時点でどちら…

AtCoder Beginner Contest 127:D - Integer Cards

問題 解法 解答 問題 atcoder.jp 解法 M 回の操作は順序を入れ替えても問題ないので,C_i が大きい順に行っていくのがよい.また,A_i を小さい順に操作するかどうかを決めていく.今見ている操作が i 番目で今見ている要素が j 番目のとき,C_i が A_j より…

AtCoder Beginner Contest 128:D - equeue

問題 解法 解答 問題 atcoder.jp 解法 問題文中の4つの操作は以下のように言い換えられる: 操作①:左端の宝石を捨てるが,最後に元に戻す 操作②:左端の宝石を捨てる,一生もとに戻さない 操作③:右端の宝石を捨てるが,最後に元に戻す 操作④:右端の宝石…

Chokudai SpeedRun 002:I - カツサンドくん β

問題 解法 解答 問題 atcoder.jp 解法 食べ物を 1 ~ N の順番に見ていく.また,最初の暫定的な「最強の食べ物」を食べ物 1 としておく.今,食べ物 i を見ているとき,どちらが勝つかどうかは簡単な四則演算で求まる.もし,食べ物 i が勝つときは暫定的な…

Chokudai SpeedRun 002:H - あまり β

問題 解法 解答 問題 atcoder.jp 解法 まず,A = B ならば,答えは -1 になる. そうでないとき,答えは abs(A - B) となる.これは,ある 0 以上の整数 p, q, r を使って,A = pX + r, B = qX + r とあらわすことが出来て,これらから A - B = (p - q)X と…

diverta 2019 Programming Contest:C - AB Substrings

問題 解法 解答 問題 atcoder.jp 解法 まず,各 s_i 中に含まれる "AB" の数を答えに加算する.これは,どういう順番で文字列を結合させても "AB" はそのままになるから. 問題は各 s_i の最初の 1 文字と最後の 1 文字をどう組み合わせていくかになる.よっ…

CPSCO2019 Session3:D - Decode RGB Sequence

問題 解法 解答 問題 atcoder.jp 解法 "RB" や "GG" と並ぶことはない.また,R は N - 1, N 文字目,G は 1, N 文字目,B は 1, 2 文字目に来ることはない.これらの条件のうち 1 つでも当てはまれば答えは No, すべてクリアしていれば Yes となる.O(N). …

いろはちゃんコンテスト Day1:H - ちらし寿司

問題 解法 解答 問題 atcoder.jp 解法 x99999... とするのが最適.しかし,N が x99999... という形であった場合,問題文にある X != N という条件を満たせない.そこで,例えば X = N = 199999 となってしまったとき,X = 289999 とすることで回避できる.…

いろはちゃんコンテスト Day1:G - 友達以上恋人以下

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k) := i - 1 日目までで,j 回好意をほのめかし,前回のほのめかしから k 日経過しているときの,i 日目以降に得られる機嫌の合計の最大値 と DP をおく.このとき遷移は,i 日目に好意をほのめかすかどうかの…

AtCoder Beginner Contest 125:D - Flipping Signs

問題 解法 解答 問題 atcoder.jp 解法 数列 A のある隣り合う 2 つの要素の一方が負の数でもう一方が正の数であるとき,両方に -1 をかけるという操作はマイナスの符号を負の数のものから正の数のものへ移動させることと同値である. これを踏まえると,A に…

square869120Contest #6:C - Infinite Grid

問題 解法 解答 問題 atcoder.jp 解法 スタートからゴールまでの移動は,まずスタートから全てのマスが移動できるマスであるような行まで移動し,ずっと右へ進み続け,その後ゴールのマスまで下がっていくようになる.到達可能である条件は「全てのマスが移…

AtCoder Beginner Contest 124:D - Handstand

問題 解法 解答 問題 atcoder.jp 解法 まず,最も長くなるような 1 の連続する部分列をただ 1 つ作るのが最適になる.なぜならば,わざわざ間に 0 をいくつか挟み複数の 1 が連続する部分を作るのであれば,複数の 1 の部分のうち最も長いものの両端の 0 の…

AtCoder Beginner Contest 123:D - Cake 123

問題 解法 解答 問題 atcoder.jp 解法 XYZ 通り列挙していては当然間に合わないので,まず XY 通り全て列挙する.この XY 通りのうち,K + 1 番目以降は最終的な答えの K 個の中に入らない(これは実験すると明らか).なので XY 通りをソートし,大きいもの…

全国統一プログラミング王決定戦 エキシビジョン:G - 回文スコア

問題 解法 解答 問題 atcoder.jp 解法 最大の長さの回文1つとあまりの文字で長さ 1 の回文をたくさん作るのが最適.O(|S|). 解答 atcoder.jp

「みんなのプロコン 2019」:C - When I hit my pocket...

問題 解法 解答 問題 atcoder.jp 解法 まず,A 枚のクッキーを B 枚のクッキーにするとき,2 枚以上増えなければ得をしない.なぜならば,2 回かかる操作をただクッキーを 1 枚あたらしく得ることに費やした方がよいから.そうでないとき,まずクッキーを A …

AtCoder Beginner Contest 122:D - We Like AGC

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k, l) := 今 i - 1 文字目まで考えて,i - 3 文字目が j,i - 2 文字目が k, i - 1 文字目が l のときの,i 文字目から先の通り数 と DP を定義する.次の1文字(すなわち i 文字目)を決めるとき 'A', 'T', …

AtCoder Grand Contest 032:A - Limited Insertion

問題 解法 解答 問題 atcoder.jp 解法 前から操作を見るのは実は困難なので,後ろから見ていく.このとき,問題は「場所 i で数字 i を消すことができる.この消し方とは?」と言い換えられる.また,消す場所は消せる場所の中で一番右がよい.なぜならば,…