ABC382の振り返りです。
結果
A,Bの2完でした。くやしい、、
解説
A問題
- 問題
- 回答
@がどこにあるかを調べるひつようもないです。.の数をカウントしてdを足せばよいです。
main :: IO ()
main = do
[n, d] <- getInts
s <- getLine
let cnt = length $ filter (== '.') s
print $ cnt + d
main :: IO ()
main = do
[n, c] <- getInts
ts <- getInts
print $ fst $ foldl' (\acc@(cnt, curr) t -> if t - curr < c then acc else (cnt + 1, t)) (1, head ts) (tail ts)
B問題
- 問題
- 回答
reverseして再帰で@を.に置き換えればよいです。
main :: IO ()
main = do
[n, d] <- getInts
s <- getLine
let s' = solve (reverse s) d
putStrLn $ take (n - length s') s ++ s'
solve :: (Eq t, Num t, Enum t) => [Char] -> t -> [Char]
solve s d = f s [] d
where
f s ans 0 = ans
f (sh : st) ans d
| sh == '@' = f st ('.' : ans) (pred d)
| sh == '.' = f st ('.' : ans) d
C問題
- 問題
- 回答(upsolved)
最初、これは「おいしさBiの食事に対して、美食度を超えない最大のAiを探せばいい」と考え、これは二分探索だなと思いました。
これを実装すると以下のようになります。
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- getInts
let im = IM.fromList as
ans = [snd $ fromJust $ IM.lookupLE b im | b <- bs]
mapM_ print ans
しかし、これを動かすと3つ目のサンプルケースが通りません。
入力値を
10 5
60 83 76 45 70 91 37 58 94 22
70 39 52 33 18
とすると、出力値は
1
7
4
10
-1
となって欲しいのですが
5
7
4
10
-1
となってしまいます。
なぜこうなるのでしょうか？
それは問題の前提条件
それぞれの人は、美味しさが自分の美食度以上である寿司が自分の前に流れてきたときはその寿司を取って食べ、それ以外のときは何もしません。
を考慮しきれていなかったことが原因です。
この条件について考えてみましょう。前の人が先にお寿司を食べてしまうので
i < i'として、Ai <= Ai' だとするとAi'の人はお寿司を食べられない
ということになります。（なんとも理不尽です）
例えば、お寿司を食べようとしている人が3人で、
A1 = 70, A2 = 60, A3 = 90
だったとします。
この状況でおいしさが70以上のお寿司が出てくると、A1の人が食べてしまうので、A2, A3はお寿司を食べることができません。
お寿司のおいしさが60 <= Bi < 70であれば、A2の人はお寿司を食べられますが、A3の人が食べられないのは同様です。
つまり、A1 <= A3の時点で、A3の人はお寿司を食べることができないのです。
これを踏まえて、Aiのリストを修正する必要があります。
修正方針としては、
i < i' として、Ai < Ai'となるAi'を全て削除する
ということになります。
これを実装すると
f [] _ _ _ = [(0, -1)]
f (ah : at) (c, d) n m
| ah < c = (ah, m) : f at (ah, m) n (m + 1)
| otherwise = f at (c, d) n (m + 1)
となり、これだとACします。
全体のコードは以下の通りです。
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- getInts
let im = IM.fromList $ f as (2 * 10 ^ 5 + 10, 0) n 1
ans = [snd $ fromJust $ IM.lookupLE b im | b <- bs]
mapM_ print ans
f [] _ _ _ = [(0, -1)]
f (ah : at) (c, d) n m
| ah < c = (ah, m) : f at (ah, m) n (m + 1)
| otherwise = f at (c, d) n (m + 1)
全体を振り返って
前提条件を踏まえて考えると解けるのですが、そこに気づくのがなかなか難しい、、
まだまだ精進です。