305.1

思っていた以上に間隔があいたのか、それとも2月が短かったのか。

250

整数配列が与えられる。A,B,Cの三人で、Aがまず配列を二つに分け、Bが二つの配列のうちどちらかを二つに分けるという処理を行い、C,B,Aの順番で好きな配列を選ぶ。配列の値の総計がスコアになるとき、各人が自分のスコアを最適にしつつ、Aのスコアをより小さくできるものを選択するとして、Aが得られる最大のスコアを求めよ、という問題。

Aがどこで分けるかで全探索。Bは指定された規則で分割をするので、それを実装するだけ。

500

二つの文字列をinterleaveしてできる任意の文字列の任意部分文字列で、回文となるものの最大長を答えよ、という問題。

偶数文字の回文と奇数文字の回文がある。奇数文字の回文については、どちらかの文字列の任意の文字を中心として考える。使わない文字列については、中心より右側に来るものと左側に来るものを分ける位置を任意に決定する。偶数文字の回文については、両方の文字列について分割される位置を決めておく。あとは左側と右側に追加可能な文字が高々2通りずつあるので、計4通り程度を吟味し、一致するようならば拡張していく、という感じでDPを書くだけ。

900

1からN(<=10^18)までの整数で、K^M(M>=2)となる整数の数を答えよ、という問題。

Mが3以上になるケースのKは高々1000000個くらいしかないので、それらについて吟味する。既に他の数のべき乗になっているものは無視する。また1000000より大きくてsqrt(N)以下の数はMが2になる可能性がある。これらの数について、すでに他の数のべき乗になっているものを除いたものは二乗してもN以下なので、1回ずつカウントする必要がある。あとは前半部をメモしつつやるだけ。