たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】AtCoder Grand Contest 002 B問題 状態を管理する配列【C#】

下記の問題の復習です。今回は、たまにみる”状態を管理するための配列”についてのメモです。

atcoder.jp

問題概要

  • N個の箱があり、1つ目の箱には赤いボールが、それ以外には白いボールが入っている
  • x , y の入力が与えられ、x番目の箱に入っているボールを一つ、y番目の箱に入れる操作を行う
  • すべての操作が完了したとき、赤いボールが入っている可能性がある箱が何個あるのか求める

公式説明動

解答の全容は下記動画を見てください

www.youtube.com

考察時のポイント

  • 各箱に入っているボールの数をカウントするための配列を用意
  • 各箱が赤いボールが入っている可能性がある箱なのか管理するための配列を用意(今回のタイトルの件)
  • 赤いボールが入っている可能性があるのは 赤いボールが入っている箱からの移動先の箱が対象となる
  • 与えられたx,yに従って箱にあるボールの数を増減するが、ボールの数が 0 になる箱は赤いボールがある可能性が0である

実装について

ACとなった実装は下記です。

github.com

今回、タイトルにも書きましたが、箱の状態を管理するような配列を用意しています。bool[]型で定義して、条件を満たす場合はTrue、満たさない場合はfalseとしています。

どの問題だったか忘れたのですが、このようなやりかたは多々みかけるので、忘れないよう、意識できるように記事に残しておきます。