競技プログラミング
問題：AtCoder Beginner Contest 284 F - ABCBAC 解説 公式の解説を見ながらZ-Algorithmで解いた。Z-Algorithmについては参考URLの章の記事を参照してください。 文字列Sを反転した文字列をS'とおき、SとS'をそれぞれ以下のように表現する。 文字列Sと、Sを…
問題：Road Improvement（道路網改修） 解説 「強連結成分分解（SCC）を使って同じグループの頂点を1つにまとめると、サイクルを含まないDAGになる」という性質を使う。 同じグループのものは1つの頂点とみなした新しいDAGグラフにおいて、入次数が0の頂点を…
問題：advertisement - 宣伝 (Advertisement) 解説 「強連結成分分解（SCC）を使って同じグループの頂点を1つにまとめると、サイクルを含まないDAGになる」という性質を使う。 連絡先を知っている関係をグラフとして表す。 をSCCしたあと、グループを1つの頂…
問題：AtCoder Beginner Contest 233: E - Σ[k=0..10100]floor(X／10k) 解説 を計算せよという問題。 Xの制約が と大きいし、k=0から10100まで計算は普通にしていたら制限時間に間に合わない。 Xの桁数が最大500000なので、問題をエスパーすれば計算量O(桁数…
![はてなブックマーク - ABC233: E - Σ[k=0..10^100]floor(X／10^k) を解いた](https://b.hatena.ne.jp/entry/image/https://takeg.hatenadiary.jp/entry/2021/12/26/151954)
問題：競プロ典型 90 問 073 - We Need Both a and b（★5） 解説 以下の木DPを構築して解きたい。 dp[u][j] := （頂点uを根とする部分木において、）頂点uを含む連結成分の状態がjのときの場合の数。ただしj=0は'a'しかない状態、j=1は'b'しかない状態、j=2…
問題：SoundHound Inc. Programming Contest 2018 -Masters Tournament- C - Ordinary Beauty 1~nの目のサイコロがある m回サイコロを振って、出た目を数列とする 数列の隣り合う2項の差がdの個数を、その数列の美しさとする 数列の美しさの期待値を求めよ …
問題：AtCoder Beginner Contest 190: E - Magical Ornament 解説 解説動画まんまかもしれません。 魔法石が個あります。 各魔法石は隣り合わせになっていいやつが決まっています。重要魔法石の集合をすべて含んでいるように魔法石を1列に並べたとき、必要な…
問題：AtCoder Beginner Contest 190: D - Staircase Sequences 解説 解説PDFまんまです。 初項a, 末項b とすると、数列は[a, a+1, ... , b-1, b]と表現できる この数列の総和をSとすると、 今回の問題では より、 両辺2倍すると、 となる。これを満たすの組…
問題：I - Coins 解説 // dp[i][j] := i枚目を投げたとき表がj枚の確率 // p[i] := i枚目が表が出る確率 ということっぽいのはわかるのだが、ここからどうすればいいのかわからなかったので、一つずつdpの状態を書いていった。 // 1枚投げて表が0枚の確率 dp…
問題：AtCoder Beginner Contest 181: E - Transformable Teacher 解説 とは事前にソートしておきます。 先生と組む生徒以外の人のペアの身長差は、ソートしたときに隣り合う人でペアを作り続ければよさそう。 図にすれば以下。 黒丸が先生と組む生徒、白丸…
問題：AtCoder Regular Contest 054: B - ムーアの法則 解説 微分して二分法をして解を求める方法と、三分探索をして解を求める方法があります。 問題を要約すると、x年後のコンピュータを使ってT(334)の計算が終わる時間をf(x)としたときの、 の最小値を求…
問題：AtCoder Beginner Contest 143: D - Triangles 公式解説PDF：https://img.atcoder.jp/abc143/editorial.pdf 公式解説動画：https://youtu.be/3U_N7zelnMM?t=2983 解説 解説動画まんまです。 二分探索問題です。 問題の条件の、 a < b + c b < c + a c …
問題：AtCoder Beginner Contest 112: D - Partition 公式解説PDF：https://img.atcoder.jp/abc112/editorial.pdf 公式解説動画：AtCoder Beginner Contest 112 解説放送 - YouTube 解説 解説動画まんまです。 のとき、最大公約数の最大値は？という問題です…
問題：AtCoder Beginner Contest 142: D - Disjoint Set of Common Divisors 公式解説PDF：https://img.atcoder.jp/abc142/editorial.pdf 公式解説動画：AtCoder Beginner Contest 142 - YouTube 解説 要約すると、（gcd(A, B)を素因数分解したときの素因数…
最後に編集した日：2023/01/18 ABC C問題 AtCoder Beginner Contest 030: C - 飛行機乗り AtCoder Beginner Contest 031: C - 数列ゲーム AtCoder Beginner Contest 032: C - 列 AtCoder Beginner Contest 140: C - Maximal Value ABC D問題 AtCoder Beginne…
問題：AtCoder Beginner Contest 115: D - Christmas 公式解説PDF：https://img.atcoder.jp/abc115/editorial.pdf 公式解説動画：なし 有志解説動画：【競技プログラミング】AtCoder Beginner Contest 115 D問題をJuliaで解く - YouTube 解説 考察問題であり…
問題：AtCoder Beginner Contest 030: C - 飛行機乗り 公式解説PDF：https://www.slideshare.net/chokudai/abc030 公式解説動画：なし 解説 二分探索問題です。 以下の解説は公式PDFの解説まんまです。 入力例1を考えます。 初期状態は以下のように、高橋く…
問題：AtCoder Beginner Contest 133: D - Rain Flows into Dams 公式解説PDF：https://img.atcoder.jp/abc133/editorial.pdf 公式解説動画：https://youtu.be/8uowVvQ_-Mo?t=3228 解説 考察問題です。数式を変換してXに対する漸化式を導きます。 以下の解説…
問題：AtCoder Beginner Contest 131: D - Megalomania 公式解説PDF：https://img.atcoder.jp/abc131/editorial.pdf 公式解説動画：https://youtu.be/XI8exXVxZ-Q?t=4046 解説 締切が早い仕事から順に終わらせていく貪欲法です。割と直感で思いつく解法です…
問題：AtCoder Beginner Contest 136: D - Gathering Children 公式解説PDF：https://img.atcoder.jp/abc136/editorial.pdf 公式解説動画：https://youtu.be/lyHk98daDJo?t=3172 解説 発想としてはランレングス法です。 S=RRRL という例を考えます。 i=0の人…
問題：AtCoder Beginner Contest 031: C - 数列ゲーム 公式解説PDF：https://www.slideshare.net/chokudai/abc031 公式解説動画：なし 解説1：力技 Nは高々50なので、 くらいまでいけそうだとあたりをつけます。 全探索で、問題をシミュレートして高橋のとり…
問題：AtCoder Beginner Contest 140: D - Face Produces Unhappiness 公式解説PDF：https://img.atcoder.jp/abc140/editorial.pdf 公式解説動画：https://youtu.be/VSeggcnxwrc?t=3564 ABC140のD問題のPython3による解説です。 初見では全くわからず、解説…
問題：AtCoder Beginner Contest 129: D - Lamp 公式解説PDF：https://img.atcoder.jp/abc129/editorial.pdf 公式解説動画：https://youtu.be/L8grWxBlIZ4?t=4363 ABC129のD問題のPython3による解説です。 解説 DP問題です。 これは公式の解説動画がとてもわ…
問題：AtCoder Beginner Contest 130: D - Enough Array 公式解説PDF：https://img.atcoder.jp/abc130/editorial.pdf 公式解説動画：https://youtu.be/ERZuLAxZffQ?t=2473 解説 ABC130のD問題の解説です。しゃくとり法の問題です。 8 10 6 1 2 7 10 1 2 1 と…
問題：AtCoder Beginner Contest 140: C - Maximal Value 公式解説PDF：https://img.atcoder.jp/abc140/editorial.pdf 公式解説動画：https://youtu.be/VSeggcnxwrc?t=2461 解説 ABC140のC問題の解説です。貪欲法（？）問題です。 数列 を リストAsに、数列 …
問題：AtCoder Beginner Contest 032: C - 列 公式解説：https://www.slideshare.net/chokudai/abc032 しゃくとり法の問題です。 公式解説を読むと、「連続する1を圧縮する」という重要なテクニックが書かれていますが、本記事ではそうではない方法で解いて…
いもす法とは いもす法(imos法)とは、長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を、計算量O(N+K)で高速に構築できる方法。 たとえば、「ある連続する区間に、1を足す」という操作を4回したい次の図の…
編集履歴 (2021/02/21)ダイクストラのプライオリティキューが最短距離の小さい順に取り出されるようになっていなかったので、それを修正 ダイクストラ法とは ダイクストラ法とは、「重み付きグラフにおける単一始点最短路アルゴリズム」 つまり、「始点s か…
ベルマンフォード法とは 蟻本によれば、「重み付き有向グラフにおける単一始点最短路アルゴリズム」 つまり、「始点s から各頂点i までの最短コストを求める」アルゴリズムです。 以下の条件で使えます。 DAG（有向グラフで閉路を持たない）である 負のコス…
Union-Find木とは Union-FindまたはDisjoint Setとは、蟻本の言葉を借りると「グループ管理のためのデータ構造」。 ・要素aと要素bが同じグループかどうか ・aが属するグループと、bが属するグループを併合(unite)する ということをしたいときに使います。 U…
