AtCoder Beginner Contest 400に参加したので振り返り。
ABの2完。どんどん解けなくなってるぞ。
A - ABC400 Party
\(400\) を \(A\) で割るだけ・・・なのだけど、読み間違えて \(A\) が素数か否か、という問題を解こうとしてしまってた。 焦ってはいけないね。
main :: IO ()
main = do
n <- readLn @Int
print $ if 400 `mod` n == 0 then 400 `div` n else -1 B - Sum of Geometric Series
式 \[ X = \sum_{i=0}^M N^i \]
の通りに \(i=0\) から順繰りに足していくだけ。
main :: IO ()
main = do
[n,m] <- list1 ucInt
putStrLn $ solve n m
solve :: Int -> Int -> String
solve n m = go 0 0
where go i acc
| acc > 10^9 = "inf"
| i > m = show acc
| otherwise = go (i+1) (acc + n^i) これも dropWhile や scanl を使って書けそう。
C - 2^a b^2
本番中は解法思いつかず、15分ほど考えてD問題に行った。
\[\begin{eqnarray} &&X = 2^a \times b^2 \\ &\Leftrightarrow & b^2 = \frac{X}{2^a} \\ &\Leftrightarrow & b = \sqrt{\frac{X}{2^a}} \end{eqnarray} \]なので、 \(2^a \le N\) なる \(a\) それぞれについて、 \(b\) の最大値 \(b_{max}(a)=\lfloor\sqrt{N/{2^a}}\rfloor\) を求める。 各 \(a\) について、 \(1 \le b \le b_{max}(a)\) なる \((a,b)\) の組み合わせは良い整数を構成するが、ここで \(b\) が偶数（ \(=2b'\) ）のとき、
\[\begin{equation} X = 2^a \times b^2 = 2^a \times (2b')^2 = 2^{a+2} \times {b'}^2 \end{equation} \]となるので、奇数である \(b\) の個数のみ数えれば良い。
実装は以下の通り。
main :: IO ()
main = do
n <- readLn @Integer
let as = takeWhile (\x -> 2^x <= n) [1..]
bs = map (isqrt . \a -> n `div` 2^a) as
bs' = map (\b -> (b + 1) `div` 2) bs
print $ sum bs'
isqrt :: Integral a => a -> a
isqrt x = bsearch (\i -> i^2 <= x) 0 (x+1) 平方根の整数部分を求める関数 isqrt は、二分探索で実装している。この方法の場合、 Int ではオーバーフローしてしまうので、 Integer を使用している。
もともと、 isqrt の実装は以下のようにしていた。
isqrt :: Integral a => a -> a
isqrt x = if c1^2 <= x && x < c2^2 then c1 else c2
where c0 = sqrt (fromIntegral x)
c1 = floor c0
c2 = ceiling c0 この実装だと、 isqrt (10^18-1) の結果が 1000000000 となってしまう（正しくは 999999999 ）。
これは、 fromIntegral で Int を Double に変換したときに、 Double の精度が足らず情報が落ちてしまったものと思われる
（実際、 fromIntegral @Integer @Double $ 10^18 - 1 は 1.0e18 と評価される）。
他の人の提出1を見てみると、Newton法で実装しているものもあった。 今後はこちらを使うのが良いかな2。
D - Takahashi the Wall Breaker
問題文や例を眺めつつ、これは01-BFS3で解くんだろうなーと当たりはついた。が、01-BFSを実装するのは初めてで結構苦戦した。 結局サンプルが通らず、時間内に提出できなかった。
01-BFSの自体の実装はこんな感じ（ Sq は Data.Sequence ）。
-- | 01-BFS
bfs01 :: forall a m i. (MArray a Int m, Ix i, Show i) =>
(i -> [i]) -> -- ^ 現在点からのコストが0の探索候補点を取得
(i -> [i]) -> -- ^ 現在点からのコストが1の探索候補点を取得
(i, i) -> -- ^ 探索範囲のbound
[i] -> -- ^ 開始点
m (a i Int)
bfs01 next0 next1 b start = do
-- 開始点からのコストを格納するarrayを作成（maxBoundは訪れていないことを表す）
cost <- newArray b maxBound
-- 開始点にコスト0を設定
forM_ start $ \s -> writeArray cost s 0
-- 探索実施
go cost (Sq.fromList start)
-- 開始点からのコストを返却
return cost
where
go :: a i Int -> Sq.Seq i -> m ()
go dist queue = case Sq.viewl queue of
-- 両端キューが空であれば終了
Sq.EmptyL -> return ()
-- 両端キューの左から次の探索点を取り出す
v Sq.:< rest -> do
-- 開始点から探索点までのコストを取得
d <- readArray dist v
-- コストが0の探索候補点を取得
cand0 <- filterM (fmap (>d) . readArray dist) . next0 $ v
-- コスト1の探索候補点を取得
cand1 <- filterM (fmap (>d+1) . readArray dist) . next1 $ v
-- コストを更新
forM_ cand0 $ \cand -> writeArray dist cand d
forM_ cand1 $ \cand -> writeArray dist cand (d+1)
-- コスト0の探索候補点を両端キューの左、コスト1の探索候補点を両端キューの右に追加し、次の探索へ
go dist $ Sq.fromList cand0 Sq.>< rest Sq.>< Sq.fromList cand1BFSとはいうものの、最短距離ではなくコストを更新しているので、Dijkstra法に近いことをしているのかな。
今回、「前蹴り」で壁の区画を道の区画に変更できる。このコストを1とすれば、探索候補点を取得する関数は以下。
next0 :: Ix i => i -> [i]
next0 = filter (\v -> grid ! v /= '#') . arounds bound nei1
next1 :: Ix i => i -> [i]
next1 = filter (\v -> grid ! v == '#') . arounds bound nei2
-- | 範囲外の点は除外して、ある点に隣接する点を列挙する。
arounds :: Ix i => (i, i) -> (i -> [i]) -> i -> [i]
arounds bound neighbours = filter (bound`inRange`) . neighbours
-- | (i, j) から上下左右4つの位置を列挙する
nei1 :: (Ix i, Num i) => (i, i) -> [(i, i)]
nei1 (i, j) = [bimap (i+) (j+) (p,q) | p <- [-1,0,1], q <- [-1,0,1], p==0||q==0, (p,q) /= (0,0)]
-- | (i, j) から上下左右毎に2個先までの位置を列挙する
nei2 :: (Ix i, Num i, Enum i) => (i, i) -> [(i, i)]
nei2 (i, j) = [bimap (i+) (j+) (p,q) | p <- [-2..2], q <- [-2..2], p==0||q==0, (p,q) /= (0,0) ]当初、コスト1の探索候補点を取得する処理を、「壁の向こうの道を探す」と考えて、距離が2か3のマンハッタン距離にある点で、道であるようなものを求めるよう実装していた。
next1 = filter (\v -> grid ! v /= '#') . arounds bound nei2
nei2 (i, j) = [bimap (i+) (j+) (p,q) | p <- [-3..3], q <- [-3..3], abs p + abs q `elem` [2,3]]これだと、Sampleは通るが、Allは通らない。 壁が3つ以上連続している場合に、それ以上探索できなくなってしまうため。
実際、通る場合と通らない場合で、探索後の cost 配列を出力すると以下のようになっている。
サンプル問題4の入力
#################### ##...##....###...### #.....#.....#.....## #..#..#..#..#..#..## #..#..#....##..##### #.....#.....#..##### #.....#..#..#..#..## #..#..#.....#.....## #..#..#....###...### #################### #################### ##..#..##...###...## ##..#..#.....#.....# ##..#..#..#..#..#..# ##..#..#..#..#..#..# ##.....#..#..#..#..# ###....#..#..#..#..# #####..#.....#.....# #####..##...###...## ####################正しい回答の
cost配列21111122222233333344 11000111111223222334 10000011111122222233 10010011121122232233 10010011111222233344 10000011111122233344 10000011121122232233 10010011111122222233 10010011111223222334 21121122222233333344 21121122222334333445 22112112222233433344 22112112222223333334 22112112223223334334 22112112223223334334 22111112223223334334 32211112223223334334 33222112222223333334 43322112222233433344 44333223333334444445誤った回答の
cost配列（探索していない区画は.と表示）.................... ..000..1111...222... .00000.11111.22222.. .00.00.11.11.22.22.. .00.00.1111..22..... .00000.11111.22..... .00000.11.11.22.22.. .00.00.11111.22222.. .00.00.1111...222... .................... .................... ..11.11..222...333.. ..11.11.22222.33333. ..11.11.22.22.33.33. ..11.11.22.22.33.33. ..11111.22.22.33.33. ...1111.22.22.33.33. .....11.22222.33333. .....11..222...333.. ....................
感想
今日はコンテスト中にちょこちょこ中断（30分くらいかな）が入って、なかなか集中して取り組めなかった・・・ とはいえ、（解答は見たものの）よく考えればできたなーという問題だったので、やはり実力不足。 （D問題も、解いてみればド典型といった問題で、探索候補点をもう少し考察できていれば時間内に解けてたという感触）
また Double の精度不足でWAとなったものについて、結構気軽に fromIntegral や ceiling 、 floor 等々で整数と浮動小数点数の変換をしてたのは反省。
できるだけ整数のまま計算を進めるようにしたい。
探索問題については、DFSやBFSといった実装は用意しているが、いざ使おうとするとまごついてしまう。 さらっと実装できるくらいにしておきたい。。。
https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division↩︎
https://betrue12.hateblo.jp/entry/2018/12/08/000020 こちらのブログの01-BFS（及び幅優先探索、Dijkstra法）の説明はわかりやすかった。↩︎