413.1

世間の人はいかにして手を抜いているか、ということ。つまり0点取ったということ。

250

doubleの等差数列の整数部分だけが与えられる。初項は整数である時、各項の差分として可能な最小の値を答えよ、という問題。

等差数列AにおいてA[i]=A[0]+d*iなので、与えられた整数部分をS[i]とすると、S[i]<=A[i]

500

A[i]=A[i/p-x]+A[i/q-y]なるときにA[N]の値を求めよ、という問題。

下の方を配列でメモしておかないと、メモリが足りなくなるらしい。メモリが足りなくなる前に時間が足りなくなるのがJavaなわけですが。

1000

グラフ、というか木が与えられるので、k-安定集合の数を答えよ、という問題。

木、というか閉路がない＋孤立点がない、と解釈して、任意の点から探索を開始。ある点の隣接点のうち、探索済みの点は高々一つで、それを除いた点について、いくつの点を含むか含まないか。各点について、自分を含む(あるいは含まない)時に、自分の次に探索する点でいくつ作れるか、というのを覚えておいて、ちゃんと計算すればそこまでだと思う。

実装系。入力が木だとは思わなかった...。