AtCoder Beginner Contest 423 振り返り

AtCoder Rated参加です

結果

今回はABCの3完でした。2ペナだしたのですが、なぜか久しぶりの茶パフォでした。

ふりかえり

A問題

• 問題
  • https://atcoder.jp/contests/abc423/tasks/abc423_a
• 回答
  • https://atcoder.jp/contests/abc423/submissions/69309565

A問題ながら、解き方がわからなくて沼りました。条件を式にして、式変形することで解く問題です。

まず、引き出すお金（つまり解）をyとすると、問題の条件は以下のような数式に書き下せます。

$y + y \cdot \frac{c}{1000} \leq x$

しかし、このままではyを求めることはできません。
yを求めやすい形に式変形しましょう。

$y \leq x \cdot \frac{1000}{1000 + c}$

1000 円単位で引き出すという制約があるので、

$x \cdot \frac{1000}{1000 + c}$

を計算して、下3桁を0にすれば解けそうです。これは1000で割って1000をかけることで実装できます。

実際のコードはこちらです。どうでもいいけどコワスギ銀行手数料たかすぎですね、、

main :: IO ()
main = do
  [x, c] <- getInteger

  let ans = (x * 1000 `div` (1000 + c)) `div` 1000 * 1000

  print ans

B問題

• 問題
  • https://atcoder.jp/contests/abc423/tasks/abc423_b
• 回答
  • https://atcoder.jp/contests/abc423/submissions/69318575

扉が1になるまで、つまり0になる間通過する部屋の数を求める問題です。

扉を通過した数が入った部屋の数(ただし最初の部屋を除く)になるので、まずは通過した扉の数を求めます。これはtakeWhile (==0)で求めることができます。

例えば、左側からスタートした人が通過する扉の数は以下のように求められます。

main :: IO ()
main = do
  n <- readLn @Int
  ls <- getInts

  let l = length $ takeWhile (== 0) ls

同様に、右からスタートした人が通過する扉の数は以下のように求められます。　

  let l = length $ takeWhile (== 0) ls

求める答えは入っていない部屋の数なので、全体の部屋数から入った部屋数を引きます。
2人が最初にいた部屋をカウントする必要があることに注意しましょう。

   let ans = n + 1 - (l + r + 2)  -- 提出版では (n - 1) - (l + r) としています。

一つ目の提出版がこちらです。

main :: IO ()
main = do
  n <- readLn @Int
  ls <- zip [1 ..] <$> getInts

  let l = length $ takeWhile ((== 0) . snd) ls
      r = length $ takeWhile ((== 0) . snd) $ reverse ls

  print $ (n - 1) - (l + r)

しかし、この回答だとサンプルはパスするのですが、提出するとWAになってしまいます。
2人が入る部屋が重複していた場合、その分重複してカウントされることが原因になっていそうです。

この問題だと、入る部屋が重複するのは1の扉がない、つまり全ての扉が0の場合のみしかなさそうです。このときは入った部屋数が全体の部屋数より大きくなることから、回答の値がマイナスになります。なので、答えが0より小さい場合は0にすればよさそうです。
（全ての扉が0だった場合をコーナーケースとして処理してもよいかもしれません。）

最終的な提出コードは以下になりました。
(提出コードでは部屋をzip [1..]しているのでtakeWhile ((== 0) . snd)としていますが、このzipは不要です。)

main :: IO ()
main = do
  n <- readLn @Int
  ls <- zip [1 ..] <$> getInts

  let l = length $ takeWhile ((== 0) . snd) ls
      r = length $ takeWhile ((== 0) . snd) $ reverse ls
      ans = (n - 1) - (l + r)

  print $ bool ans 0 (ans < 0)

C問題

• 問題
  • https://atcoder.jp/contests/abc423/tasks/abc423_c
• 回答
  • https://atcoder.jp/contests/abc423/submissions/69336441

初期地点から、左右で0の扉があるところまで扉を開いていきます。
問題を見ていると、以下の条件で問題が解けそうに見えます。

1. 0となる扉のうち最も左端の扉から、0となる扉のうち最も右端の扉までの区間を取り出せばよさそう
2. 0の扉は自由に通過できるので、1回閉める操作を行うだけになる。また、1の扉は1回開けば自由に通過できるので、開く -> 閉じる の2回操作になる
   • 0の扉は1回操作、1の扉は2回操作で答えが求められる

1.の条件については、dropWhileを使って以下のように取り出すことができます。

ls <- getInts

let ls' = dropWhileEnd ((== 1) . snd) $ dropWhile ((== 1) . snd) ls

2.の条件については、map (+ 1)で強引に実装しました。

map (+ 1) ls'

全体のコードは以下の通りです。しかしこの回答も提出時にWAになってしまいます。

main :: IO ()
main = do
  [n, r] <- getInts
  ls <- zip [1 ..] <$> getInts

  let ls' = dropWhileEnd ((== 1) . snd) $ dropWhile ((== 1) . snd) ls
      ans = sum $ map ((+ 1) . snd) ls'

  print ans

