2024-02-05から1日間の記事一覧
AtCoder
AtCoder600点
黄色diff
ARC-D
彩色問題
グラフ
数学(整数問題)
数列
構築
Yes/No判定問題
区間
ほとんどのところで値が一定値に決まる
累積和テク:区間の総和を累積和で高速に求める
条件の言い換え
高速ゼータ変換
包除原理
O(3^N)なbitDP
bitDP
コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…
備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …
AtCoder
AtCoder600点
ARC-B
水色diff
順列を題材とした問題
順列
順列テク:巡回群の直積と見る
数え上げ問題
順列の数え上げ
解空間:O(N!)通りの選択肢
条件の言い換え
各地点について自由度を掛け算していく
選択肢が広い方か狭い方から決めていく
順列をどうのこうのする系、最近多いかもしれない。 問題へのリンク 問題文 考えたこと 操作の内容を解釈するのに少し苦労した。 順列 から誘導される Functional Graph を考えた。このグラフ上で、頂点 から出発して頂点番号が大きくなる限り進んでいったと…
AtCoder
AtCoder400点
茶色diff
ARC-A
算数と数学
算数と数学:パズル
最大安定集合問題
二次元グリッド
駒(コマ)や石やコインを扱う問題
最大スコア
場合分け
パリティ
必要条件を列挙したら十分条件になる
競技数学色強め
最適化問題
慎重に解いた。ノーペナで解けたのは収穫。 問題へのリンク 問題概要 のグリッドに、以下の条件を満たすように 個のルークと 個のポーンを配置することが可能かどうかを判定せよ (ルークとポーンを合わせて駒と呼ぶ)。 どのルークについても、それと同じ行・…