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

問題へのリンク

問題概要

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

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

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

問題へのリンク

問題概要

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

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

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日AtCoder競プロ, セグメント木, 区間, 更新, データ構造, set, imos法, 遅延評価セグメント木, イベントソート, 座標圧縮

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻 \(S_i−0.5\) から時刻 \(T_i−0.5\) まで座標 \(X_i\) ...

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& ...

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

問題へのリンク

問題概要

二人で以下のゲームを行う。先手と後手のどちらが勝つか?

以下の操作を交互に行うA = \( a_1, a_2, \ldots, a_N\) の元 x を一つ選び、K 個の山から丁度 x 個取り ...