想定解なんて知ってるわけないじゃん...。 問題 大きさ1のものと2のものしかないナップザック問題。 解答例 大きさごとに分けて、価値の大きい順にソートしておく。詰められる量が奇数なら、大きさ1の側から一番価値の大きいものを1個詰めておく。後は、大き…

典型的な誤差について考える幾何の問題。 問題 正N角形の頂点のうちの三つが指定されるので、可能な正N角形のうち、一番小さいものの面積を答えよ、という問題。 解答例 外心を計算して、各頂点との間でなす角の角度を求めてやる。それが正N角形のNを指定し…

過去問ちょこちょこ。4桁の人が解いている問題はやる必要ないとは思う。 問題 N*MのホールをカバーするようにA*Aの布を敷きたい。布は切ってはいけない。何枚必要か答えよ、という問題。 解答例 縦に何枚、横に何枚、というのを計算して乗算するだけ。乗算の…