A - Star
シグネチャを決める。
abc192a :: Int -- X
-> Int -- 答え
abc192a x = 100 - mod x 100
B - uNrEaDaBlE sTrInG
シグネチャを決める。
import Data.Char
abc192b :: String -- S
-> Bool -- 答え
abc192b s = and $ zipWith ($) (cycle [isLower, isUpper]) s
判定関数を交互に入れ替えて適用する。
C - Kaprekar Number
シグネチャを決める。
abc192c :: Int -- N
-> Int -- K
-> Int -- 答え
忠実に実行する。showを使わない方が速かったのでそれで。
結果
import Data.List
import Data.Tuple
abc192c :: Int -> Int -> Int
abc192c n k = iterate g n !! k
g n = enc ds - enc (reverse ds)
where
ds = sort $ dec n
dec = unfoldr step
where
step 0 = Nothing
step x = Just $ swap $ divMod x 10
enc = foldr (\d acc -> d + acc * 10) 0
D - Base n
シグネチャを決める。
abc192d :: String -- X
-> Int -- M
-> Int -- 答え
基数が大きいほど、桁ごとの重みが大きくなるので、同じ数字列を解釈した結果が大きくなる。
1つずつ調べていくと、例3のような場合に途方もなくなる。
そこで、二分探索で調べる。下限はdでよい。
上限は、Mをその基数で表記したとき、確実にXの値を下回るような値にする必要がある。
2から開始し、条件を満たすような値になるまで順に倍にして探索して決める。
このとき、$M \leq 10^{18}$ と大きく、Int の上限ギリギリなので、
「とある基数 b で X を解釈した値」を Int で作るとオーバーフローする危険がある。
なので逆に、「とある基数 b で M を表記した列」と X を、列で比較するか、Integer で実装する必要がある。
結果
b進表記の数を、下位桁が前にくる整数リストで表した版：AC, 1ms
下は、Integrerを用いた版：AC, 2ms
import Data.List
import Data.Char
import Data.Tuple
main = do
x <- getLine
m <- readLn
let ans = abc192d x m
print ans
abc192d :: String -> Integer -> Int
abc192d x m
| badnews = 0 -- |X| == 1 も含め、最小のb0でもMを越えるとき、0個
| length x == 1 = 1 -- 基数を何にしても、1桁の数の値は変わらないので、1
| otherwise = be - b0
where
badnews = not $ prop $ succ b0
ds = reverse $ map (fromIntegral . digitToInt) x
b0 = fromIntegral $ maximum ds
bx = fromIntegral $ head $ dropWhile prop $ iterate (2 *) 1
(_, be) = binary_search prop bx b0
prop b = m >= foldr (\d acc -> d + fromIntegral b * acc) 0 ds
binary_search :: (Int -> Bool) -> Int -> Int -> (Int, Int)
binary_search prop unsat sat = loop unsat sat
where
loop a b
| ende = (a, b)
| prop m = loop a m
| True = loop m b
where
ende = a == m || b == m
m = div (a + b) 2
E - Train
シグネチャを決める。横着する。
abc192e :: [Int] -- N,M,X,Y
-> [[Int]] -- Ai,Bi,Ti,Ki
-> Int -- 答え
ダイクストラ法の原理を理解できる内容。
スタート地点から、全ての出辺に対して、辺の長さの時間を掛けて向こうに到着する列車を出発させる。
到着駅が、最速の到着時刻が決定済みならば、列車は到着するだけでおしまい。
初めてその駅に到着したとき、その駅の最速時刻が決まり、その駅発の列車を全て出発させる。
この様子を、時刻順に追跡するシミュレーションのために、時刻をキーにした優先度付きキューを用いる。
この問題では、列車の到着次第次の列車を出す代わりに、$K_i$ による待ち時間を考慮する点が、
素のダイクストラ法と異なる。
結果
時刻判明済みの駅の一覧を、STArray Int Bool 的な表で持つよりも、
IntSet で管理するコードの方が速かったのはなぜだろう。
import qualified Data.IntSet as IS
import Data.Array
import qualified Data.Heap as PQ
abc192e :: [Int] -> [[Int]] -> Int
abc192e [n,_m,x,y] abtks = loop IS.empty (PQ.singleton (0,x))
where
tt = accumArray (flip (:)) [] (1,n) [p | a:b:tk <- abtks, p <- [(a,b:tk),(b,a:tk)]] -- timetable of city a
loop is pq =
case PQ.uncons pq of
Nothing -> -1 -- キューが尽きた
Just ((t, u), pq1)
| IS.member u is -> loop is pq1 -- 目的地からは列車は出発済み
| u == y -> t -- Yに付いたなら答えが出た
| otherwise -> loop (IS.insert u is) pq2
where
pq2 = PQ.union pq1 $ PQ.fromList [(ti + k * divrup t k, b) | b:ti:k:_ <- tt ! u]
divrup x y = negate $ div (negate x) y
F - Potion
シグネチャを決める。
abc192e :: Int -- N
-> Int -- X
-> [Int] -- Ai
-> Int -- 答え
$k$ 個を選んで合計した値が $S$ として、$(X - S) \div k = m \dots 0$ となる最大の $m$ が正常系の要求。
$k = 1$ として $(X - A_1) \div 1 = X - A_1 \dots 0$ なので、$X$ が作れないことはない。
もう一つの経路として、いきなり $X = S$ となるような場合を心配したくなるが、
$X$ が大きくとってあり、$A_i$は抑えてあるので、$N = 100, X = 10^9, A_i = 10^7$ という状況でのみそれが発生する。
$k$ を何か決めて、それについて、$A_i$ から $k$ 個選んだ総和 $S$ で、$X$ と $k$ に対する剰余が等しいような最大の値が知りたい。
そこで、$arr[1 \leq j \leq k-1, 0 \leq r < k]$ を、$A_i$ から $j$ 個選んだ総和 $S$ で、$S \bmod k = r$ なものの最大値、とする。
ただし、0のときは値はないものとする。
$A_i$ について順に、これを足した値について、また$A_i$ 単体について、$arr$ を更新したら、
最終結果の $arr[k, X \bmod k]$ が $S$ である。
結果
import Data.Array.Unboxed
abc192f :: Int -> Int -> [Int] -> Int
abc192f n x as
| specialcase = 0
| otherwise = minimum $ map comp [1 .. n]
where
specialcase = x == sum as -- n=100, x=10^9, as = replicate 100 (10^7)
-- k個の薬を足し合わせる場合の最短のmを探す
comp 1 = x - maximum as -- 最大のやつをxに届くまで放置して+1する回数
comp k = loop k arr0 as
where
-- 足し合わせた個数、mod acc k -> accの最大値 0 のときは不在
arr0 = accumArray (flip const) 0 ((1,0),(k, pred k)) []
loop :: Int -> UArray (Int,Int) Int -> [Int] -> Int
loop k arr []
| ax == 0 = maxBound
| otherwise = div (x - ax) k
where
ax = arr ! (k, mod x k)
loop k arr (a:as) = loop k arr1 as
where
arr1 = accum max arr $
((1, mod a k), a) :
[ ((succ j, qq), aqa)
| ((j,q),aq) <- assocs arr, j < k, aq > 0
, let aqa = aq + a, let qq = mod aqa k
]
一見すると immutable array の更新があるので、相当遅くなりそうに見えるが、実際にはかなり高速に完了した。なんで？