人権なし

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

AtCoder 300 点問題

AtCoder Grand Contest 035:A - XOR Circle

問題 解法 解答 問題 https://atcoder.jp/contests/agc035/tasks/agc035_a 解法 (a ^ b) == c は (a ^ b ^ c) == 0 と同値より,高々 3 種類の数字しか登場してはならない.3 種類の場合は (a ^ b ^ c) == 0 となる a, b, c がそれぞれ N / 3 個,2 種類の場…

AtCoder Beginner Contest 132:C - Divide the Problems

問題 解法 解答 問題 https://atcoder.jp/contests/abc132/tasks/abc132_c 解法 (N / 2 + 1 番目に難しい問題の難易度, N / 2 番目に難しい問題の難易度] のどれかを K と設定するのがよい.ソートすればこれは求まる.O(NlogN). 解答 https://atcoder.jp/c…

AtCoder Beginner Contest 130:C - Rectangle Cutting

問題 解法 解答 問題 atcoder.jp 解法 与えられた長方形の重心を通るような面積を半分にする直線は,長方形の対角線である 2 本が考えられる.それ以外の点で半分にする直線は 1 本に定まる.O(1). 解答 atcoder.jp

AtCoder Beginner Contest 131:C - Anti-Division

問題 解法 解答 問題 atcoder.jp 解法 A - 1, B 以下の整数で C でも D でも割り切れない整数の数をそれぞれ求め,後者から前者を引けば答えになる.C でも D でも割れる数の扱いに注意する.O(1). 解答 atcoder.jp

diverta 2019 Programming Contest 2:B - Picking Up

問題 解法 解答 問題 atcoder.jp 解法 まず,N^2 個(正確にはもっと少ない)ある (p, q) の組を全列挙する.その後,各 (p, q) の組について必要となるコストの回数を計算する.ある頂点 v から移動量が (p, q) または (-p, -q) であるような頂点 u があれ…

AtCoder Beginner Contest 129:C - Typical Stairs

問題 解法 解答 問題 atcoder.jp 解法 dp(i) := i 段目まで登る通り数 として DP を考える.通り数は i が「壊れている床」のとき 0 通り,そうでないときは dp(i - 1) + dp(i - 2) 通りとなる.O(N). 解答 atcoder.jp

AtCoder Beginner Contest 126:C - Dice and Coin

問題 解法 解答 問題 atcoder.jp 解法 各さいころの目ごとに得点を K 以上にするために必要な確率を求め,1 / N と掛け合わせたものを合計したものが答えになる.コインが表が出続けなければならない回数は,得点が 2 倍されていく過程をシミュレーションす…

AtCoder Beginner Contest 127:C - Prison

問題 解法 解答 問題 atcoder.jp 解法 全ての [L_i, R_i] に含まれるカードの枚数を求めればよい.これは,L_i のうち最も大きいものと R_i のうち最も小さいものの差になる.この2つの位置が逆転するとき,答えは 0 となるので注意.O(N). 解答 atcoder.j…

AtCoder Beginner Contest 128:C - Switches

問題 解法 解答 問題 atcoder.jp 解法 スイッチの数 N が N <= 10 と小さいので,スイッチが on か off かを 1, 0 と置き換え bit 全探索をする.全スイッチの状態それぞれについて電球がつくかどうか問題文にある通りに調べればよい.O(2^N * M). 解答 atc…

Chokudai SpeedRun 002:G - GCD α

問題 解法 解答 問題 atcoder.jp 解法 ユークリッドの互除法で各 A_i, B_i の最大公約数は求まる.O(N * log(max(A, B))). 解答 atcoder.jp

Chokudai SpeedRun 002:F - 種類数 α

問題 解法 解答 問題 atcoder.jp 解法 (min(A_i, B_i), max(A_i, B_i)) をペアとし,std::set に追加していく.最終的な set のサイズが答えになる.O(NlogN). 解答 atcoder.jp

AtCoder Grand Contest 033:A - Darker and Darker

問題 解法 解答 問題 atcoder.jp 解法 問題文中の「辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる」は「黒色のマスと辺を共有して隣接する白色のマスが黒色になる」と言い変えられるので,全ての黒色の…

CPSCO2019 Session3:C - Camp Reception

問題 解法 解答 問題 atcoder.jp 解法 受付しなければいけない人がいる時間帯の区間の数が知りたいので,imos 法を用いて「ある時間 t に受付しなければいけない人がいるか?」を O(1) で知れるように前計算しておく.あとは,受付しなければいけない人が連…

いろはちゃんコンテスト Day2:C - 陽気な妖姫

問題 解法 解答 問題 atcoder.jp 解法 座標圧縮のアルゴリズムを用いればよい.O(NlogN). 解答 atcoder.jp

いろはちゃんコンテスト Day2:B - 河川敷の変態仮面

問題 解法 解答 問題 atcoder.jp 解法 川と変態仮面の動く線分が交差しているかを判定すればよい.O(1). 解答 atcoder.jp

いろはちゃんコンテスト Day2:A - わたのはら

問題 解法 解答 問題 atcoder.jp 解法 最長共通部分列 (LCS) の長さ + 1 が答えになる.LCS は簡単な DP によって求めることが出来る.O(|S||T|). 解答 atcoder.jp

