314.1

たまたま先日のPower Overwhelmingと似たような問題に当たった。こちらはlong溢れしない良い問題。

250

N人の人が1列に並んでおり、自分より背の高い人が左側に何人いたかを背の低い人から順に答えたリストが与えられる。どのような順番に並んでいた答えよ、という問題。

一番背の低い人は自分の位置を答え、二番目に背の低い人は一番背の低い人が左側にいるなら一つずれている位置を答えるが、そうでなければ自分の位置を答える。このように、自分より小さい人の位置を考慮しながら、小さい人から順番に位置を決めていけば良い。

500

N本の棒が与えられるので、三角形を一つの棒を複数回使わずに作る事を考える。このとき、三角形の面積の総和の最大値を答えよ、という問題。

三角形の面積はヘロンの公式から求めることができるので、任意の三本の組が三角形になるかどうかを判定する。(判定式は問題文中に書いてある。)後は同じものを複数回使わないようにDPで合計値を計算していけば良い。

1000

1個10円のものをN個買いたいが、K個のセットをかうとM円で、P個のセットを買うとQ円であることが分かっている。買い過ぎても良いので、一番安く買うのに必要な値段を答えよ、という問題。

N,K,Pはどれも10^12程度の大きさ。ここではKとPの大きさについて考える。KまたはPが十分に大きい場合、それぞれの買う個数を決めれば、別のセットの買い方は3通り(買い過ぎてもいいから買う、買い過ぎないギリギリまで買う、全く買わない)になる。なので、KまたはPが10^6以上だとすると、10^6通りだけその3通りを試せば良い。なので以降ではKとPがともに10^6以下だと思って良い。

このとき、KをP個買えるなら、PをK個買うと言った買い替えができるので、KをP個以上買うか、PをK個以上買うかの両方を満たすような状況について考える必要はない。(少なくともどちらかのセットの方を優先的に買った方が損はしない。)つまり、Kの個数はP以下か、Pの個数はK以下である。どちらも高々10^6なので、適当に全部探索すればおしまい。