AtCoder Beginner Contest 376 振り返り

ABC376の振り返りです。

結果

A,B,Cの3完でした。

解説

A問題

• 問題
  • https://atcoder.jp/contests/abc376/tasks/abc376_a
• 回答
  • https://atcoder.jp/contests/abc376/submissions/58943441

foldを使って解きました。
T1を初期値として、次の要素との差分Ti - 現在のTを計算します。
差分がC未満の場合は、カウントと現在のT両方を更新せず次に進み、C以上ならカウントを増やして現在のTも更新します。

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問題

• 問題
  • https://atcoder.jp/contests/abc376/tasks/abc376_b
• 回答
  • https://atcoder.jp/contests/abc376/submissions/58967202

問題そのものは難しくないですが、条件の整理が面倒でした。
動かすのが左手か右手かは置いておいて、まず問題文から移動のパターンを整理します。

現在地点をc, 移動先をtとすると以下の様に条件を書き下せます。

• 右回転の場合
  • 移動先がNを跨がない場合
    • 移動途中に動かさない手が存在する場合 -> 移動できない(maxBoundとでもしておく)
    • 存在しない場合 -> 移動距離を t - c とする
  • 移動先がNを跨ぐ場合
    • 移動途中に動かさない手が存在する場合 -> 移動できない(maxBoundとでもしておく)
    • 存在しない場合 -> 移動距離を t + (N - c) とする
• 左回転の場合
  • 移動先がNを跨がない場合
    • 移動途中に動かさない手が存在する場合 -> 移動できない(maxBoundとでもしておく)
    • 存在しない場合 -> 移動距離を c - t とする
  • 移動先がNを跨ぐ場合
    • 移動途中に動かさない手が存在する場合 -> 移動できない(maxBoundとでもしておく)
    • 存在しない場合 -> 移動距離を c + (N - t) とする

上記のパターンで、左回転、右回転の移動距離を計算して短い方を回答としました。

ちなみに、移動距離の途中に動かさない手があるかどうかは、動かす手の現在位置と動かさない手の移動距離を求めて

現在地点からターゲットまでの移動距離 >= 現在地点から動かない手までの移動距離

である場合は移動不可能であると判定しました。

main :: IO ()
main = do
  [n, q] <- getInts
  hts <- replicateM q do
    [h, t] <- readWords
    return (h, read @Int t)

  let ans =
        foldl'
          ( \((l, r), cnt) (h, t) ->
              case h of
                "L" -> let d = dist r l l t n in ((t, r), cnt + d)
                "R" -> let d = dist l r r t n in ((l, t), cnt + d)
          )
          ((1, 2), 0)
          hts

  print $ snd ans

dist r l c t n =
  let rlr = if (r - l) > 0 then r - l else r + (n - l)
      rll = if (l - r) > 0 then l - r else l + (n - r)
      tcr = if (t - c) >= 0 then t - c else t + (n - c)
      tcl = if (c - t) >= 0 then c - t else c + (n - t)
      tcr' = if tcr > rlr then maxBound else tcr
      tcl' = if tcl > rll then maxBound else tcl
   in min tcr' tcl'

条件の洗い出しが面倒で解くのに時間がかかりましたが、もっとシンプルな解き方があるかもしれません。

• 左回転は現在地点と目標地点を入れ替えて右回転しただけとも捉えられるので、余計なコードを減らせそう
• 左回転と右回転のどちらかに必ず途中に動かない手があるからそれで条件分岐するといいかも

とか

C問題

• 問題
  • https://atcoder.jp/contests/abc376/tasks/abc376_c
• 回答
  • https://atcoder.jp/contests/abc376/submissions/58980308

条件の洗い出しが面倒だったBより簡単な印象でした。
おもちゃと箱をそれぞれ降順ソートし、比較しつつ再帰していきます。

比較する時の条件を整理すると以下の様になります。

• 今見ている箱の大きさ >= おもちゃの大きいとなっている場合
  • 箱とおもちゃどちらも次の要素に進める
• 今見ている箱の大きさ < おもちゃの大きいとなっている場合
  • おもちゃの大きさを回答にし、箱はそのままでおもちゃだけ次に進める

この条件で再帰を行い、最後に

• おもちゃが残った場合は残ったおもちゃの大きさを回答にする
• 箱がのこってしまった場合は回答なし(-1を回答にする)

としました。

main = do
  _ <- readLn @Int
  as <- sortOn Down <$> getInts
  bs <- sortOn Down <$> getInts

  print $ solve as bs []

solve :: (Ord t, Num t) => [t] -> [t] -> [t] -> t
solve [] [] cnt = head cnt
solve [] b _ = -1
solve [a] [] _ = a
solve (ha : ta) b@(hb : tb) cnt =
  if hb >= ha
    then solve ta tb cnt
    else solve ta b (ha : cnt)
solve _ _ _ = error "Invalid Pattern"

(ちなみに、回答をリストに詰めてるのはデバッグのためですが、結局使いませんでした。)

全体を振り返って

今回は問題を見て解き方がスムーズに思いついたのですが、条件の整理とかに時間がかかったため3完が限界でした。
レートをあげるためにはもっと速く解く必要があるので、何か工夫がいるかなという感想です。

ただ、しばらくは問題の解き方のパターンを増やして行きたいので、茶diffの問題をひたすら解いていこうかなと思います。