2020-11-08から1日間の記事一覧
AtCoder
AtCoder900点
AGC-C
黄色diff
操作
数え上げ問題
グラフ・盤面・数列の個数の数え上げ
数列
操作によって何通り作れるかの数え上げ
判定関数を考える
重複組合せ
総和一定制約の数え上げ
包除原理
包除原理:対称性
パリティ
変数変換して扱いやすい同型な問題を見出す
条件の言い換え
小さいところで帳尻を合わせる
操作をK回まで行える
入力が定数個
二項係数
必要条件を列挙したら十分条件になる
補集合を考える
制約条件:K以下
こういう数え上げ、大好きすぎる!!! 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
銅色 diff 問題が自力で解けて嬉しい。(修正:赤色になった) 問題へのリンク editorial 問題概要 原点を中心とする半径 1 の円周上に 個の点 がある (偏角が入力として与えられる)。 これらの点からランダムに 3 点選んでできる三角形の内心の座標の期待値を…
構築楽しかった 問題へのリンク editorial 問題概要 のグリッド上に のドミノを互いに重ならないように配置していく。 どの行・列を見ても、その行・列上にある のドミノの個数が互いに等しいような配置を求めよ。存在しない場合は "-1" を出力せよ。 制約 …
AtCoder
AtCoder800点
AGC-C
黄色diff
数え上げ問題
操作
操作によって何通り作れるかの数え上げ
判定関数を考える
変数変換して扱いやすい同型な問題を見出す
条件の言い換え
DP
操作:circular_shift
0と1の問題
操作をK回まで行える
DP高速化
DP高速化:いもす法
DP高速化:累積和
グラフ・盤面・数列の個数の数え上げ
こういう問題めっちゃ好き!!! 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…