アルゴリズムロジック

ランレングス圧縮と復元

ランレングス圧縮（ランレングス符号化）とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。 同じ文字が連続して何文字出現するかに変換します。 例： In: aaallgooooooOut: a3l2g1o6 圧縮(encode)する際は Run Length Encoding, 復元(decode)する際は Run Length Decoding と言います。 ア

2020/04/13 10:07

重みが最小となる閉路を求めるアルゴリズム

アルゴリズム 最小コストの閉路： 任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除くv から u への最短経路 d を求める(ダイクストラ/BFS など)d+cost(u,v) を計算するグラフ G に e を戻すd+cost(u,v) の最小値が、閉路の重みの最小値 ※ ある辺 e を含む最小のコストの閉路を、全ての辺について求めます。 ※ 具体例では以下の様に

2020/04/06 11:45

F – Division or Substraction 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 \(N\) が \(K\) 未満になるまで以下の操作を繰り返す時、最終的に 1 になるような \(K\) が何通り存在するか答えよ。 \(N\) が \(K\) で割り切れる：\(N\) を \(\frac{N}{K}\) にする\(N\) が \(K\) で割り切れない：\(N\) を \(N-K\) にする 制約 \( 2 \leq N \leq 10^{12}\)

2020/04/05 10:51

E – Yutori 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 N日間のうちK日働く。 一日働いたら、直後のC日間働けないi+1 日目は、Sの i 文字目が 'o' の時だけ働ける 必ず働く日を全て求めよ。 制約 \(1 \leq N \leq 2\times 10^5\)\(1 \leq K \leq N\)\(0 \leq C \leq N\) 考え方 「必ず働く日」や「必ず働かなくても良い日」というのは、どの

2020/04/05 09:49

D – Lunlun Number 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 桁ごとに見た時、隣り合う数字の差の絶対値が 1 以下になる数を考える。小さいほうから K 番目の数を求めよ 制約 \(1 \leq K \leq 10^5\) 考え方 制約が結構重要です。小さい方から1つずつ全探索することができれば、求められそうだということが分かります。 特殊な条件を持つ数を小さい方から全探索する時（パナソニックプログラミングコンテスト2020 D -

2020/04/04 23:27

木DPと全方位木DPを基礎から抽象化まで解説【競技プログラミング】

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。 木DP 基本的な考え方とイメージ 木DP とは、根を一つ固定した木について、以下のように部分木に関する値を利用して計算する動的計画法です。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 木が N 頂点から構成されるなら、部分木

2020/04/03 12:09

木DPと全方位木DPの総まとめ【競技プログラミング】

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。 木DP 基本的な考え方とイメージ 木DP とは、根を一つ固定した木について、以下のように部分木に関する値を利用して計算する動的計画法です。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 木が N 頂点から構成されるなら、部分木

2020/04/03 12:09