AtCoder Beginner Contest 134 D - Preparing Boxes
問題概要
個の箱が並んでおり、各箱にボールを入れるかどうかを決めることができる。この時、
について、
の倍数が書かれた箱に入っているボールの数の総和を2で割った余りが
であるような入れ方を構成せよ。
解法
箱を昇順に見て行こうとすると、番目の箱にボールを入れるか否かを決めるためには、
番目の箱にボールが入っているかの情報が必要であるが、これは
番目の箱を見ている状態では未知の情報なのでこれではダメ。
逆に、降順に見て行くと、昇順に見て行く時に未知であった情報は既に判明しているので箱を降順に見て行く方針で考える。
これをしようとすると、
①:箱を降順に見て行く
②:①の内側のループで番目の箱を見て行く
というアルゴリズムになり、これはとなり、間に合わなそうなお気持ちになるかもしれないが、
となるため、計算量は
となり、間に合う。
間に合うため、上に書いたアルゴリズムを実装して、AC。
