問題 一直線上に左右それぞれに進行する物体がある。直線の長さLと物体の速度Vと初期位置Pと進行方向が与えられる。最後に落ちる物体の名称と時間を求めよ。 解法 貪欲法を使う。衝突により方向は変わるが速度は変わらない。注目物体以外に何もないと仮定し…

問題 要素数20の数列が与えられる。各要素は1か0である。すべての要素を0にする。ただし、注目点と隣接する要素は同時に反転される。 解法 反転される一番左の要素に注目する。各要素を見ていき1なら反転させる。ひとつめの要素に関してはそのままでは決定で…

問題 縦5×横6の配列が与えられる。配列の要素は1か0である。与えられた配列の要素を全て0にする。ただし、注目点と四近傍は同時に反転される。 解法 貪欲法で解ける。ひとつ上の要素が1ならその注目点で反転させる。一番上の要素の状態を全探索し、全て0にで…