Dが簡単評価なのにWA放置していることに気づいて再挑戦した記録。
A - Eating Symbols Easy
シグネチャを決める。
abc101a :: String -- S
-> Int -- 答え
abc101a = sum . map f
where
f '+' = 1
f '-' = -1
B - Digit Sums
シグネチャを決める。
想定解に沿うべく、10で割った商と余りで$S(N)$を求める。
abc101b :: Int -- N
-> Bool -- 答え
abc101b n = 0 == mod n (s n)
s :: Int -> Int
s 0 = 0
s x = let (q,r) = divMod x 10 in r + s q
Nを文字列のままで受け取る方が二度手間がない。
細かいことを言うと、read の中で digitToInt をしているのでやはり二度手間か？
import Data.Char
abc101b :: String -- N
-> Bool -- 答え
abc101b n = 0 == mod (read n) (sum $ map digitToInt n)
C - Minimization
シグネチャを決める。
abc101c :: Int -- N
-> Int -- K
-> [Int] -- Ai
-> Int -- 答え
考える
結局全て1にするしかないので、1を含んだ区間をまずK個1にする。
あとはその両側を、端を1つ重ねて、K-1個ずつ1にすることを繰り返して全て1にする。
1が先頭からK個以内にあるとき、左端からK個、続きK+1個、…と操作する。
1が先頭よりもっと遠くにあるとき、端を1つ重ねる、の重ねる向き（操作する順）を変えれば、結局同じ回数の操作で目標を達成できるとわかる。
その回数は、余りを切り上げる除算を $\div$ として $1 + (N-K) \div (K-1)$ となる。
abc101c n k _ = succ $ divrup (n - k) (pred k)
divrup :: Int -> Int -> Int
divrup x y = negate $ div (negate x) y
$1 + (N-K)/(K-1) = (N-K+K-1)/(K-1) = (N-1)/(K-1)$ と式変形することで、もっと単純にできる。
abc101c n k _ = divrup (pred n) (pred k)
なんにせよ $A_i$ は使わないひっかけ問題。
標準入力から取り込むことすらサボるとタイムを稼げる。
D - Snuke Numbers
シグネチャを決める。
abc101d :: Int -- K
-> [Int] -- 答え
自分の解答
考慮する必要のある S(n) の上限
$S(n)$ が $T$ であるような最小の数を考える。
それは、$d = \min(9,T)$ を最下位桁とし、その上の桁に $S(n)$ が $T - d$ となる数 を乗せた数になる。
$R(0) = 0$
$R(T) = R(T - d) \times 10 + d \ \ (d = \min(9,T))$
$T$ を1増やしたとき、$T$ が9の倍数を超えるたびに $R(T)$ は1桁増える。そうでないとき、最上位桁が1ずつ増える。
どちらにせよ、$R(T)/T$ は爆発的に増加する。
さて、すぬけ数 $n$ とは、それより大きなあらゆる整数 $m > n$ について、$\frac{n}{S(n)} \leq \frac{m}{S(m)}$ であるような数と定義されている。
これは定義上、いくらでも大きな $T = S(m)$ についても成り立つ必要がある。しかし、$T = S(m)$ が十分大きいとき、それを満たす$m = R(T)$ は大きな数となり、$R(T)/T$ は爆発的に増加するため、$n/S(n)$ より勝手に大きな数となり、検討する必要がなくなる。
具体的には、問題の制約で $10^{15}$ 以下のすぬけ数のみを考えるので、$S(99...99 (= 10^{16}-1)) = 9 * 16 = 144$ 以下の $T$ について考えれば余る。
S(n) を固定した すぬけ数候補
$x$をすぬけ数とする。
任意の $1 \leq T \leq 144$ に関して、$S(y) = T$ となる最小の整数 $y_T > x$ が得られているとする。
それらの中で、$y_T/T$ が最小となる値のうちの $y$ の最小値が次のすぬけ数である。
他のどの数 $m$ よりも $y/S(y)$ が小さいか等しいからである。
その後、$y$ を下限として $y_T$ を作り直して繰り返すことで、順にすぬけ数を取り出すことができる。
Xより大きくS(Y)=Tを満たす最小のY
この方針でできそうなので、$x$ と $T$ が指定されたときに $x < y, S(y) = T$ を満たす最小の $y$ を構成する方法を考える。
$x < y$ とするために、$x$ のいずれかの桁を1大きな数にする。
すると、それより下の桁はどうなっていても $x$ より大きくできるので、極力小さい値とするために、下の桁になるべく数を集めて、
全体で $S(y)=T$ となるように桁を埋める。
この操作をできるだけ下位の桁で行う。
最上位桁まで全て試してもできなかった場合、$x < 10^k$ となる最小の数を持ち出してこれで再度試みる。
それでも駄目なら $10^{k+1}$ で試す…とすれば、いつかは発見できる。
なお、$T=1$ の場合は、そのような数は $1,10,100,\dots$ だけなので、別に扱う。
結果
import Data.List
import qualified Data.Heap as PQ
abc101d :: Int -> [Int]
abc101d k = take k snukeNumbers
-- 10進の桁ごとに分解（下位が前）
enDec :: Int -> [Int]
enDec 0 = []
enDec x = let (q,r) = divMod x 10 in r : enDec q
-- enDecの逆関数
deDec :: [Int] -> Int
deDec = foldr (\x acc -> x + acc * 10) 0
nextSN :: Int -- T
-> Int -- X
-> Int -- X<Y, S(Y)=T となる最小のY
nextSN 1 x = head $ dropWhile (x >=) $ iterate (10 *) 1
nextSN t x = deDec $ head
[ redump i re (ei:ds)
| xs <- xs0 : xss
, (i,di:ds,acci) <- zip3 [0 ..] (tails xs) (tail $ scanr (+) 0 xs)
, ei <- [succ di .. 9]
, let re = t - acci - ei, 0 <= re, re <= 9 * i ]
where
xs0 = enDec x
xs1 = map (const 0) xs0 ++ [1]
xss = xs1 : map (0 :) xss
-- i桁でreをなるべく小さいenDec表現に収めものをdsの前（下位桁）に繋げる
redump 0 0 ds = ds
redump 0 _ _ = error "amari"
redump i re ds = let b = min 9 re in b : redump (pred i) (re - b) ds
-- 優先度付きキューの要素
data SN = SN Int Int deriving Eq
-- n/S(n) の小さい順、n の小さい順
instance Ord SN where
compare (SN i v) (SN j w) = compare (v * j, v) (w * i, w)
snukeNumbers :: [Int]
snukeNumbers = loop 0 pq0
where
pq0 = PQ.fromList $ [SN i v | i <- [1 .. 9 * 16], let v = nextSN i 0]
-- n/S(n)の小さい順に取り出し、直前のすぬけ数xを越えていたらそれが次のすぬけ数
-- そうでないものはxより大きいものを探し直してキューに戻す
loop x pq
| v <= x = loop x pq2
| otherwise = v : loop v pq2
where
Just (SN i v, pq1) = PQ.uncons pq
pq2 = PQ.insert (SN i $ nextSN i x) pq1
ACしたけれど、どうも他の人の解答はこんな計算はしていないようだ。
公式解説を（難解だけど）読む。
公式解説のやり方
読んでもさっぱりわからん。
他のHaskell解答を味わう
非常にシンプルで高速（2ms!）なproton06さんの提出
を解読。
snukeNumbers :: [Int]
snukeNumbers = loop 0 1
where
loop :: Int -- n : 直前のすぬけ数
-> Int -- b : 1増やす桁 base
-> [Int] -- こたえ
loop n b = m : loop m c
where
c = if check (n + b) b then b else b * 10
m = n + c
check :: Int -- n : 今回のすぬけ数の候補
-> Int -- b : nを作るために足しこんだb
-> Bool -- こたえ このbで正しかったか
check n b = n * s (n + b) <= (n + b) * s n
-- B問題のsと同じ
s :: Int -> Int
check は $\frac{n}{S(n)} \leq \frac{n+b}{S(n+b)}$ を判定している。
loop の計算では、前回のすぬけ数 n にベース b を足した n + b を次のすぬけ数にしたいが、
同じペースでさらにその次の数 n + b + b との間で $n/S(n)$ の値が逆転するとき、
この b は次の位に移す必要がある、となっている。
（なんでそれでいいのかはわからない。）
ゴルフに走っているjasyさんの提出
を解読。
import Data.Char
snukeNumbers :: Int
snukeNumbers = loop 1 1
where
loop :: Int -- n : 今回のすぬけ数
-> Int -- b : 1増やす桁 base
-> [Int] -- こたえ
loop n b = n : loop n1 b1
where
n1 = n + b
n2 = n + b + b
b1 = if b * s n2 < n2 then b else b * 10
-- B問題のsと同じ
s :: Int -> Int
全体のロジックはproton06さんのものとほぼ同じで、
結果のすぬけ数を出力するタイミングが1つ遅くなっている。
なので、次のすぬけ数は n + b で固定的に決まり、
その次に使うbaseをズラすかズラさないかだけ計算をしている。
ただその判定基準が $b < \frac{n2}{S(n2)}$ と違っていて、
なんでこれでいいのか輪をかけてわからない。
どちらの提出も、公式解説にある「これらすべてに対して $\frac{x}{S(x)}$ を計算して比較」という動作は見当たらない。
次のすぬけ数を作るために1増やす桁はどこなのかを決定的に判断している。
降参です…