458.1

最近ひどいのでリハビリ開始。

250

1次元の世界で、複数のボールが等速で移動する。初期位置が与えられたとき、指定された時間内に何回衝突するか答えよという問題。衝突した二つのボールはそれぞれ向きが反転する。

ボールが少ないので頑張って計算すればいつかは解ける。

実は衝突したときに向きが変わるとか考えないで、そのまま進めても同じなので、ぶつかるように進んでいるボールの距離が指定された時間内に到達するかどうか判定するだけ。

450

商品の金額リストが与えられるので、すべてを別々に購入するとき必要になる硬貨の枚数が最小になるように、硬貨の額面を決定する。このときの必要な硬貨の最小枚数を答えよ、という問題。

硬貨は小さい硬貨の整数倍であることが求められ、整数倍する際に無意味な硬貨を間に入れても良いので、取り敢えず素数倍だけ考えることにする。後は、新規硬貨を用意する際に、何倍のものを用意するか、というので全探索してやるだけ。それだと当然のごとく遅いので、途中経過で現在の最小枚数以上になったら枝を狩る。(かなりいい加減だけど通ってしまった。)

900

整数Nについてすべての約数を4で割った余りを考える。余りがいくつになるかでグループ分けしたとき、それぞれのグループに含まれる個数が指定されているとき、そのような整数Nが存在するか答えよ、という問題。

取り敢えず約数が4で割って2余るものというのは、0個か、1余るものと3余るものの合計のいずれか。4余るものは2余るものの整数倍個だけれど、2余るものがない時は4余るものも存在しない。1余るものは少なくとも一つは存在する。

以上を踏まえた上で、1余るものの数と3余るものの数の関係が導出できればおしまい。どうやるかはいつか考える。