枝刈り全探索https://codeforces.com/problemset/problem/453/B問題概要N要素の正整数列Aが与えられる。最小となるような数列Bを構成せよ。相異なる2要素が互いに素であるという条件から「1は何回でも使える」「1以外の数は最大でも1回しか使えない」ことがいえる。Aiが最大でも30までという制約の小ささに注目すると、1が何回でも使えることからBに対して59以上の数は使う意味がないということがわかる(代わりに1を使えば必ずAとの差は小さくなるので)。場合、BiとBjをswapすれば必ず最終スコアは小さくなる)。互いに素の条件から、ある数を使ったときそれとのGCDが1でない数は以降使えなくなる。使える数はたかだか60なのでどの数がもう使えないかは64bit型整数で管理することができる。以上の条件をすべて踏まえると、【今見ているインデックス、使える数の最大値、もう使えない数のビットマスク、現在の差の合計】あたりの値をもってDFSで全探索していくことができ、制限時間も長いのでこれで十分間に合う。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。