この記事は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…
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776950 3桁を指定するのはO(N3)かかってしまう。 だが、答えの組み合わせに注目してみると、103通りある。 これなら全探索でき…
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c 前提知識 yes/no系動的計画法 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776665 品物は106個あるので、足りなくなることはない。 DPしよう。yes/noのDPをする。 dp[x] :=…
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_b 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776597 N/1.08をすれば答えが得られそうではあるが、小数点以下切り捨てになっているので、ちょっとやりにくい。 Nの上限が500…
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_a 解説 https://atcoder.jp/contests/sumitrust2019/submissions/8776530 月末日であるためには、次の日で月が変わる必要がある。 よって、D1,D2は関係なく、M1
https://yukicoder.me/problems/no/935 尺取法 解説 https://yukicoder.me/submissions/402911 んーと思って見てると制約が弱めなことに気がつく。 よって、O(NQ)はまずできそう。 つまり、ビームの始点は全探索可能。 始点からビームでどこまで伸ばせるかを…
https://yukicoder.me/problems/no/934 解説 https://yukicoder.me/submissions/402813 リアクティブ問題。 色々考えると思いつくけど、どういう道筋で思いつくんだろうね。 ある魔剤以外を混ぜたときに、 爆発する→ある魔剤は爆発に必要ない 爆発しない→あ…
https://yukicoder.me/problems/no/933 解説 https://yukicoder.me/submissions/403112 これ難しくないか? ん?まじで何も分からん。 多倍長整数で殴れそうな気もするけど、ほんとか? あれっ?あれっ? こんなときはランキングを見るとヒントがあったりす…
https://yukicoder.me/problems/no/932 解説 https://yukicoder.me/submissions/402564 便利なカンマで分割する関数を作ろう。 (この機に作ると主にyukicoderで役に立つ。自分が使ってるやつも借りてきたやつなんですけどね) string S; //----------------…
https://codeforces.com/contest/1261/problem/D2 解説 「そのままの点数 < 入れ替え後の点数」が満たされればいい。 言い換えると、「0 < 入れ替え後の点数 - そのままの点数」を満たせばいい。 i番目の数をxと決めると、h[i]=xであればそのままの点数が+1…
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…
https://atcoder.jp/contests/abc146/tasks/abc146_e 解説 https://atcoder.jp/contests/abc146/submissions/8635001 まずは常套手段として、右端を全探索して条件を満たす左端を探すことにしよう。 連続する和について考えるので、累積和を考えれば良さそう…
https://atcoder.jp/contests/abc146/tasks/abc146_d 解説 https://atcoder.jp/contests/abc146/submissions/8632543 貪欲に色を決めて塗っていけば達成できそう。 根を1つ決めて貪欲に色を塗っていく。 あとは、実装を頑張る。 各頂点で必要な色は次数と一…
https://atcoder.jp/contests/abc146/tasks/abc146_c 前提知識 二分探索 解説 https://atcoder.jp/contests/abc146/submissions/8630477 x
https://atcoder.jp/contests/abc146/tasks/abc146_b 解説 https://atcoder.jp/contests/abc146/submissions/8629425 前の問題同様に文字を数に変換して+Nをすることで変換をする。 +Nするときは、ループの構造を考えるために26で割ったあまりで考える。 あ…
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'となる。 文字列だと差を出しにくいので、数値…
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587942 コードがかちゃかちゃだが、方針を伝える。 以下の様な考察で解にたどり着く。 ぱっと見て最適な動きが思いつかない…
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_e 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8589071 N個ならんで質問をしよう。 1つずつずらしながら質問をしたときに答えの色が変わるポイントがある。 例えばiからN個…
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587942 コードがかちゃかちゃだが、方針を伝える。 以下の様な考察で解にたどり着く。 ぱっと見て最適な動きが思いつかない…
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_c 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587526 実装方針としては、まずは縦にスライスして、横にスライスする。 cnt[x] := x座標がxであるいちごの個数 これを数え…
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_b 解説 https://atcoder.jp/contests/ddcc2020-qual/submissions/8587116 どの切れ目を選ぶかを全探索する。 ある位置で切ったとして、片方の長さがlft, もう片方の長さがrhtであるとき、 操…
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; //----…
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…
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…
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…
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-three-sushi-game 解説 www.hackerrank.com 寿さんは自由に手を決めることができるので、毎回最適な手を出せばいい。 サンプルには丁寧にも全てのパター…
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/…
https://yukicoder.me/problems/no/929 解説 https://yukicoder.me/submissions/400103 なんとなく貪欲でやれば良さそうな気がする。 先頭からなければ前から持ってくるか、後ろから持ってくるかすればいい。 これはボールに最初にある場所の添字を付けて、…