300 グリッド上に石が何個か乗っかっている。今、方向を選んで、その方向にすべての石を1マス動かすという操作ができる。落っこちた石は棄てる。残りの石をちょうどK個にするために必要な操作の回数の最小値を求めよ。残りの石は長方形状の場所に収まること…

問題 高々21*21の盤面が与えられる。各マスは'.'か、アルファベットが書かれている。アルファベットは21種類のうちどれかである。今、この盤面上で「パス」を考える。パスは、iマス目がi+1マス目に隣接している(1 解法 まず、パスの定義に「互いに異なる」と…

3638 Moogle いくつか点がある。そのうちのC個を選んで、それらの座標は正確に記録する。他は、C個の点のうち各点をはさむような2点の間にあるということだけ記録する。そのとき、平均誤差を最小化したい。その値を求めよ。DP。なぜかabs(double)を実施した…

3658 Artificial Lake 長方形を横にいくつかつなげたような形の水槽がある。水槽の最も低い場所の上空から、水を流していく。各部分が高さ1の水で覆われるまでにかかる時間を求めよ。stackを使って適当にやる。 1894 Alternative Scale of Notation 10進法で…

2374 Fence Obstacle Course フェンスがいくつかX軸に平行にある平面上で、原点から(S, N)までの最短距離のうちX軸方向の移動距離を求めよ。DPだが、ある位置について見るときにフェンスに邪魔されないならそのままスルーしてよくて、フェンスに邪魔されたら…

1201 Intervals いくつかの整数の区間と、それぞれに含まれるべき整数の個数が与えられる。整数の集合で、これらの区間についての制約をすべて満足しかつ、集合の大きさが最小のものの大きさを求めよ。累積和をとると線形計画問題になる。この線形計画問題は…

3251 Big Square グリッド上にJやBや*がある。*である場所１つにJを置いた後、頂点がJのみからなる最大の正方形の面積を求めよ。O(N^4)を定数倍ではやくする

2132 Cow Math 辺に重みがついているグラフが与えられる。起点から終点までの各経路について、通った辺の重みの最大公約数を考える。すべての経路について最大公約数を求めた時、それらの最小公倍数を求めよ。答えをRとして、Rがある整数iで割り切れるかどう…

3270 Cow Sorting それぞれ異なる数値をもつ牛がN頭いる。牛を入れ替えて数値の順に整列させたい。2頭の牛を入れ替える際には、2頭の数値の和だけコストがかかる。任意の2頭を入れ替えられる。コストの和を最小化せよ。巡回列らしい 3280 Cheapest Palindrom…

2430 Lazy Cows 2*Bのグリッド上に牛がN頭いる。K個の長方形を置いて牛を全部カバーしたい。面積の和の最小値を求めよ。牛をソートしておいて、左から順に見ていくが、「上段をカバー」「下段をカバー」「両方の段をそれぞれ幅1でカバー」「両方の段を幅2で…

2180 Bale Figures 立体の情報が与えられるので、その立体の表面積（地面に接している部分は除く）を求めよ。やるだけ 3182 The Grove 連続したXを一周するような経路で最も短いものを求めよ。てきとうに通る点を決めてDijkstraするだけ

3260 The Fewest Coins コインが何種類かあって、ある品物を買うのに、「払ったコインの枚数」と「おつりの枚数」の合計が最小になる方法で買いたい。おつりは最も枚数が少なくなるように返される。払うことができるコインの枚数には限界があるが、おつりで…

3622 Gourmet Grazers 牛と牧草があり、牧草ごとに値段とgreennessが決まっている。各牛は、牧草に要求する最小の値段とgreennessを持っている。牛は個性を犠牲にしたくないので、それぞれ異なる牧草を食べたい。牧草の値段の総和を求めよ。牛と牧草をあわせ…

最下位。 1: 簡単だが、敷居が高いように思う 2: やるだけ 3: やるだけ 4: 日本語をうまく読解できればわりと良い問題 5: 計算式に従って計算する（行列の知識要。高１とかだと習っていない可能性もある） 6: 問題文が非常に曖昧、かなり好意的に解釈しない…

問題 テレビ局channel2の番組では今年も「D-1ダジャレグランプリ2011（通称D-1）」という番組を放映することになりました。応募のあったダジャレをスタジオの三人の審査員が審査する毎年恒例の番組です。高評価を得ると一躍有名になれるということもあって、…