A - Payment
シグネチャを決める。
abc173a :: Int -- N
-> Int -- 答え
1000で割った余りを1000から引いた値、だと、例2のようにNが1000で割り切れるときに間違いになる。
結果
abc173a n =
case mod n 1000 of
0 -> 0
r -> 1000 - r
切り上げ除算で1000円札の必要な枚数を求めてそれで支払ったお釣りとすれば、間違いは起きない。
abc173a n = divrup n 1000 * 1000 - n
divrup a b = div (a + pred b) b
ユーザ解説の「金額の上限1万円だから、万札で払って、釣りの小銭だけ考えたらヨシ」はすごい着想だと思う。
abc173a n = mod (10000 - n) 1000
B - Judge Status Summary
シグネチャを決める。
abc173b :: Int -- N
-> [String] -- Si
-> String -- 答え
1文字目で判別してカウントする。
出力の形式が特殊なので、全て作って返す。
結果
なお、unlinesは最後の改行まで入れるので、結果は putStrLn でなく putStr で出力する。
import Data.Array
abc173b :: Int -> [String] -> String
abc173b _n ss = unlines [unwords [k, "x", show c] | (k,c) <- zip ks $ elems cnt]
where
cnt = accumArray (+) 0 (1,4) [(f s, 1) | s:_ <- ss] :: Array Int Int
f 'A' = 1
f 'W' = 2
f 'T' = 3
f 'R' = 4
ks = ["AC", "WA", "TLE", "RE"]
C - H and V
シグネチャを決める。
abc173c :: Int -- H
-> Int -- W
-> Int -- K
-> [String] -- c_ij
-> Int -- 答え
$H,W \leq 6$ なので、総当たりの場合の数は $2^{12} = 4096$ しかない。
36マスのうち、選ばなかった行、列のマスの黒を数える手間は $4096 \times 36 = 147456$ なので、愚直にやってもらいましょう。
結果
import Data.Array
import Data.Bits
abc173c :: Int ->Int -> Int -> [String] -> Int
abc173c h w k css = length
[ ()
| b <- [0 .. 2^(h + w) - 1] :: [Int]
, k == length [() | ((i,j), True) <- assocs c, testBit b i, testBit b (j + h)]
]
where
c = listArray ((0,0),(pred h, pred w)) [c == '#' | cs <- css, c <- cs]
これだけ制限時間が1secで他より厳しかった。2msなので影響はないけれど。
もっと速く
それぞれの行の様子をビットパターンにしておいて、塗らない行だけ取り出し、
塗る列を0にしたマスクパターン（とは b の下位 W ビット）とANDをとった後で popCount するアプローチが最速か。
abc173c :: Int ->Int -> Int -> [String] -> Int
abc173c h w k css = length
[ ()
| b <- [0 .. 2^(h + w) - 1] :: [Int]
, k == sum [popCount (b .&. x) | (x,i) <- zip bs [w..], testBit b i]
]
where
cs2b cs = sum [b | ('#', b) <- zip cs $ iterate (2 *) 1]
bs = map cs2b css
ms単位だと違いがわからなかった。
もっと遅く
ビット操作の練習、が出題の意図でもあるが、あえてそれを使わずに計算してみる。
import Data.Array
abc173c :: Int ->Int -> Int -> [String] -> Int
abc173c h w k css = length [() | hi <- his, wj <- wjs, count hi wj == k]
where
c = listArray ((1,1),(h,w)) [c == '#' | cs <- css, c <- cs]
his = power [1 .. h] -- 塗らない、つまり数える添え字のリスト、の全ての場合
wjs = power [1 .. w]
count hi wj = length [() | i <- hi, j <- wj, c ! (i,j)]
-- リストの要素を入れるのと入れないので2^lengthの場合を作る
power :: [a] -> [[a]]
power [] = [[]]
power (x:xs) = map (x :) pxs ++ pxs
where
pxs = power xs
これも2msでACしたので、ms単位だと違いがわからなかった。（あれっ？）
D - Chat in a Circle
シグネチャを決める。
abc173d :: Int -- N
-> [Int] -- Ai
-> Int -- 答え
人 $j$ と 人 $k$ の間に人 $i$ が入ると、$\min(A_j, A_k)$ が今回のスコアになり、
以降、人 $i$ の両隣の入り込みスコアはそれぞれ $\min(A_i,A_j), \min(A_i,A_k)$ になる。
どんどん小さくなるので、$A_i$ の大きい順にきて貰うべきなのは確定とする。
シミュレーション解法
隙間を、そこで得られるスコア、すなわち両側のスコアの低い方の値で表す。
次に到着した人が最高スコアの隙間を選んだとき、新たにできる2つの隙間のスコアは、
スコアの高い順に到着すると、既に並んでいる人は今回の人以上のスコアであることが保証されるので、
両側とも自分のスコアとなる。
という状況は、優先度付きキューでシミュレーションできる。
import Data.List
import qualified Data.Heap as PQ
abc173d :: Int -> [Int] -> Int
abc173d _n as = sum cs
where
a1:as1 = sortBy (flip compare) as
(_, cs) = mapAccumL step (PQ.fromList [-a1]) as1
step pq aj = (PQ.insert (-aj) $ PQ.insert (-aj) pq1, - nai)
where
Just (nai, pq1) = PQ.uncons pq
さらによく考えると、新たに追加する隙間のスコアは、既にある輪の中で最小であることも保証されているので、
優先度付きキューでなく、単にキューの末尾に追加するだけでよい。
import Data.List
import qualified Data.Sequence as Q
abc173d :: Int -> [Int] -> Int
abc173d _n as = sum cs
where
a1:as1 = sortBy (flip compare) as
(_, cs) = mapAccumL step (Q.fromList [a1]) as1
step (ai Q.:<| q) aj = (q Q.|> aj Q.|> aj, ai)
もっと早い方法
上の二つめの解で、消費された要素も含めてキューの内容を考えると、
先頭は最大値、それ以降は大きい順に要素がダブって並ぶ。
その列の前から $N-1$ 個の和が答え。
つまり、$N-2$ が偶数のときは、最大値とそれ以外の大きい方から $(N-2)/2$ 個の和、
$N-2$ が奇数のときは、最大値と大きい方から $(N-1)/2$ 個の和と、もう一つ次の値の和になる。
import Data.List
abc173d :: Int -> [Int] -> Int
abc173d n as
| even n2 = a1 + 2 * sum as2
| otherwise = a1 + 2 * sum as2 + a3
where
n2 = n - 2
a1:as1 = sortBy (flip compare) as
(as2,a3:_) = splitAt (div n2 2) as1
E - Multiplication 4
シグネチャを決める。
abc173e :: Int -- N
-> Int -- K
-> [Int] -- Ai
-> Int -- 答え
悩んだ末に after_contest が通せなかった。
調べると、試したアプローチは公式解説の解法2に相当する、「絶対値の大きい方から順に貪欲に選んでいく、ただし、負の数をとると負になってしまうことを避けるために2つセットで取る」で、正の数も2つセットにしていたのがダメだったようだ。
どちらを選ぶかは連続する2数の積を比較するけれど、正の数は2個セットにせずひとつだけ選ぶ、という理屈がわからない。
最後の帳尻合わせの場合の分析もややこしくて、コードはあまり見せられない。
公式解説の解法1「絶対値の大きい方からK個とにかく選んで、負の数が奇数個だったら最後で調整する」アプローチの方がまだ見通しがよいのでそれを写経する。
結果
import Data.List
import Data.Function
import Data.Maybe
import Control.Monad
abc173e :: Int -> Int -> [Int] -> Int
abc173e n k as
| n == k = prodd 1 as -- 工夫の余地なし
-- 以下、as2 /= []
| head ras1 == 0 = 0 -- 0が混入しているなら結果は0
-- 以下、notElem 0 as1
| even $ length $ filter (0 >) as1 = prodd 1 as1 -- 負の数が偶数個なら結果は正
-- 以下、工夫して結果を正にしたい
| isJust case1, isJust case2 -- 両方使えるなら結果の大きい方
= fromJust $ if cond then case1 else case2
| otherwise -- いずれか使える方か
= fromJust $ case1 `mplus` case2 `mplus` noway -- どちらもダメなら敗戦処理
where
(as1, as2) = splitAt k $ sortBy (flip compare `on` abs) as -- 絶対値の降順でソートして、K個取り分ける
ras1 = reverse as1
lastN = fmap negate $ safeHead $ filter (0 >) ras1 -- as1の絶対値最小の負数
lastP = safeHead $ filter (0 <) ras1 -- as1の絶対値最小の正数
fstN = fmap negate $ safeHead $ filter (0 >) as2 -- as2の絶対値最大の負数
fstP = safeHead $ filter (0 <) as2 -- as2の絶対値最大の正数
-- lastNを抜いてfstPを追加、ができるときその結果
case1 = (\fstP lastN -> prodd fstP $ delete (negate lastN) as1) <$> fstP <*> lastN
-- lastPを抜いてfstNを追加、ができるときその結果
case2 = (\fstN lastP -> prodd (negate fstN) $ delete lastP as1) <$> fstN <*> lastP
-- case1,case2ともに有効なとき、case1を選択するべきか
cond = fromJust fstP * fromJust lastP >= fromJust fstN * fromJust lastN
noway = Just $ prodd 1 $ take k $ sortBy (flip compare) as -- Aiは負ばかり
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
modBase :: Int
modBase = 10^9 + 7
reg :: Int -> Int
reg x = mod x modBase
mul :: Int -> Int -> Int
mul x y = reg $ x * y
prodd :: Int -> [Int] -> Int
prodd = foldl' mul
F - Intervals on Tree
シグネチャを決める。横着する。
abc173f :: Int -- N
-> [[Int]] -- u_i, v_i
-> Int -- 答え
$u_i < v_i$ と仮定する。
グラフ全体は木なので、連結にするのに無駄な辺はひとつもない。（ループでの回り込みは起きない。）
ある範囲 $L,R$ を考えるとき、関わる辺は $L \leq u_i, v_i \leq R$ な辺 $i$ のみ。
これらの辺だけで、$R - L + 1$ 頂点のグラフがいくつ連結になるか Union-Find で数えようとすると、常に有効な辺になる。つまり、使った辺の本数だけ連結成分の個数は減る。
これをそのまま数えようとしても、$N^2$ の手間がかかる。
全ての $1 \leq L \leq R \leq N$ の場合について、上の値の総和をとることが目標。
$L,R$に入っている辺を $E(L,R) = \{ (u_i, v_i) \ |\ L \leq u_i, v_i \leq R \}$ として、次のように表せる。
\sum_{L=1}^N \sum_{R=L}^N \Big ( (R - L + 1) - \big | E(L,R) \big | \Big )
計算すると、前半は（これchatGPTに聞いたら嘘つかれた…maximaとか使うべきだった）
\sum_{L=1}^N \sum_{R=L}^N \big (R - L + 1 \big ) = N(N+1)(N+2)/6
後半は、$L,R$ からでなく辺 $u_i,v_i$ からに視点を移して、
ひとつの辺 $(u_i, v_i)$ を含む $(L,R)$ の個数を $C(i)$ とすると
\begin{split}
& \sum_{L=1}^N \sum_{R=L}^N \big | E(L,R) \big | = \sum_{i=1}^{N-1} C(i) \\
& C(i) = (u_i以下なLの個数) * (v_i以上なRの個数) = u_i * (N+1-v_i)
\end{split}
結果
abc173f :: Int -> [[Int]] -> Int
abc173f n uvs = div (n * (n+1) * (n+2)) 6 - sum [min u v * (succ n - max u v) | u:v:_ <- uvs]
最終問題の答えがワンライナーになってしまった。