atcoder.jp 問題 消費税T%のとき課税後の整数値として現れないN番目のものを出力せよ。 制約 解説 ある自然数Aがあって、T*A の結果、100の位へ繰り上げがあるなら、(100+T)*A/100-1 は登場しない整数値である。 なぜなら、T*A で100の位への繰り上げが生じ…

燃やす埋める系の問題をまとめて解いたので、学んだ点について書き残しておく。 燃やす埋める問題とは以下の様な問題である。 いくつかのものが与えられて、それを赤か青に塗り分ける必要がある（燃やすか埋めるか）。それぞれがどちらの色に属するかによっ…

問題 atcoder.jp 公式解説 atcoder.jp 解説にある通り、青白赤を0,1,2に対応させることで各ブロックは二項係数を使って最下段のブロックのから（二項係数の計算量は無視して）O(N)で求めることができるという問題。 この問題には更に 二項係数の計算において…

最近DPの漸化式を行列式に変換するセンスを磨くために関連問題を解いており、問題や行列累乗全般について雑多なメモを残しておこうと思う。 フィボナッチ数列のN項目を高速に求める フィボナッチ数列 例題をいくつか ABC 009 D - 漸化式 ARC 050 C - LCM 111…

問題 yukicoder.me 2-SATについての前提 2-SAT問題の解き方 論理和を論理包含に変換 1を元にimplication graphを作る 2のimplication graphを強連結成分分解する 3の結果、ある要素Xとその否定￢Xが強連結成分であるなら、その2-SATを満たす解は存在しない …

前提 有向グラフGの頂点の部分集合をSとする。 Sが強連結であるとは、Sの任意の2頂点間が行き来可能であること Sが強連結成分であるとは、Sに他のどの頂点を追加してもそれ以上強連結にならないこと 強連結成分分解とは、強連結成分を1つの頂点にまとめるこ…

AC Libraryに、より高速なライブラリが存在する。 https://atcoder.github.io/ac-library/document_ja/string.html 以下に載せた実装は、自分の理解を深めるために実装したもの。（蟻本のものにアレンジを加えclass化した。計算量は変わらず、Manber & Myers…

制約から座標圧縮をすべきであることは想像しやすいが、この問題はかなり難しいと思った。 atcoder.jp 前提 座標圧縮 pione.hatenablog.com 解説 座標圧縮を行う問題でよく見かけるパターンは以下の2つである。 いくつかの長方形が与えられて、長方形が重な…

前提 一次元座標圧縮はBITによる転倒数の数え上げでお馴染み。 二次元の場合は、x軸、y軸を独立に捉えることでほぼ同様に求めることができる。 二次元座標圧縮における注意点は、登場する座標の1つ隣の座標も登録する点にある。これは登場する座標だけで圧縮…

前提 基本的な考えは、Bellman-Ford法による最小費用流の求め方と同じである。 以下の実装では高速化のためBellman-Ford法の実装個所をDijkstra法に置き換えており、同時に負の辺が存在するグラフに対してDijkstra法を適用するため、ポテンシャルを導入して…

前提 最小費用流問題のグラフには、最大流問題で与えられる辺の情報に加えて辺のコストが付与される。 以下の実装では、このコストに対してS-T最短路を1つ見つけて目いっぱい流す、その経路が限界になったら次の最短路を見つけて目いっぱい流して、という事…

前提 Dinic法を理解するには、先にFord-Fulkerson法を知っていると早い。 pione.hatenablog.com Dinic法の基本的な動作はFord-Fulkerson法と同じで、残余グラフを構築して増加路の辺、逆辺の capacity を更新していき、更新できるパスがなくなるまでそれを繰…

前提 最大流問題とは、辺に capacity を持つグラフが与えられて、始点から目いっぱい水を流した時に終点に流せる最大量を求める問題。 グラフの最大流は、そのグラフのS-T最小カットに対応する。 計算量: O(|flow||E|) （最大フローをflow、辺数をEとする） …

A(500) C1(750) E(2250) の3完。良問が多い回だった。 A - Shifting Stacks (500点) 英文読解の問題。 前の要素を自身より後ろの任意の場所に移動させられるという条件で、狭義単調増加を作れるかという問題。 B - Eastern Exhibition (1000点) 本番中にこれ…

問題 onlinejudge.u-aizu.ac.jp 前提 ダイクストラ法 クラスカル法 最近共通祖先（Lowest Common Ancestor） 解説 ダイクストラ法、クラスカル法（的な発想）、Lowest Common Ancestor、3つ基本アルゴリズムの合わせ技で解ける良問。 ざっと他の人の解説を見…

