AtCoder469振り返りです。
今週は前回に続いて連続して参加しました

結果

AB2完でした。やらかしたー

ふりかえり

A問題

問題文通りにとくだけです

main :: IO ()
main = do
  [n, k] <- getInts
  print $ n - k + 1

B問題

これも問題文通りに解くだけです。
パターンマッチの便利さに頼って再帰で頑張りました

solve :: String -> Int
solve s
  | s == "x" = 1
  | s == "o" = 0
  | take 2 s == "xx" = go 1 s
  | take 2 s /= "xx" = go 0 s
  | otherwise = error $ "invalid input s: " <> s
  where
    go cnt ['x', 'x'] = cnt + 1
    go cnt [_, _] = cnt
    go cnt ('x' : lst@('x' : 'x' : _)) = go (cnt + 1) lst
    go cnt (_ : st) = go cnt st
    go _ s = error $ "invalid pattern s: " <> s

-- Main
main :: IO ()
main = do
  _ <- readLn @Int
  s <- getLine
  print $ solve s

ちなみに、先頭と末尾にxを追加してzipWith3を使うともっとシンプルに解けます。

-- >>> solve "xxoxxxox"
-- >>> solve "ooooo"
-- >>> solve "x"
-- 2
-- 0
-- 1
solve :: String -> Int
solve s = length $ filter id $ zipWith3 (\c1 c2 c3 -> all (== 'x') [c1, c2, c3]) s' (drop 1 s') (drop 2 s')
  where
    s' = ('x' : s) <> "x"

-- Main
main :: IO ()
main = do
  _ <- readLn @Int
  s <- getLine
  print $ solve s

C問題

問題
- https://atcoder.jp/contests/abc469/tasks/abc469_c
回答(upsolved)
- https://atcoder.jp/contests/abc469/submissions/78056175

問題文に書いてある通りにシミュレーションしたところ、TLEになってしまいました。
1≤N≤8×10^5の制約であること、この解法だと計算量がO(N^2)であることから、最悪6.4 x 10 ^ 11オーダーの計算量になってしまうためTLEになってしまいます。

TLE解法

solve :: String -> Int -> Int
solve s k = if cnt0 > 0 then go (k, cnt0 - 1) sr else k
  where
    (sl, sr) = splitAt k s
    cnt0 = length [() | c <- sl, c == 'o']
    go (score, _) [] = score
    go (score, rem) ('o' : st) = go (score + 1, rem) st
    go (score, rem) ('x' : st)
      | rem <= 0 = score + 1
      | rem > 0 = go (score + 1, rem - 1) st

-- Main
main :: IO ()
main = do
  n <- readLn @Int
  s <- getLine
  mapM_ (print . solve s) [1 .. n]

では制限時間内で解くためにはどうすればよいのでしょうか

解説にはこのように書かれています

S に含まれる x の個数が k 個未満ならばすべての袋を受け取ることができ、k 個以上ならば k 番目の「はずれ」の袋まで受け取ることができます。

思ったより解法の考え方は簡単そうです。より納得できるよう、具体例で考えてみましょう。

oxoxoでk=2の場合を考えてみます。
問題文通りにシミュレーションすると、

最初に持っている袋: ox
oを持っていることから次の袋を受け取れます。oを捨てて次の袋を取ります。

1つ目の操作後に持っている袋: xo
oを持っていることから次の袋を受け取れます。oを捨てて次の袋を取ります。

2つ目の操作後に持っている袋: xx
全ての袋がxになっているため、ここで操作を中断します。

このとき、取った袋は4つです。そして、k=2個目の袋に該当します。
解説通りになってますね。

この具体例をもとに考察すると、次のことが言えそうです。

操作の途中にoが出てくる -> oを捨てて次の袋を取る。つまり手持ちの袋に増減はなく次の操作に進む。そのため途中に出てくるoは気にしなくてよい
操作の途中にxが出てくる -> 持っているoを捨ててxを加える。つまり持っている袋にxを加える。これがk個になればそれ以上操作ができなくなる

=> xがk個出てくるまで袋を取ることができる。

これは以下のように言い換えることができます。

xがk個出てきた時のindex(k個出るまでに取った袋の数)が答え

ここまでくれば実装に起こせそうです。実装は以下のようになります。

最初にzip [1..]を使ってindexを付与しておき、xでfilterしつつ出現回数をkey, 出現回数を満たしたindexをvalueとしてIntMapを作りました。

-- >>> solve 5 "oxoxo"
-- >>> solve 3 "ooo"
-- >>> solve 1 "x"
-- >>> solve 5 "xxxoo"
-- >>> solve 5 "oooxo"
-- [2,4,5,5,5]
-- [3,3,3]
-- [1]
-- [1,2,3,5,5]
-- [4,5,5,5,5]
solve :: Int -> String -> [Int]
solve n s = map f [1 .. n]
  where
    im = IM.fromList $ tail $ scanl' (\(cnt, _) (idx, _) -> (cnt + 1, idx)) (0, 0) $ filter (\(_, c) -> c == 'x') (zip [1 ..] s)
    f k = fromMaybe n (IM.lookup k im)

-- Main
main :: IO ()
main = do
  n <- readLn @Int
  s <- getLine
  mapM_ print (solve n s)

解法の考え方そのものがわかればシンプルですが、そこに辿り着くのが難しい問題だったように思います。

(補足)array関数について

最初この問題をarray関数を使って解こうとしたのですが、いくつか罠があったので補足です。

arrayを使って以下のように実装していたのですが、この場合エラーが発生してしまいます。
!?を使ってMaybeを返すようにしてもダメです。

Array版

-- >>> solve 5 "oxoxo"
-- >>> solve 3 "ooo"
-- >>> solve 1 "x"
-- >>> solve 5 "xxxoo"
-- >>> solve 5 "oooxo"
-- (Array.!): undefined array element
-- (Array.!): undefined array element
-- [1]
-- (Array.!): undefined array element
-- (Array.!): undefined array element
solve :: Int -> String -> [Int]
solve n s = map f [1 .. n]
  where
    arr = array @Array (1, n) $ tail $ scanl' (\(cnt, _) (idx, _) -> (cnt + 1, idx)) (0, 0) $ filter (\(_, c) -> c == 'x') (zip [1 ..] s)
    f k = fromMaybe n (arr IA.!? k)

UArray版だとこうなります。どうも初期値0が入っていて、indexアクセスに失敗したときはこの値を返すようです。

-- >>> solve 5 "oxoxo"
-- >>> solve 3 "ooo"
-- >>> solve 1 "x"
-- >>> solve 5 "xxxoo"
-- >>> solve 5 "oooxo"
-- [2,4,0,0,0]
-- [0,0,0]
-- [1]
-- [1,2,3,0,0]
-- [4,0,0,0,0]
solve :: Int -> String -> [Int]
solve n s = map f [1 .. n]
  where
    arr = array @UArray (1, n) $ tail $ scanl' (\(cnt, _) (idx, _) -> (cnt + 1, idx)) (0, 0) $ filter (\(_, c) -> c == 'x') (zip [1 ..] s)
    f k = fromMaybe n (arr IA.!? k)

array関数は引数としてbounds (i,i)とindexとvalueのタプルのリスト[(i, e)]を受け取るのですが、このリストに指定していない値については以下のようになってしまうようです。

Arrayの場合 -> エラー
UArrayの場合 -> eの型に応じた初期値(Intの場合は0)

!?でmaybeを返すようにしても、この関数は範囲チェックしかしないので初期化されていないindexについてはどうもエラーを発生させてしまう挙動になっているようでした。
https://hackage.haskell.org/package/array-0.5.8.0/docs/src/Data.Array.Base.html#%21%3F

arrayでArrayを作っても、indexアクセスが部分関数になってしまうと扱いづらいので、array関数を使うのは避けた方がよさそうです。

自分はこの対処としてIntMapを使ったのですが、accumArrayを使って回避する方法がありそうでした(とーらすさんありがとうございます！)

これは以下のようにaccumArrayでflip constを使うことで、初期化した値をそのまま置き換えていく実装になります。

let = accumArray @UArray (flip const) n (1, n) [(i, e) | 色々操作]

これを使うことで、初期値を実装者側で決めつつindexとvalueのタプルリストから安全にArrayを作ることができます。

今回indexアクセスに失敗したらnを返したいので、初期値はnとします。
(xの個数がkとなることがありえない場合は全て取得する、つまりnを返したい)

この場合は実装はこうなります。

-- >>> solve 5 "oxoxo"
-- >>> solve 3 "ooo"
-- >>> solve 1 "x"
-- >>> solve 5 "xxxoo"
-- >>> solve 5 "oooxo"
-- [2,4,5,5,5]
-- [3,3,3]
-- [1]
-- [1,2,3,5,5]
-- [4,5,5,5,5]
solve :: Int -> String -> [Int]
solve n s = map (arr !) [1 .. n]
  where
    arr = accumArray @UArray (flip const) n (1, n) $ tail $ scanl' (\(cnt, _) (idx, _) -> (cnt + 1, idx)) (0, 0) $ filter (\(_, c) -> c == 'x') (zip [1 ..] s)

-- Main
main :: IO ()
main = do
  n <- readLn @Int
  s <- getLine
  mapM_ print (solve n s)

無事ACしました。
https://atcoder.jp/contests/abc469/submissions/78066056

全体を振り返って

今回のC問題は解法に気づくことができず最後まで解くことができませんでした。
解法が簡単なので、気づけば解けたのにー！という気持ちになってしまいますが、原因を「気づけたら」に求めてしまうと再現性がなく同じ失敗を繰り返してしまいそうです。

正直こういう問題を確実に解けるためにどうすればいいかわからないですが、時間をかけて丁寧に考察することで思考の精度を高めて筋の良い解法を探していくしかなさそうな気がしています。

なかなか伸びませんが、引き続き泥臭くやるしかなさそうです。
時間がなく睡眠時間を削りながらになってしまっていますが、引き続き頑張りますー！