2-SAT は強連結成分分解の典型的な応用例！ 問題へのリンク 問題概要 旗 を数直線上に設置したい。旗 は、座標 または座標 に設置可能である。 ただし、どの 2 つの旗も、その距離が 以上となるようにする必要がある。 本の旗を設置することが可能かどうかを…

素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…

アルファベットは 26 文字！26 は偶数！ 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の無向単純グラフ が与えられる。各頂点 には、1 文字の英小文字 が振られている。ここで正の整数 が与えられ、改めて次のように定義されるグラフ を考える の頂点集合…

木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…

順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…