これはスタート地点が関係してきます。

扉が以下のようになっていて、

 1 1 1 1 0 0 0

2の部屋からスタートする場合、以下のような立ち位置になります。

 1 1 1 1 0 0 0
    ↑スタート地点

また逆に扉が以下のようになっていて、6の部屋にいる場合

 0 0 0 1 1 1 1

6の部屋からスタートする場合、以下のような立ち位置になります。

 0 0 0 1 1 1 1
            ↑スタート地点 

この場合、1.の条件「左端の0から右端の0」で計算すると、スタート地点が含まれなくなってしまいます。改めて条件を考慮する必要があります。

では何を考慮する必要があったのでしょうか？

そもそも1の条件だと、考慮に漏れがあります。
スタート地点より左に0が無い場合は右だけに移動、スタート地点より右に0がない場合は左だけに移動します。

この条件を考慮すると、1.の条件ではなく

a. 「スタート地点から左の0となる最も左端まで移動」
b. 「スタート地点から右の0となる最も右端まで移動」

で考えればよさそうです。

この場合、aの区間は

  let left = dropWhile (== 1) $ take r ls

b.の区間は

   let right = dropWhileEnd (== 1) $ drop r ls

で求められます。

もし移動できない場合（つまり移動方向の扉が全て1の場合）は配列が空になることを考慮すると、右方向、左方向の操作回数は以下のように求められます。

  let ansLeft = if null left then 0 else sum $ map (+ 1) left
      ansRight = if null right then 0 else sum $ map (+ 1) right

提出回答は以下のようになりました。（ちなみに、これもzip [1..]してますが不要なコードです）

main :: IO ()
main = do
  [n, r] <- getInts
  ls <- zip [1 ..] <$> getInts

  let left = dropWhile ((== 1) . snd) $ take r ls
      right = dropWhileEnd ((== 1) . snd) $ drop r ls
      ansLeft = if null left then 0 else sum $ map ((+ 1) . snd) left
      ansRight = if null right then 0 else sum $ map ((+ 1) . snd) right

  print $ ansLeft + ansRight

D問題(upsolved)

• 問題
  • https://atcoder.jp/contests/abc423/tasks/abc423_d
• 回答
  • https://atcoder.jp/contests/abc423/submissions/69356184
    • cjpさんの回答を参考にしました（というかほぼそのままです、すみません、、）

レストランに入った人を優先度キューで管理する問題です。

レストランに入ったらレストランの許容人数から入った人数を引き、退出したら許容人数に退出した人数を足します。

レストランに入る前のグループは問題分通り待ち行列（つまりリスト）で管理し、レストランに入っているグループは退出時間の優先度キューで管理します。

Haskellの優先度キューはData.Heapを使いますが、データをタプルにした場合、一つ目の値を優先して優先順位をつけてくれます。

そのため、優先度キューはH.Heap (退出時刻, 人数)とすればよさそうです。
こうすると、レストランから退出する時に退出時刻が小さい方から取り出すことができます。

レストランに入る前の待ち行列のグループ人数が、許容人数以下の場合はそのままレストランに入ります。

入る時間は現在時効と来店時間のうち、大きい方の時間になること
退出時間は現在時刻と来店時刻(a) + 退出までの時間(b) のうち、大きい方の時間であることから

レストランの許容人数をcap, 現在時刻をtとした場合は以下の通りになります。

c <= cap = max t a : f (H.insert (max t a + b, c) heap) (cap - c) (max t a) abc2

レストランの許容人数が足りずにグループが来店できない場合、退出まで待つことになります。
レストランからの退出はunconsで以下のように実装します。

((t', c'), heap') = fromJust $ H.uncons heap

そのため、退出時は以下のように実装になります。（退店時の時刻は解答に不要なのでconsする必要はありません）

f heap' (cap + c') t' abcs
  where
    ((t', c'), heap') = fromJust $ H.uncons heap

コードの全体像は以下のとおりです。

main :: IO ()
main = do
  [n, k] <- getInts
  abcs <- replicateM n getInts

  mapM_ print $ f H.empty k 0 abcs

f :: H.Heap (Int, Int) -> Int -> Int -> [[Int]] -> [Int]
f heap cap t [] = []
f heap cap t abcs@([a, b, c] : abc2)
  | c <= cap = max t a : f (H.insert (max t a + b, c) heap) (cap - c) (max t a) abc2
  | otherwise = f heap' (cap + c') t' abcs
  where
    ((t', c'), heap') = fromJust $ H.uncons heap

全体を振り返って

今回気づいたことなのですが、競プロで問題を解くには以下のことがもっときちんとできないといけなさそうです。書いてみると当たり前のことですが

• 解法をそのまま覚えるのではなく、考え方を理解してトレースできるようにする
• いきなりコードを書き出すのではなく、解くまでの道筋を頭の中で描けるようにする
• 一つ一つの条件を図に書いて視覚的に整理できるようにしておく

なかなか伸びませんが、焦らず地道に精進していこうと思います