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

問題へのリンク

問題概要

N日間のうちK日働く。

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

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

2020年3月8日AtCoder剰余,数え上げ,500点,競プロ,区間,素数,Pで割り切れる

問題概要

長さ N の数 S が与えられる。
素数 P で割り切れるような区間の選び方は何通りあるか?

制約\(1 \leq N \leq 2 \times 10^5\)
\(2 \leq P \leq 10000\ ...

2020年3月2日AtCoder500点,セグメント木,区間,set,クエリ

問題概要

長さ N の英小文字からなる文字列 S を与えられ、以下の二種類のクエリ合計 Q 個を処理する。

S の \(i_q\) 番目を \(c_q\) に変更する
S の \(i_q\) 番目から \(r_q\) 番目ま ...

2020年2月24日AtCoder剰余,二項係数,操作,数え上げ,500点,重複組合せ

問題概要

n 個の部屋に 1 ずつ人がいる。以下を k 回行ったとき、考えられる状態は何通りあるか \(10^9+7\) で割った余りで答えよ。

ある部屋 \(i\) にいた人が、\(i \neq j\) を満たす任意の部屋 \( ...

2020年2月17日AtCoderDP,500点,桁ごと,お釣り,硬貨

問題へのリンク

問題概要

\(1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}\) の紙幣で金銭のやり取りをする。

N 円払う時、支払うのに使う紙幣の枚数と、お釣りでもらう紙幣の ...

2020年2月10日AtCoder動的計画法,数え上げ,DP,500点,桁DP,場合分け

問題へのリンク

問題概要

1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。

制約

\begin{align}
&1 \leq N \leq 10^{100} \\ ...

2020年1月26日AtCoder操作,最大公約数,不変量,最大値,500点,約数

問題へのリンク

問題概要

N 個の整数列 \(A_1, A_2, \cdots, A_N\) に、以下の操作をK回まで行う。これら全てはある数の倍数となるが、その数の最大値を求めよ。

操作:\(A_1, A_2, ...

2020年1月25日AtCoder有向グラフ,閉路,DAG,有向非巡回グラフ,半順序,500点

問題へのリンク

問題概要

N人の選手がいる。各選手は1日1試合のみできる。総当たり戦を行う時、最短で何日かかるか?

ただし、i 番目の選手は \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, ...