【AtCoder】AtCoder Grand Contest 002 B問題 状態を管理する配列【C#】
下記の問題の復習です。今回は、たまにみる”状態を管理するための配列”についてのメモです。
問題概要
- N個の箱があり、1つ目の箱には赤いボールが、それ以外には白いボールが入っている
- x , y の入力が与えられ、x番目の箱に入っているボールを一つ、y番目の箱に入れる操作を行う
- すべての操作が完了したとき、赤いボールが入っている可能性がある箱が何個あるのか求める
公式説明動
解答の全容は下記動画を見てください
考察時のポイント
- 各箱に入っているボールの数をカウントするための配列を用意
- 各箱が赤いボールが入っている可能性がある箱なのか管理するための配列を用意(今回のタイトルの件)
- 赤いボールが入っている可能性があるのは 赤いボールが入っている箱からの移動先の箱が対象となる
- 与えられたx,yに従って箱にあるボールの数を増減するが、ボールの数が 0 になる箱は赤いボールがある可能性が0である
実装について
ACとなった実装は下記です。
今回、タイトルにも書きましたが、箱の状態を管理するような配列を用意しています。bool[]型で定義して、条件を満たす場合はTrue、満たさない場合はfalseとしています。
どの問題だったか忘れたのですが、このようなやりかたは多々みかけるので、忘れないよう、意識できるように記事に残しておきます。
