AtCoder二項係数,数え上げ,確率,形式的べき級数・多項式

問題へのリンク

問題概要

座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。
1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\ ...

2020年5月11日AtCoder剰余,ダブリング,周期性

問題へのリンク

問題概要

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

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

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年3月31日AtCoder剰余,動的計画法,数え上げ,逆元,木DP,部分木,階乗

問題へのリンク

問題概要

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

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

2020年3月23日AtCoder二項係数,Lucasの定理,偶奇性,パスカルの三角形,差の絶対値

問題へのリンク

問題概要

1,2,3 で構成された整数列 \(a_1 a_2 a_3 \cdots a_N\) が与えられ、\(x_{i,j}\) を以下のように再帰的に定義する。

\(x_{1,j} := a_j\) ...

2020年3月15日AtCoderset,imos法,遅延評価セグメント木,イベントソート,座標圧縮,競プロ,セグメント木,区間,更新,データ構造

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻&n ...

2020年3月10日AtCoderDP,競プロ,区間DP,区間の除去・圧縮・合体

問題へのリンク

問題概要

N 個の数列 \({a_1, a_2, a_3, \cdots, a_N\}\) があり、以下の操作を数列の要素数が 1 になるまで繰り返す。

隣り合う2つ \(a, b\) を選んで取り除き ...

2020年3月10日AtCoderDP,競プロ,ゲーム,二人零和有限確定完全情報ゲーム,後退解析,最大化,最小化,区間DP

問題へのリンク

問題概要

数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。

a の先頭要素または末尾要素を取り除く。 取り除いた要素を x& ...