人権なし

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

競技プログラミング

Tenka1 Programmer Contest 2019

結果 C - Stones D - Three Colors 結果 4問中1問正解(300 / 2500 点, 12:06),1101 位中 459 位,パフォーマンス 1709,新レート 1540 (+20).C 問題を早解き出来ていれば黄色パフォを取れていたので残念だった. C - Stones babcs2035.hateblo.jp D - …

Tenka1 Programmer Contest 2019:D - Three Colors

問題 解法 解答 問題 atcoder.jp 解法 a の和を sum とすると max({R, G, B}) < sum / 2 が成り立っていれば三角形を構成出来る.なので,R, G, B のどれかが 1 つでも sum / 2 以上の値であるとき,三角形は構成できない. ここで,塗り分ける場合の数全体…

Tenka1 Programmer Contest 2019:C - Stones

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

yukicoder:No.818 Dinner time

問題 解法 解答 問題 yukicoder.me 解法 まず,ニワトリ i が k 回食料として利用されるとき,ニワトリ i - 1 は必ず k 回以上利用されなければならない.そうでなければ,問題のルールに反してしまう. 次に,各ニワトリに分けて考える.各ニワトリについて…

yukicoder:No.817 Coin donation

問題 解法 解答 問題 yukicoder.me 解法 コインの枚数の境目は最大でも 2 * N 個しかできないので,コインの数字を座標圧縮することを考える.そうすると,空間計算量を O(N) に減らせる.各コインの枚数の区間において,その区間に属するもともとのコインの…

yukicoder:No.816 Beautiful tuples

問題 解法 解答 問題 yukicoder.me 解法 A + B は C の倍数であるので,C は A + B の約数となる.よって,A + B の約数を列挙し,これらを C の候補とし,条件を満たす候補があるかどうかを試せばよい.O(√(A + B)). 解答 yukicoder.me

square869120Contest #6:C - Infinite Grid

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

square869120Contest #6:B - AtCoder Market

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

AtCoder Beginner Contest 124:D - Handstand

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

AtCoder Beginner Contest 124:C - Coloring Colorfully

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

yukicoder:No.812 Change of Class

問題 解法 解答 問題 yukicoder.me 解法 まず,各クエリで与えられる頂点を始点としてダイクストラ法を用いて全頂点への最短距離を求める.ここで,到達できる頂点の数が最大の友達の数になる. 次に,各頂点と始点の頂点が何日で友達になるかを調べる.1 日…

yukicoder:No.811 約数の個数の最大化

問題 解法 解答 問題 yukicoder.me 解法 N の素因数をあらかじめ求めておき,1 ~ N - 1 の全ての数について素因数を求め,N の素因数と共通しているものが K 以上あるものは約数の個数を計算し,その約数の個数を最大化するように更新していく.最大の約数の…

AtCoder Regular Contest 079:E - Decrease (Judge ver.)

問題 解法 解答 問題 atcoder.jp 解法 (解法の証明をせず通してしまった) 数列 a の中の最大値である箇所が何回かの操作によって最小値になるまでにかかる最小の操作の回数を二分探索で求め,操作後の a をソートし,またこの二分探索を繰り返していき,最…

AtCoder Beginner Contest 123:D - Cake 123

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

AtCoder Beginner Contest 123:C - Five Transportations

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

Codeforces Global Round 2

結果 A - Ilya and a Colorful Walk B - Alyona and a Narrow Fridge C - Ramesses and Corner Inversion D - Frets On Fire 結果 8問中4問正解(4134 / 18000 点),4753 位中 1081 位,新レート 1587 (+100, Highest).誤答無しで4問通すことが出来たの…

Codeforces Global Round 2:D - Frets On Fire

問題 解法 解答 問題 codeforces.com 解法 まず S をソートしておき,重複しているものは取り除いてよい. ここで,各クエリで与えられる区間の「位置」は答えに影響を与えず,「長さ」が影響を与える.なぜならば,区間が [l, r] としたら,その区間にあっ…

Codeforces Global Round 2:C - Ramesses and Corner Inversion

問題 解法 解答 問題 codeforces.com 解法 問題にある操作は「任意の x1 < x2, y1 < y2 となるような 4 つの値を選び,マス (x1, y1), (x1, y2), (x2, y1), (x2, y2) の値を反転させる」と言い変えることが出来る.また,マス目 A, B で異なっている箇所をマ…

