A - Task Scheduling Problem
シグネチャを決める。横着する。
abc103a :: [Int] -- A1,A2,A3
-> Int -- 答え
考える
6とおりの全ての順序について、コストを計算してみる。
abc103a [a1,a2,a3] = minimum
[ d12 + d23 -- 1,2,3
, d31 + d12 -- 1,3,2
, d12 + d31 -- 2,1,3
, d23 + d31 -- 2,3,1
, d31 + d12 -- 3,1,2
, d23 + d12 -- 3,2,1
]
where
d12 = abs (a1 - a2)
d23 = abs (a2 - a3)
d31 = abs (a3 - a1)
重複している要素がある。それを消すと
abc103a [a1,a2,a3] = minimum
[ d12 + d23
, d31 + d12
, d23 + d31
]
where
...
d12, d23, d31 の3つのうち2つを足したものの最小値、とは、3つともの和から最大値を除いたものを計算している。
abc103a as = sum ds - maximum ds
where
ds = map abs $ zipWith (-) as (last as : as)
さらに考える
数直線で考えると、$|A_j - A_i|$ とは、その2点間の距離。
つまり、$A_1$ から $A_2$ を経由して $A_3$ まで到達する道のりが求める値。
$B_1 < B_2 < B_3$ と仮定する。$B_1 + D = B_2, B_2 + E = B_3$ とおく。
出発点を間の $B_2$ にすると、$B_1$ へ先に行き $D + D + E$ または $_3$ へ先に行き $E + E + D$ となる。必ず折り返しが起きる。
出発点を端の $B_1$ にすると、$B_2, B_3$ と順に辿ると折り返すことなく $D + E$ で済む。
逆の端 $B_3$ から出発しても同様に $D + E$ になる。
$D + E$ = $B_3 - B_1$ で、結局、最大値と最小値の差が必要な値。
abc103a as = maximum as - minimum as
A問題でこんなに考えるはめになるとは。
問題文
書きぶりがおかしい。
コストの説明
$i$ 番目のタスクを完了した直後にコスト $|A_j - A_i|$ で $j$ 番目のタスクを完了できます。
に対して、与えられる入力の $A_1, A_2, A_3$ が変数そのままでは意味が通じない。
入力は3つのタスクのコストパラメータ $B_1, B_2, B_3$ で、
実施順の添字を付けた $A_1, A_2, A_3$ は $B$ の順列である、と言わないと。
B - String Rotation
シグネチャを決める。
abc103b :: String -- S
-> String -- T
-> Bool -- 答え
簡単に
たかだか100文字なので、総当たりで試せばよい。
import Data.List
abc103b s t = elem t $ map (take len) $ take len $ tails $ s ++ s
where
len = length s
偏執狂的に
take はリストのコピーを作るために遅い。一方、drop は参照を読むだけなので速い。
回りくどいが、リスト xs の前から i 要素除いた残りが、リスト ys の前方に一致するかを判定する述語を考える。
import Data.List
check xs ys i = drop i xs `isPrefixOf` ys
s を k 文字回転させたものが t と一致するとき、(a,b) = splitAt k s として b ++ a == t である。
(++) を無くして考えると、n = length s として (c,d) = splitAt (n-k) t として a == d && b == c である。
a == d は check t s (n-k) と同値で、b == c は check s t k と同値である。
abc103b s t = or [check s t k && check t s (n-k) | k <- [0 .. pred n]]
where
n = length s
ByteStringで
ByteString の take は参照を操作するだけなのでリストのそれのように重くはないので、
上の a == d && b == c を直接定義できる。
abc103b :: BS.ByteString -> BS.ByteString -> Bool
abc103b s t = or [a == d && b == c | k <- [0 .. pred n], let (a,b) = BS.splitAt k s, let (c,d) = BS.splitAt (n-k) t]
where
n = BS.length s
abc103b s t = or [BS.isPrefixOf b t && BS.isSuffixOf a t | k <- [0 .. pred n], let (a,b) = BS.splitAt k s]
C - Modulo Summation
シグネチャを決める。
abc103c :: Int -- N
-> [Int] -- ai
-> Int -- 答え
$a_i$ の最小公倍数を $L$ とする。
つまりどの $a_i$ についても整数 $b_i$ で $a_i \cdot b_i = L$ となるものが存在し、つまり $(L - 1) \bmod a_i = a_i - 1$ となる。これはそれぞれの項で望める最大の値である。
これの和は $\sum (a_i - 1) = \sum a_i - N$ である。
abc103c n as = sum as - n
LCMの真値は巨大になるので直接求めてはいけない。
解説を見たら、LCMでなくても $\prod a_i$ で十分とあった。そらそうだ。
D - Islands War
シグネチャを決める。横着する。
abc103d :: Int -- N
-> Int -- M
-> [[Int]] -- ai,bi
-> Int -- 答え
考える
なるべく橋を落とさずに済ませるには、ぎりぎりまで貯め込んでやればよいだろう。
端の島 $k = 1$ から順に調べていき、$a_i = k$ な要望がある島に到達したとき、$b_i$ までに落とす必要があるとして記録する。
記録した限界の最小値だけ追跡して、いよいよとなったときに橋を落とす。
すると、それよりも遠くでよかった全ての要望も満たされるので、記録がない状態に戻る。
橋を落とした回数を数えれば終わり。
import Data.Array.Unboxed
import Data.List
abc103d :: Int -> Int -> [[Int]] -> Int
abc103d n _m pqs = sum $ snd $ maAccumL step maxBound $ assocs arr
where
arr :: UArray Int Int
arr = accumArray min maxBound (1,n) [(p,q) | p:q:_ <- pqs]
step lim (a, b)
| lim == a = (b, 1)
| otherwise = (min lim b, 0)
これはバケツソートも込みで $O(M+N)$ の解。
公式解説のやり方
$b_i$ の小さい順に考える。（このときソートに $O(M \log M)$ かけている。）
最後に落とした橋の位置を覚えておく。
満たされていない要望がきたとき、なるべく東の端で落とす（これは上と同じ）ことで、それ以降の要望を満たしやすくする。
結局落とす橋は同じになるが、初見の要望を叶えてしまい、ここまではもう達成済み、とするか、注目点が限界を通過しようとした瞬間に落とすか、落とすタイミングが違う感じ。
この方法のまま $O(N)$ にするには、$b_i$ についてバケツソートするために、$a_i$ の最大値を記録するようにして、落とし済みの橋の初期値を1とかにしておく感じかしら。
abc103d :: Int -> Int -> [[Int]] -> Int
abc103d n _m pqs = sum $ snd $ mapAccumL step 1 $ assocs arr
where
arr :: UArray Int Int
arr = accumArray max 0 (1,n) [(q,p) | p:q:_ <- pqs]
step x (b,a)
| a < x = (x, 0)
| otherwise = (b, 1)