問題 atcoder.jp 前提 最長共通部分列問題（Longest Common Subsequence） 解説 最長共通部分列問題（Longest Common Subsequence）が解法の基盤になっていると思った。 LCSのDPでは、複数の列における部分列の長さの最大値を管理するが、この問題では不一致…

yukicoder.me 問題 1～nからn-1個を選んで作れる最小公倍数のうち、その最小値を求め、998244353で割った余りを求めよ。 前提 エラトステネスの篩 pione.hatenablog.com 解説 まず除外すべき1つの数は自明に、1～nの中の最大の素数である。 次にn-1個の数の…

一次合同式についての教育的な良問だったので、考えたことを書き残しておく。 問題 atcoder.jp 考えたこと この問題は言い換えると、初期値がsの状態からkを何度か足すことで、nの倍数を作れるか、という問題になる。 つまり、(kx+s)%n==0となる最小のxを求…

高難度帯の部分問題として出てくるので実装を置いておく。 実装 以下の実装は、訪れた順に頂点を採番していく。 /// オイラーツアー struct EulerianTrail{ vector<int> order; EulerianTrail(vector<vector<int>>& G, int root=0){ int n=G.size(); order.resize(n); int cur</vector<int></int>…

過去問埋めしてて、トポロジカルソートで解く問題に当たって面白かった↓。 atcoder.jp 良い機会なので、改めて実装についてまとめておこうと思う。 前提 トポロジカルソートとは、閉路無し有向グラフ(DAG)において、どの頂点もその出力辺の先の頂点より前に…

エラトステネスの篩と、それを利用した素因数の高速列挙の実装をライブラリ化した。（どちらかというと後者の実装を残す目的で作った） 前提 整数nまでの素数の列挙を高速に行うアルゴリズム O(nloglogn) https://mathtrain.jp/eratosthenes https://detail.…

前提 Trie木は、複数の単語（文字列）を登録でき、ある文字列（またはそのprefix）が登録済みであるかを高速に検索できるデータ構造 基本的な機能はシンプルに、insert / searchの2つだけ 実態は有向木 基本的な動作は、単語のprefixが同じならNodeを共有し…

二分探索と比べて、区間の内分点の取り方やら、下に凸か上に凸かやら、地味に考えることが多いので汎用性を目指してライブラリ化してみた。 前提 三分探索とは、ある区間[l, r]において、極値がただ一つだけ存在するとき、その極値の近似値を区間の長さをnと…

これは何 最近コンテストで、入力値が小数第4位程度まで与えられ、その入力値を素直にdoubleで受け取って計算すると丸め誤差で WA となるような問題が散見されるようになった。 （直近の問題だと ABC 191 D Circle Lattice Points がそう） atcoder.jp この…

要求される度に、uniqueやらeraseやら、1-indexやらの箇所で微妙に考えてしまうので、この際ライブラリ化しておく。 ※ 転倒数には、i < j でかつ、a_i > a_j であるとき転倒とする場合と、a_i >= a_j であるとき転倒とする場合の2種類があり、以下の実装は前…

他ライブラリ（転倒数等）で活用されることがあるので置いておく。 前提 Fenwick Treeとも 競プロにおいては、BITでできることは以下の2点であると抑えておこう。 累積和テーブルの更新: add 指定した区間の累積和の計算: sum 機能を限定することで扱いやす…

今まで文字列照合系問題は、DP(LCS)で頑張っていたけど、持っていたら便利そうだと思ったのでライブラリを用意してみた。 前提 Z-Algorithmとは、最長共通接頭辞の長さを線形時間で求めるアルゴリズム。 文字列の長さをnとして、O(n2)を、O(n)に改善できる …

クラスカル法など、他ライブラリから呼ばれることがあるので実装を置いておく。 前提 グループの管理を高速で行うことができるデータ構造 実態は木（森）になっている ある状態から、グループを併合することができ、分割することはできない UnionFind木の機…

前提 いずれも発想は貪欲法である。 クラスカル法 実装内容の理解についてはクラスカル法の方が楽 頂点数に対応する大きさのUnionFind木を用意する グラフの辺を、重みの小さい順に見ていき、(u, v)がまだ同じグループに属していないならばその辺を採用する…

前提 ダブリング手順 dp[i][j]:=頂点iの2j個上の頂点 iは頂点数nに対して、log_n 初期化: まずdpを-1で初期化したのち、dp[0][j]、つまり1個上のノードを登録する 以降、dp[i+1][j]=dp[i][dp[i][j]] で更新 ダブリングのわかりやすい解説 satanic0258.hatena…