Codeforces Global Round 2:B - Alyona and a Narrow Fridge

問題 解法 解答 問題 codeforces.com 解法 何本までを冷蔵庫に入れるか (k) を固定して考えたとき,a_1, a_2, ... , a_k をソートしたものを b とおく.まず,高さ b_k のものを入れなければならないので,仕切りは必ず b_k の高さが入るような空間が出来る…

Codeforces Global Round 2:A - Ilya and a Colorful Walk

問題 解法 解答 問題 codeforces.com 解法 各色ごとに最も小さい座標と最も大きい座標を求め,それぞれソートしておく.その後,ある色を固定したとき,ほかの色の最大値を求めその差の max を取り答えにする.ほかの色の最大値を求めるのには事前に各色の最…

Google Code Jam Qualification Round 2019

結果 Foregone Solution You Can Go Your Own Way 結果 50 / 100点,31663 位中 6285 位.予選通過基準である 30 点を超えることが出来たので,Round 1 に進めることになった. Foregone Solution babcs2035.hateblo.jp You Can Go Your Own Way babcs2035.h…

Google Code Jam Qualification Round 2019:You Can Go Your Own Way

問題 解法 解答 問題 codingcompetitions.withgoogle.com N * N マスを左上から右下まで移動する手順が与えられる.この手順のパスを通らずに右か下への移動だけを用いて左上から右下まで移動する手順を1 つ出力する問題.なお,入力で与えられるパスと交わ…

Google Code Jam Qualification Round 2019:Foregone Solution

問題 解法 解答 問題 codingcompetitions.withgoogle.com N が与えられる.N は少なくとも 1 つの桁に 4 を含む自然数.これを自然数 A, B を用いて A + B = N とあらわしたい.ここで,A, B は 4 を含んではならない.どれか 1 つ考えうる A, B を出力する…

AtCoder Regular Contest 075:E - Meaningful Mean

問題 解法 解答 問題 atcoder.jp 解法 a_l, a_(l + 1), ... , a_r の平均が K 以上であるには (a_l - K) + (a_(l + 1) - K) + ... + (a_r - K) が 0 以上であればよいので,a_i から K を引いた値で考える.また,a の累積和 a_imos を考えると,a_l ~ a_r …

AtCoder Regular Contest 071:E - TrBBnsformBBtion

問題 解法 解答 問題 atcoder.jp 解法 各クエリで与えられる部分文字列を A だけの最も短い文字列にすることを考える.まず,部分文字列中の B を全て AA に変換し,残った A だけの文字列のうち AAA と 3 つ A が並んでいる箇所は空文字列に出来るので出来…

AtCoder Regular Contest 097:E - Sorted and Sorted

問題 解法 解答 問題 atcoder.jp 解法 次の DP を考える: dp(i, j) := 白いボールを 1 ~ i 番までソートし,黒いボールを 1 ~ j 番までソートしたときの,残っている 2 * N - (i + j) 個のボールをそれぞれの色でソートするのにかかる操作回数の最小値 この…

AtCoder Regular Contest 102:E - Stop. Otherwise...

問題 解法 解答 問題 atcoder.jp 解法 i の偶奇で場合分けする. i が奇数の場合,サイコロの目として出てはいけない組み合わせ(禁止された組み合わせ)は (1, i - 1), (2, i - 2), ... となる.この組み合わせの個数を p とおき,これら 2 * p 個の数のう…

AtCoder Regular Contest 103:E - Tr/ee

問題 解法 解答 問題 atcoder.jp 解法 まず,s[0] は必ず 1 で s[|s| - 1] は必ず 0 でなければならない.なぜなら,葉に繋がる辺を切れば必ず大きさ 1 の部分木が出来て,どこかの辺で切ったら木全体が2つに分けられるため大きさ |s| の部分木は出来ないか…

エクサウィザーズ 2019

結果 C - Snuke the Wizard D - Modulo Operations 結果 6 問中 2 問正解 (300 / 3300 点, 1:48),3164 位中 547 位,パフォーマンス 1724,新レート 1520 (+25).A, B 問題を早解き出来たので一応レートは上げることが出来たが,長い時間かけた D 問題を通…

エクサウィザーズ 2019:D - Modulo Operations

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 今黒板に書かれている数が i で,j 個 S から取り出したとき,これからの操作で考えうる最後に書かれる数の和 と DP をたてる.また,ある数字 x よりも大きい数字 y で mod をとっても x は変わらないので…