問題 要素のスワップを繰り返して数列を昇順にソートしたい。数列中のXとYを入れ替える時のコストをX+Yとする。ソートに必要な最小コストを求めよ。 やりかた 数列を巡回置換のまとまりに分解する。 例えば(3,5,7,4,2,1,6)であれば(3,7,1,6)(5,2)(4)となる。…

問題 直径Dの円に内接する複数の直径dの小円を考える。小円同士の中心が少なくともs+d以上離れているように配置したい。最大でいくつの小円を配置できるか。 やりかた 配置する間隔は等間隔にする。間隔は円の個数に対して単調減少なので二分探索できる。C個…

問題 一直線の道路上にN個のぬかるみがありそれが[s,e)の形で与えられる（s,eは非負整数）。なお与えられる範囲に重複はない。長さKの木板が無数にあり、これらを使ってぬかるみをすべて覆いたい。最小でいくつの木板が必要か。 やりかた 貪欲。 領域の左端…

問題 略 やりかた 見開きのページ番号の和はどの見開きであっても一定（ページ数以上の最小の4の倍数+1になる）になるので片一方の番号がわかれば見開きのもう片方の番号は自動的に決まる。コード上では見開き上の若番の番号から老番のページ番号を求めて、…