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

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

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

完敗。手も足も出ず。 300 板の上にコインが乗っている。全部のコインを上下左右にまとめて移動させることができるので、できるだけ少ない操作回数で、コインの残り枚数を指定された枚数にしたい。最小回数を答えよ、という問題。 どの矩形領域を残すかとい…

分かるけど、できない。できなきゃ意味ない...。 250 距離Xだけ荷物を運ぶが、一度の運搬で移動して良い距離は素数でない距離でなくてはならない。何回の運搬に分けて行えば良いか答えよ、という問題。 Xが素数なら1だけ動かして、素数でなくなるまで試す。 …

問題 有向グラフが与えられる。開始点と終了点が与えられるので、最短距離またはその+1までのパスは何通りあるか答えよ、という問題。 解答例 まずダイクストラで、開始点からの最短距離を全部の点について求める。再度ダイクストラで、最短距離またはその+1…

明日に備えて肩慣らし。タグをPOJにしておくべきだったかも？ 問題 石がいくつかある。それぞれに重さと価値があって、二つのバケツに振り分ける。最初は一つ目のバケツに石を入れていき、D+1以上の重さになったらもう一つのバケツに入れていく。二つ目のバ…

参加資格剥奪です、といわれても仕方ないくらいひどいスコア。 A 8x8の盤面上を、下向きに移動する物体が配置されているので、上下左右斜め移動を駆使して全部回避できるかどうか判定せよ、という問題。 やるだけ。 B 文字列が与えられるので、その任意の部…

比較的新しいところをやろうとして、解いた問題番号のmax付近から。2005年って新しくはないな...。 問題 行列に対して、上下反転・左右反転・90度刻みの回転・対角線で反転(2種類)といった操作列が与えられるので、最終的な結果を答えよ、という問題。 解法例…

解けないと判断したときに踏ん切りがつかないのをどうにかしましょうね、というお話。 250 a+b*xとc*d^yという式で表現されるN以下の数はいくつあるか答えよ、という問題。 前者は圧倒的に数が多いので、取り敢えず除算でいくつあるかカウントする。後者は指…

最初二問が普通なのに、最後が...。 250 N人の人がいて、全員白または黒の帽子をかぶっている。自分以外の人を見て白い帽子をかぶっている人数を答えるので、白い帽子をかぶっている人の人数を答えよ、という問題。 結果をソートすると、白い帽子をかぶって…

二回目なのに、余りの頭の悪さに絶望した...。 250 NxMの盤面に数字が書かれている。どの行・どの列からも二つ以上数字を選ばないように選んだとき、総和が等しくなるか否かを答えよ、という問題。 DPすれば良い。選択しない行があるとめんどくさいので、行…