2020年5月19日その他二次元, 座標圧縮

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。

仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。

例:\(0\) ~ \(10^9\) の数直線はメモリにのらない

その他, その他競プロ, LCA, ダブリング, 繰り返し二乗法

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において

前処理:\(O(N \log K)\) 時間, \(O(N ...

AtCoder剰余, ダブリング, 周期性

問題へのリンク

問題概要

町が \(N\) 個ある。町 \(i\) から町 \(A_i\) に移動することを K 回繰り返す。
町 1 から始めた時、最終的にどの町にたどり着くか?

制約\(2 \leq N \ ...

探索

forループを用いた全探索などは比較的簡単な内容なので直感的にもわかりやすいですが、簡単なものしか全探索できません。

複雑な条件や構造を持つものを全探索したい場合には、再帰関数を用いた深さ優先探索(DFS)を用いる必要があ ...

その他圧縮, 復元, ランレングス圧縮

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

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

例:

In: aaal ...

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

アルゴリズム

最小コストの閉路:

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

AtCoder剰余, 約数, 600点, 互いに素

問題へのリンク

問題概要

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

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

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 とは、根を一つ固定した木について、以 ...