2020-11-08から1日間の記事一覧
AtCoder
AtCoder900点
AGC-C
黄色diff
操作
数え上げ問題
グラフ・盤面・数列の個数の数え上げ
数列
操作後の結果の数え上げ
操作によって作れるものの集合を考える(判定関数を考える)
重複組合せ
制約条件:総和=K
包除原理
包除原理:対称性
パリティ
変数変換して扱いやすい同型な問題を見出す
条件の言い換え
小さいところで帳尻を合わせる
入力が定数個
二項係数
必要条件を列挙したら十分条件になる
補集合を考える
制約条件:ちょうどK個
操作をちょうどK回行う
こういう数え上げ、大好きすぎる!!! 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
AtCoder
AtCoder1000点
AGC-D
競技数学色強め
計算幾何
三角形
三角形の五心
期待値
ある量を固定して考える
二次元平面上のN点の問題
円
図形的量の期待値
赤色diff
連続量問題
浮動小数点型を扱う問題
銅色 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 ]…