5000個程度の長方形の座標が与えられるので、他のいずれかの中に完全に含まれるものの個数を答えよ、という問題。 自明解は5000^2で、多分間に合わないと信じる。logNを出す必要があるので、ソートか何かかなぁ、という感じ。 取り敢えず、左から順番になめ…

整数Nと使って良い数字のリストが与えられるので、使って良い数字だけからなる最小のNの倍数を答えよ、という問題。 先頭から桁を一つずつ追加しつつ、余りをメモしつつ、な感じでBFSする。状態数はNで停止するはず。BFSなので桁数が一番小さいのが出るので…

二つの文字列が与えられるので、それぞれから任意の文字を削って同じ文字列になるようにするとき、残る文字列のうち最長のものの長さを答えよ、という問題。 長さの指定がないので、適当にやっても十分間に合うんだろうか、からテスト開始。取り敢えず長さN…

商品の値段と売ることのできる期日のリストが与えられる。一つのものを売ると時間が一つ進む。売ろうとしたものがすべて売れるとして、売値の合計の最大値を答えよ、という問題。 最後から順に何を売るか割り当てていけば良く、まだ売ることのできるすべての…

N人が座っている円卓で、隣接する二人をスワップするという操作を何回やれば、両隣の人が逆転した状態にできるか答えよ、という問題。 N人をK人とN-K人に分けて、それぞれをスワップ操作で逆順にすることを考える。K人のスワップは、2K-3回のスワップとK-2人…

NxMの格子点上にある都市において、上下左右斜めの8方向のみに道がある状況で、すべての都市を一度ずつ巡る最短閉路長を求めよ、という問題。 NxM回移動する必要があり、距離1の遷移より短い遷移はない。なので、距離1の遷移のみで一筆書きできるならば、NxM…