2020年1月19日AtCoder最小回数,操作,700点,動的計画法,bit全探索,BIT,bitDP,パリティ

問題へのリンク

問題

表が\(A_i\)、裏が\(B_i\)、と書かれた\(N\)枚のカードがある。「隣り合う2枚を選択して、入れ替えて裏返す」という操作をして、カードの並びが広義単調増加になる最小回数を求めよ。

制約 ...

2020年1月18日データ構造競プロ,データ構造,連結成分,Union-Find

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。

素集合系の例

素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用い ...

2020年1月17日AtCoder動的計画法,400点,数字の文字列,桁ごと,剰余

問題へのリンク

問題

一部が ? で与えられる数字の文字列 S について、13で割って5余る数で考えられる物は何通りあるか。
答えを 1e9+7 で割った余りで答えよ。

制約\(1 \leq |S| \leq ...

2019年12月6日数学最大公約数,競プロ,ユークリッドの互除法,拡張ユークリッドの互除法

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。

このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られ ...

2019年12月4日数学剰余,二項係数,テーマ記事,競プロ,素数,逆元

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。

...

2019年12月3日AtCoder300点,順列,全探索

問題

平面上でN個の座標が与えられる。全ての点を１回ずつ通るような動き方は\(N!\)通りあるが、これらの総移動距離の平均を求めよ。

元の問題: C – Average Length

解き方

二通りの方 ...

2019年12月2日探索順列

\(n!\) 通りの全探索を行いたい時に順列が用いられます。

順列(permutation)とは、n 個のものを順番に並べるのは何通りあるかを考える問題です。n 個全てを区別できるなら、\(n!\) 通りの並べ方があります ...

2019年11月30日探索入門,幅優先探索,グラフ,キュー

幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。

木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状 ...

2019年11月30日AtCoderグラフ,木,400点,BFS,辺彩色

問題

木構造について、頂点から見た時に自身から伸びる枝に重複が無いように色を塗る。使う色の数の最小値はいくつか？

問題：D – Coloring Edges on Tree

(木構造はグラフの一種と捉 ...

2019年11月30日探索全探索,入門,幅優先探索,スタック,再帰関数

深さ優先探索とは、全探索アルゴリズムの一種です。グラフや、グラフと同一視できるものを探索する際に良く使われます。

幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を ...