261.1
プログラマ失格ですねこれは。それにしても点数の付け方がおかしい。(一般的にこう点数配分するのが正しいという状況で、相対的に普段よりも簡単とされるものに全く手が出ないのが何よりも問題。)
550
1からNまでの要素からなる二分探索木を行きがけ順で書いたときに辞書順でK番目のものを答えよ、という問題。
A文字以下の二分探索木の記述方法が何通りあるか分かれば、A+1文字の二分探索木は、どの文字をrootにするか決めれば計算できる。rootの文字が一つずつ大きくなるようにして、右側と左側が何通りあるかで、rootの文字は決定できる。このとき後いくつ先なのかを考えれば、右側と左側のそれぞれについて、要素数と何番目のものを答えれば良いかがわかる。後は再帰的に計算するだけ。
1000
N個のものについて、重さと上に積んで良い重さが与えられるとき、いくつ積むことができるか、という問題。
全く手が出ない。うまくグラフにして最大流とかなんだろうか？(あるものを使うと今まで使えたはずの別のものが使えなくなる、というのは最大流で良く出てくる性質。)
全然ロジカルな話は分からないけど、重さと上に積んで良い重さの和でソートすると、単純なDPになるらしい。順番付けがあっているなら、DP自体は自明に組める。個々の二つについては、前の奴の下に後ろの奴は入らないけど、後ろの奴の下に前の奴が入る、という状況は起きないようになっている。それがその前に何か積んである状況でも保障されるかどうかは不明。
前の奴が重さAでBまで積めて、後ろの奴が重さCでDまで積めるとすると、後ろの奴を積んだ後の状態では重さCで、それがB以下なら、A+BがC+D以下であることからA+CはA+B以下なのでAはD以下になる。C+XがB以下なら、A+XがD以下だから、ここでの順番の逆転は問題にならない？両方積めるケースが存在するのに、それを否定することさえなければ良い、というのが結論だから、問題ないのかなぁ...。
