drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ABC-F 橙色diff 2-SAT 制約:数値が10^6以下 密グラフ グラフの辺数削減テク:スーパー頂点を用いてsparseに グラフの辺数を削減する 2-SATの密を解消する累積OR スラック変数 N個のペア値の問題 解空間:O(2^N)通りの選択肢 カードや山札を扱う問題 数学(整数問題) 見積り大事 Yes/No判定問題 互いに素 各素因数ごとに考える そのまま覚えたいシンプル設定の中堅以上の典型問題 f(i,j)をiとjとに分離する 線形性に着目する SAT グラフテク:スーパー頂点 NoviSteps4D 2-SAT の「密」を解消する累積 OR テクを学んだ！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも互いに素であるようにすることが可能かどうかを判定せよ。 制約 考えたこと いかにも 2-SAT な問題だった。 個の整数を素因数分解して登場しうる各素数 に対して、次のように考えられる。 も も で割り切れるような の個数が 2 個以上ならば、直ちに "No" その個数が 1 個ならば、そのような 以外の各 に対して、 が の倍数ならば、 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F08%2F06%2F235112" title="AtCoder ABC 210 F - Coprime Solitaire (4D, 橙色, 600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2023-08-06 23:51:12 rich https://drken1215.hatenablog.com/entry/2023/08/06/235112 1.0 100%