この記事はCompetitive Programming (1) Advent Calendar 2019の7日目の記事です。 対象読者 解説で多項式とか母関数とか形式的べき級数とか書いてあるとそっ閉じするあなた 厳密な話は要求しないから、テクニックとして理解したいあなた .oO（多項式の計算…
この記事はCompetitive Programming (2) Advent Calendar 2019の7日目の記事です。 AtCoder Beginner Contest 146でこっそり一人解説RTAやってたので、動画とってた。 その各所での技術を以下は紹介する。 RTA動画はこれ ojt みんな大好きOnline Judge Tools…
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8777300 着色をしていくわけだが、先頭から順番に色をつけていこう。 最初の0は3色のどれかが入る。次の0は残りの2色。最後は1…
![はてなブックマーク - Colorful Hats 2 [Sumitomo Mitsui Trust Bank Programming Contest 2019 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/12/03/225149)
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776950 3桁を指定するのはO(N3)かかってしまう。 だが、答えの組み合わせに注目してみると、103通りある。 これなら全探索でき…
![はてなブックマーク - Lucky PIN [Sumitomo Mitsui Trust Bank Programming Contest 2019 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/12/03/225048)
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c 前提知識 yes/no系動的計画法 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776665 品物は106個あるので、足りなくなることはない。 DPしよう。yes/noのDPをする。 dp[x] :=…
![はてなブックマーク - 100 to 105 [Sumitomo Mitsui Trust Bank Programming Contest 2019 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/12/03/224946)
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_b 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776597 N/1.08をすれば答えが得られそうではあるが、小数点以下切り捨てになっているので、ちょっとやりにくい。 Nの上限が500…
![はてなブックマーク - Tax Rate [Sumitomo Mitsui Trust Bank Programming Contest 2019 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/12/03/224844)
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_a 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776530 月末日であるためには、次の日で月が変わる必要がある。 よって、D1,D2は関係なく、M1
![はてなブックマーク - November 30 [Sumitomo Mitsui Trust Bank Programming Contest 2019 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/12/03/224724)
https://yukicoder.me/problems/no/935 尺取法 解説 https://yukicoder.me/submissions/402911 んーと思って見てると制約が弱めなことに気がつく。 よって、O(NQ)はまずできそう。 つまり、ビームの始点は全探索可能。 始点からビームでどこまで伸ばせるかを…
![はてなブックマーク - う し た ぷ に き あ く ん 笑 ビ － ム [yukicoder 935]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/30/101735)
https://yukicoder.me/problems/no/934 解説 https://yukicoder.me/submissions/402813 リアクティブ問題。 色々考えると思いつくけど、どういう道筋で思いつくんだろうね。 ある魔剤以外を混ぜたときに、 爆発する→ある魔剤は爆発に必要ない 爆発しない→あ…
![はてなブックマーク - Explosive energy drink [yukicoder 934]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/30/101632)
https://yukicoder.me/problems/no/933 解説 https://yukicoder.me/submissions/403112 これ難しくないか？ ん？まじで何も分からん。 多倍長整数で殴れそうな気もするけど、ほんとか？ あれっ？あれっ？ こんなときはランキングを見るとヒントがあったりす…
![はてなブックマーク - おまわりさんこいつです [yukicoder 933]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/30/101531)
https://yukicoder.me/problems/no/932 解説 https://yukicoder.me/submissions/402564 便利なカンマで分割する関数を作ろう。 （この機に作ると主にyukicoderで役に立つ。自分が使ってるやつも借りてきたやつなんですけどね） string S; //----------------…
![はてなブックマーク - 解法破綻！高橋君 [yukicoder 932]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/30/101428)
https://codeforces.com/contest/1261/problem/D2 解説 「そのままの点数 < 入れ替え後の点数」が満たされればいい。 言い換えると、「0 < 入れ替え後の点数 - そのままの点数」を満たせばいい。 i番目の数をxと決めると、h[i]=xであればそのままの点数が+1…
![はてなブックマーク - Wrong Answer on test 233 (Hard Version) [Codeforces Round #602 (Div. 1, based on Technocup 2020 Elimination Round 3) D2]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/30/101306)
https://atcoder.jp/contests/abc146/tasks/abc146_f 解説 https://atcoder.jp/contests/abc146/submissions/8635768 DPして復元する。 後ろからまずは最短手数になるようにDPしよう。 i番目のマスが0で最短距離がdp[i]であれば、dp[i-1]～dp[i-M]がdp[i]+1…
![はてなブックマーク - Sugoroku [AtCoder Beginner Contest 146 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/24/231322)
https://atcoder.jp/contests/abc146/tasks/abc146_e 解説 https://atcoder.jp/contests/abc146/submissions/8635001 まずは常套手段として、右端を全探索して条件を満たす左端を探すことにしよう。 連続する和について考えるので、累積和を考えれば良さそう…
![はてなブックマーク - Rem of Sum is Num [AtCoder Beginner Contest 146 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/24/231220)
https://atcoder.jp/contests/abc146/tasks/abc146_d 解説 https://atcoder.jp/contests/abc146/submissions/8632543 貪欲に色を決めて塗っていけば達成できそう。 根を1つ決めて貪欲に色を塗っていく。 あとは、実装を頑張る。 各頂点で必要な色は次数と一…
![はてなブックマーク - Coloring Edges on Tree [AtCoder Beginner Contest 146 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/24/231120)
https://atcoder.jp/contests/abc146/tasks/abc146_c 前提知識 二分探索 解説 https://atcoder.jp/contests/abc146/submissions/8630477 x
![はてなブックマーク - Buy an Integer [AtCoder Beginner Contest 146 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/24/231012)
https://atcoder.jp/contests/abc146/tasks/abc146_b 解説 https://atcoder.jp/contests/abc146/submissions/8629425 前の問題同様に文字を数に変換して+Nをすることで変換をする。 +Nするときは、ループの構造を考えるために26で割ったあまりで考える。 あ…
![はてなブックマーク - ROT N [AtCoder Beginner Contest 146 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/24/230908)
https://atcoder.jp/contests/abc146/tasks/abc146_a 解説 https://atcoder.jp/contests/abc146/submissions/8629033 SUN,MON,TUE,WED,THU,FRI,SATを0,1,2,3,4,5,6と変換して考えてみよう。 すると、答えは7-S'となる。 文字列だと差を出しにくいので、数値…
![はてなブックマーク - Can't Wait for Holiday [AtCoder Beginner Contest 146 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/24/230805)
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587942 コードがかちゃかちゃだが、方針を伝える。 以下の様な考察で解にたどり着く。 ぱっと見て最適な動きが思いつかない…
![はてなブックマーク - Digit Sum Replace [DISCO Presents Discovery Channel Code Contest 2020 Qual D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/24/003030)
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_e 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8589071 N個ならんで質問をしよう。 1つずつずらしながら質問をしたときに答えの色が変わるポイントがある。 例えばiからN個…
![はてなブックマーク - Majority of Balls [DISCO Presents Discovery Channel Code Contest 2020 Qual E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/233131)
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587942 コードがかちゃかちゃだが、方針を伝える。 以下の様な考察で解にたどり着く。 ぱっと見て最適な動きが思いつかない…
![はてなブックマーク - Digit Sum Replace [DISCO Presents Discovery Channel Code Contest 2020 Qual D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/233029)
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_c 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587526 実装方針としては、まずは縦にスライスして、横にスライスする。 cnt[x] := x座標がxであるいちごの個数 これを数え…
![はてなブックマーク - Strawberry Cakes [DISCO Presents Discovery Channel Code Contest 2020 Qual C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/232908)
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_b 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587116 どの切れ目を選ぶかを全探索する。 ある位置で切ったとして、片方の長さがlft, もう片方の長さがrhtであるとき、 操…
![はてなブックマーク - Iron Bar Cutting [DISCO Presents Discovery Channel Code Contest 2020 Qual B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/232808)
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_a 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8586587 賞金額の合計を求めよう。 1位、2位、3位の賞金を入れておき、どっちも1位なら追加で40万与える。 int X, Y; //----…
![はてなブックマーク - DDCC Finals [DISCO Presents Discovery Channel Code Contest 2020 Qual A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/232707)
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-tahoiya-ga-tokuiya/problem 前提知識 動的計画法 解説 https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-pr…
![はてなブックマーク - Tahoiya ga Tokuiya [TSG LIVE! 4 プログラミングコンテスト E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/163108)
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-lcm-interval 前提知識 Disjoint Sparse Table 想定解はSliding Window Aggregationだが、本解法では使ってない 解法 https://www.hackerrank.com/contes…
![はてなブックマーク - LCM Interval [TSG LIVE! 4 プログラミングコンテスト F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/161806)
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-constructable 嘘解法かも https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-constructable/submissi…
![はてなブックマーク - Constructable [TSG LIVE! 4 プログラミングコンテスト C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/160246)
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-three-sushi-game 解説 www.hackerrank.com 寿さんは自由に手を決めることができるので、毎回最適な手を出せばいい。 サンプルには丁寧にも全てのパター…
![はてなブックマーク - Three Sushi Game [TSG LIVE! 4 プログラミングコンテスト B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/155923)
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-live-performer 解法 https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-live-performer/submissions/…
![はてなブックマーク - Live Performers [TSG LIVE! 4 プログラミングコンテスト A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/23/155829)
https://yukicoder.me/problems/no/929 解説 https://yukicoder.me/submissions/400103 なんとなく貪欲でやれば良さそうな気がする。 先頭からなければ前から持ってくるか、後ろから持ってくるかすればいい。 これはボールに最初にある場所の添字を付けて、…
![はてなブックマーク - よくあるボールを移動するやつ [yukicoder 929]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/11/22/234256)