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

問題へのリンク

問題概要

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

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

2020年3月10日AtCoder数え上げ,DP,競プロ,ナップサック,合計得点が何通りか

問題へのリンク

問題概要

N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。合計得点は何通り考えられるか?

制約1 ≤ N ≤ 100
1 ≤ p ...

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

問題概要

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

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

2020年3月3日AtCoderグラフ,競プロ,連結成分,Union-Find

問題概要

N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。

まだ友達関係ではない
ブロック関係ではない
友達関係を辿ってたどり着ける
制約\ ...

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

問題概要

長さ 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月20日AtCoder最大値,二分探索,最小値

問題概要

問題へのリンク

風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のとこ ...

2020年2月17日AtCoder400点,二分探索,K番目,2つの積

ARC037 億マス計算 の上位問題です。

問題概要

問題へのリンク

N個の整数 \(A_1, A_2, A_3, \cdots, A_n\) がある。
2つを選んでその積を \(\frac{N(N-1) ...

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

問題へのリンク

問題概要

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

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

2020年2月10日AtCoder二項係数,600点,二次元,区間和

問題へのリンク

問題概要

2次元の平面上で、以下のように関数 f(r,c) を定義する。

f(r,c) := (0,0)から(r,c)までの経路の個数

この時、以下を計算せよ。ただし、\(10^9+7 ...