AtCoder 478 振り返り

AtCoder478振り返りです。
最近ずっとさぼってたので久しぶりの出場です

結果

ABC3完でした。3完ですが3ペナ…

ふりかえり

A問題

• 問題
  • https://atcoder.jp/contests/abc478/tasks/abc478_a
• 回答
  • https://atcoder.jp/contests/abc478/submissions/79730467

1時間近くどハマりしてました…汗
問題文通り解くためにはMArrayが必要だけどそんな難しいことやる必要あるのか？
割って残りを配るにしてもどうやるのか？
わからず悩みに悩み、結局Rustで書いて提出しました

#[fastout]
fn main() {
    input! {
        n: usize,
        mut m: i32,
    }

    let mut v = vec![0; n];
    while m > 0 {
        for i in 0..n {
            v[i] += 1;
            m -= 1;
            if m <= 0 {
                break;
            }
        }
    }

    for i in 0..n {
        println!("{}", v[i]);
    }
}

ちなみに割ってあまりを分配するやりかたで普通に解けます。
その場合の回答はこんな感じです。

割った値で初期化して、残った値を分配すれば良いだけでした

main :: IO ()
main = do
  [n, m] <- getInts
  let (d, md) = m `divMod` n
      ans = snd $ mapAccumL (\acc v -> (max 0 (acc - 1), if acc > 0 then v + 1 else v)) md $ replicate n d
  mapM_ print ans

B問題

• 問題
  • https://atcoder.jp/contests/abc478/tasks/abc478_b
• 回答
  • https://atcoder.jp/contests/abc478/submissions/79732050

自作関数combinationsNで指定した個数の相異なる組み合わせを出せるので、リスト内包表記で組み合わせの合計がV以下になるように計算しました。

main :: IO ()
main = do
  [_, v] <- getInts
  ws <- getInts
  print $ maximum [vi + vj + vk | [(i, vi), (j, vj), (k, vk)] <- combinationsN 3 (indexed ws), i + j + k <= v]

C問題

• 問題
  • https://atcoder.jp/contests/abc478/tasks/abc478_c
• 回答
  • https://atcoder.jp/contests/abc478/submissions/79743564

リスト内部のある長さK以下の区間をソートした結果、全体がソートされた状態になるかどうかを判定します。

具体的には以下のように考えます。

• リスト内部の区間(長さK以下)をソートした結果と、全体をソートした結果は同じになります
• よって、ソートが必要になる区間は、「両端から"元のリストとソート後のリストが同じである要素を除いた区間"」になります

この長さがK以下であることを判定すれば良いです

-- Main
main :: IO ()
main = do
  [n, k] <- getInts
  as <- getInts
  let as' = sort as
      diffs = zipWith (==) as as'
      ht = length $ takeWhile id diffs
      lt = length $ takeWhileEnd id diffs
  printYn $ k >= n - (ht + lt)

全体を振り返って

A問題で大事故したけど強引に解けてよかったです（よかったのか…？？）
配列の初期化をreplicateでやるのと、分配をmapAccumLを使ってやることに早く気づければよかったのかな…

ともかく次も頑張ります！