いろはちゃんコンテスト Day1:F - Head of The Dragon

問題 解法 解答 問題 atcoder.jp 解法 N を素因数分解したときの項数よりも K が大きいとき,条件を満たす解はない. そうでないとき,答えの 1 ~ K - 1 項まで順番に N の素因数を小さい順に当てはめていけばよい.最後に残った素因数を全て掛け合わせたも…

いろはちゃんコンテスト Day1:E - 放課後

問題 解法 解答 問題 atcoder.jp 解法 デートする日を最小化することを考える.以下,最小のデート回数を考える. B = 0,すなわち,記念日が無いとき,最小のデート回数は N / A. そうでないとき,0 日目と最初の記念日の間,B - 1 箇所ある隣り合う記念日…

AtCoder Beginner Contest 125:C - GCD on Blackboard

問題 解法 解答 問題 atcoder.jp 解法 数列 A のうち 1 つを選び,任意の整数に書き換えられるということは,その選んだ数は A 全体の GCD に影響を与えないということと同値である.なので,ある個所を選んだ時の GCD は,その箇所より左の部分列の GCD と…

Tenka1 Programmer Contest 2019:C - Stones

問題 解法 解答 問題 atcoder.jp 解法 黒の右には白はないので,操作後の石の列は「白白白白白...」か「黒黒黒黒黒...」か「白白白...黒黒黒...」となる.よって,左から何個かを白にして,そのほかを黒にすればよい.この「何個」を 0 ~ N まで試せばよい.…

square869120Contest #6:B - AtCoder Market

問題 解法 解答 問題 atcoder.jp 解法 入口と出口を全てのマスについて試していては TLE となってしまうので,候補を減らすことを考える.すると,それぞれ A_i, B_i の座標全てについて調べれば十分であるので,候補を減らすことが出来た.O(N^3). 解答 at…

AtCoder Beginner Contest 124:C - Coloring Colorfully

問題 解法 解答 問題 atcoder.jp 解法 タイルを塗り替えた後の S は 01010... か 10101... の 2 通り.つまり,この 2 つと初期状態の S を比べ,違う色の枚数の少ない方を塗り替えたあとの S として採用すればよい.O(|S|). 解答 atcoder.jp

AtCoder Beginner Contest 123:C - Five Transportations

問題 解法 解答 問題 atcoder.jp 解法 A, B, C, D, E のうち最も少ない人数に合わせて人を運ぶという方針でよい.なぜなら,それより多い人数を運んでも,容量の小さい箇所で人が溜まってしまい,結局は同じになってしまうから.よって,容量の小さい箇所を …

全国統一プログラミング王決定戦本戦:C - Come Together

問題 解法 解答 問題 atcoder.jp 解法 各駒の縦方向・横方向の移動は独立に考えられる. ある x 座標への全ての駒の縦方向の移動量の総和を求めることを考える.ここで,決めた x 座標より小さい座標にある駒の数 cnt_up と座標の値の総和 cost_up を知れれ…

AtCoder Beginner Contest 122:C - GeT AC

問題 解法 解答 問題 atcoder.jp 解法 N, Q <= 10^5 より,各クエリごとに文字列を走査していては間に合わない.そこで,各クエリに O(1) で答えられるようにする. imos_i := i 文字目までに登場する "AC" の数 とおくと,各クエリで求める値は imos_r - im…

AtCoder Beginner Contest 121:C - Energy Drink Collector

問題 解法 解答 問題 atcoder.jp 解法 どの店も1本ごとに値段が決まっているので,1本ごとの値段が安い店から順番に出来るだけ買うのが最適.M 本買えるまで安い順に店を当たっていく.ソートがボトルネックとなり O(NlogN). 解答 atcoder.jp くだらない…

AtCoder Beginner Contest 118:C - Monsters Battle Royale

問題 解法 解答 問題 atcoder.jp 解法 モンスター同士が攻撃しあう様子を見るとユークリッドの互除法の過程をしているだけなので,GCD(A_1, A_2, ..., A_N) を答えにすればよい.これは,ある2体のモンスターが攻撃しあって生き残ったほうの体力は2体のモ…

AtCoder Beginner Contest 117:C - Streamline

問題 解法 解答 問題 atcoder.jp 解法 まず,駒を +1 の方向に動かした後に -1 の方向に動かすのは自明に意味がない.なので,駒を +1 の方向にだけ動かすことを考える.駒が通る距離を最小化したいので,駒が通らない距離を最大化すればよい.一番左・右の…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦:A - レース (Race)

問題 解法 解答 問題 atcoder.jp 解法 雪マスは必ず2つ以上連続するので,1つの雪マスを氷マスに変化させても氷マスの連続する区間が1つの区間になることはない.また,氷マスの区間が最も長い区間の前後どちらかの雪マスを氷マスに変化させるのが最適で…

AtCoder Beginner Contest 116:C - Grand Garden

問題 解法 解答 問題 atcoder.jp 解法 「水やり」の回数を最小化したいので,1回の「水やり」で出来るだけ多くの花の高さを伸ばしたい.なので,あと 1 以上伸ばさなければいけない花の連続する区間は1回の「水やり」で 1 ずつ伸ばす.h_i に達した花がそ…