はむ吉(のんびり)の練習ノート

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

yukicoder No.638 Sum of "not power of 2":解法と実装

昨日 (1/26) に,yukicoder contest 181 - yukicoder が開催されました.私は参加できなかったのですが,このコンテストで出題されたうちの一問である No.638 Sum of "not power of 2" - yukicoder を演習として解きました.学習記録を兼ねて,この問題の解き方とその実装を自分なりに記しておきます.

問題の趣旨

正の整数 N が与えられる.等式 N = a + ba, b はいずれも 2 の整数乗として表せない正の整数)を満たす二つ組 (a, b) のうち,a が最小となるものを求めよ.そのような二つ組が存在しなければ指摘せよ.

解き方

所与の a, b がいずれも 2 の整数乗として表せないという条件をそのまま考えるのは難しいので,まずは逆に  2^k\:(k \ge 0, k\in\mathbb{Z}) の形で表せる 1 以上 N 以下*1自然数がどれだけあるか考えましょう.このような数は,床関数を用いると  k = 0, 1, \cdots, \lfloor \log_2 N \rfloor の 計  \lfloor \log_2 N \rfloor + 1 個あります.所与の等式から,a を決めると b が決まる(あるいはその逆)なので,適さない(a, b の少なくとも一つが 2 の整数乗となってしまう) (a, b) は高々 2(\lfloor \log_2 N \rfloor + 1) 個しかないことになります.

上記の議論に基づき,1 ≤ abN - 1 の下で*2,解を探索しましょう.とりあえず, a = 1, 2, \cdots と小さいものから順番に見ていくとします.先述のように,「適さない」 a,すなわち ab の少なくとも一方が  2^k 型になってしまう a が, 1 から N の整数たちのなかに高々 2(\lfloor \log_2 N \rfloor + 1) 個紛れ込んでいます.このような「適さない」 a が,どのように分布しているのかは,容易にはわかりません.ひとところに固まっているかもしれませんし,散らばっているかもしれません.しかし,裏を返せば,少なくとも  a = 1 から始めて  2(\lfloor \log_2 N \rfloor + 1) + 1 個目まで順番に a を見さえすれば,(存在するならば)「適する」 a を見つけられるのです.すなわち, a = 1, 2, \cdots, 2(\lfloor \log_2 N \rfloor + 1) + 1 を全探索し,それぞれが所与の条件を満たすか確認すれば十分なのです.さらに言い換えると,上記の「適さない」a の集合 S (便宜上 0 も含めるものとする) について,mex S を求めればよいのです *3. 制約は  N \le 10^{18} ですから,高々百数十個の数について調べるだけで済み,制限時間には間に合います.

Haskell による実装例

import Data.Int (Int64)
import Text.Printf (printf)

-- 失敗しうる関数なので,Maybe を用いる
-- 解がないときは Nothing を返す
-- 解があるときは Just にくるんで (a, b) を返す
findPair :: Integral a => a -> Maybe (a, a)
findPair n
    | null cands = Nothing
    | otherwise = let a = head cands in Just (a, n - a)
    where
        -- 上で述べた 2 の整数乗で表せる N 以下の正整数の個数
        numKs = succ $ floor $ logBase (2.0 :: Double) $ fromIntegral n
        --  2^k 型の値たち
        ps = [2 ^ k | k <- [0 .. numKs - 1]]
        -- a が満たすべき条件は,a も b = N - a も 2^k 型でないこと
        f x = notElem x ps && notElem (n - x) ps
        -- 適する a たちのリスト
        cands = filter f [1 .. min (numKs + 1) (n - 1)]

main :: IO ()
main = do
    n <- readLn :: IO Int64
    case findPair n of
        Nothing -> putStrLn "-1"
        Just (a, b) -> printf "%d %d\n" a b

感想

当初解法が思い浮かばず,解説を読みましたがそれでもその正当性について納得できませんでした.しかし,紙に書いて考えてみることで,理解に至りました.画面とにらめっこするだけではなく,手を動かしてもみることの重要性を感じました.

*1:厳密には N - 1 以下でよい

*2:最小の a を求めたいので,このような設定を行います.

*3:ここでの mex (minimum excluded) は,集合の要素ではない数の中で,最も小さい非負整数を与える関数です.この関数は,ゲームに関する問題で有用である Grundy 数の計算に登場します.