2022-12-13から1日間の記事一覧
AtCoder
AtCoder600点
ABC-G
黄色diff
グラフ
グラフ・盤面・数列の個数の数え上げ
入力が定数個
BFS
最短路問題
特殊なmod
多項式・FPS(形式的冪級数)
FPS(形式的冪級数)の高等演算
DP
最大値や最小値に着目する
DFS木やBFS木を考察する
二項係数
特定の場所を決め打つことで単純な場合に帰着する
残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…
AtCoder
AtCoder500点
ABC-F
青色diff
XOR
0と1の問題
再帰的に上位桁から順に値で分類した木を作る
数列
各桁ごとに見る
辞書順
最大値の最小化
Greedy
BinaryTrie
そのまま覚えたいシンプル設定の中堅以上の典型問題
Greedy:辞書順最小を求める
数列に対して、2 進法で表して、再帰的に上位桁から 0 と 1 で分類した木を作る!!! こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…
AtCoder
AtCoder400点
ABC-D
緑色diff
DP
部分和
ナップサックDP
N個からK個を選ぶ設定の問題
DP状態:あまり
DP状態:個数
制約条件:ちょうどK個
数列
総和を求める
最大スコア
最適化問題
部分和問題の応用問題! 問題へのリンク 問題概要 個の非負整数 が与えられれる。 これらの整数から 個選んで、総和が の倍数となるようにする。その値として考えられる最大値を答えよ。 の倍数にするのが不可能な場合は -1 を答えよ。 制約 前提知識 この問…