2020年4月13日その他圧縮,復元,ランレングス圧縮

ランレングス圧縮(ランレングス符号化)とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。

同じ文字が連続して何文字出現するかに変換します。

例:

In: aaal ...

2020年4月6日グラフグラフ,有向グラフ,閉路,最小値,BFS,ベルマンフォード法,ダイクストラ法

アルゴリズム

最小コストの閉路:

任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除く
v から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...

2020年4月5日AtCoder剰余,約数,600点,互いに素

問題へのリンク

問題概要

\(N\) が \(K\) 未満になるまで以下の操作を繰り返す時、最終的に 1 になるような \(K\) が何通り存在するか答えよ。

\(N\) が \(K\) で割り切れる:\(N\) を ...

2020年4月5日AtCoder500点,貪欲法,後ろから選択肢を選ぶ

問題へのリンク

問題概要

N日間のうちK日働く。

一日働いたら、直後のC日間働けない
i+1 日目は、Sの i 文字目が ‘o’ の時だけ働ける

必ず働く日を全て求めよ。 ...

2020年4月4日AtCoder深さ優先探索,キュー,全探索,400点

問題へのリンク

問題概要

桁ごとに見た時、隣り合う数字の差の絶対値が 1 以下になる数を考える。小さいほうから K 番目の数を求めよ

制約\(1 \leq K \leq 10^5\)
考え方

制約が結構重要で ...

2020年4月3日動的計画法動的計画法,,テーマ記事,競プロ,モノイド,結合則,木DP,部分木,全方位木DP,単位元

競技プログラミングでよく出題される木DPについての説明と、木DPで解ける一部の問題を同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。

木DP基本的な考え方とイメージ

木DP とは、根を一つ固 ...

2020年3月31日AtCoder剰余,動的計画法,数え上げ,逆元,木DP,部分木,階乗

問題へのリンク

問題概要

木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。

制約\(2 \leq N \leq 1000 \)
考え方前提: ...

2020年3月30日グラフグラフ,重み付きグラフ

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。

ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。

負の辺が含まれていても動作する
負の閉路がある場 ...

2020年3月27日データ構造配列,Trie木,文字列,prefix

Trie木は、効率的な検索(retrieval)のために使われるデータ構造です。文字列などの先頭部分(接頭辞: prefix)の共通部分を共有して保存することで、\(O(M)\) での検索を可能にします。(文字列の長さを\(M\) と ...

2020年3月26日数学全探索,素因数分解,約数の個数,平方数,平方根

Nが自然数の2乗で表現できるとき、平方数と言います。

平方数の例4 (= 2×2)
9 (= 3×3)
16 (= 4×4)
25 (= 5×5)
アルゴリズム

以下の方法以外にも色々な求め方 ...