人権なし

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

AtCoder 400 点問題

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 を消すことができる.この消し方とは?」と言い換えられる.また,消す場所は消せる場所の中で一番右がよい.なぜならば,…

AtCoder Beginner Contest 120:D - Decayed Bridges

問題 解法 解答 問題 atcoder.jp 解法 グラフから辺を取り除いていくのではなく,辺を追加していくと考える.辺を後ろから追加していった時の「不便さ」を逆にしたものが求める答えになる. 辺を1つ追加したときに改善される「不便さ」は辺の両端の頂点それ…

AtCoder Beginner Contest 119:D - Lazy Faith

問題 解法 解答 問題 atcoder.jp 解法 各クエリごとに x_i より左にある最寄りの神社・寺,x_i より右にある最寄りの神社・寺の場所を計算する.これは std::lower_bound() や std::upper_bound() を用いて O(logA), O(logB) で計算できる.あとは,神社と寺…

AtCoder Beginner Contest 121:D - XOR World

問題 解法 解答 問題 atcoder.jp 解法 A, B >= 10^12 と大きいので愚直な計算では TLE となってしまう. ここで,答えとなる数の k bit 目を明らかにすることを考える.0 から順番に数を 2 進数表記で書いて眺めてみると,1 bit 目は 0, 1, 0, 1, ... と 0, …

AtCoder Beginner Contest 118:D - Match Matching

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := マッチ棒を i 本ちょうど使って出来る最大の数 と DP を定義する.このとき,遷移時に A_i を全て試し,その中で最大の数を DP の答えにすればよい.答えとなる数は非常に大きくなるので,文字列として扱う.O…

AtCoder Beginner Contest 117:D - XXOR

問題 解法 解答 問題 atcoder.jp 解法 K の i bit 目を K_i,K より小さい数 X の i bit 目を X_i とすると, K_40 = X_40 K_39 = X_39 ... K_i > X_i (0 <= i <= 40) となる.ここで,X_(i - 1), X_(i - 2), ... , X_0 は 0 でも 1 でもよい(K との大小に…

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019:C - Different Strokes

問題 解法 解答 問題 atcoder.jp 解法 自分と相手にとって幸福度の高いものを食べたいと考えると,(a_i + b_i) が大きいものから食べていけば最適だと気付く.言い方を変えると,最初に求める答えが -(b_1 + b_2 + ... + b_N) だった場合,ここに最大の (a_i…

AtCoder Beginner Contest 116:D - Various Sushi

問題 解法 解答 問題 atcoder.jp 解法 まず,N 個の寿司を「おいしさ」が大きい順にソートし,大きいものから K 個選び答えの候補にする.このとき選んだ寿司のネタの種類数が k だとしたとき,1 ~ (k - 1) 種類のネタだけで K 個選ぶことは不可能 or 最適で…