ferinの競プロ帳

競プロについてのメモ

2019-02-16から1日間の記事一覧

ARC084 E - Finite Encyclopedia of Integer Sequences

問題ページ 解法 まずKが偶数ならば(K/2, K, …, K)となる数列が答えになることがわかる。よってKが奇数のものについてのみ考える。 ナイーブな解法として答えの数列でi番目で数列のa番目をつくるにはi番目の数字が一意に定まるとして前から決めていくような…

ARC065 E - へんなコンパス / Manhattan Compass

問題ページ 解法 まずマンハッタン距離なので45度回転しチェビジェフ距離に変換しておく。 コンパスの移動で穴2つの距離が変わることはない。したがって穴aと穴bの距離Dと等しい穴の組が何個あるのかを考えればよい。穴の組O(N^2)個について全て考えるのは不…