問題 TopCoder Statistics - Problem Statementevimaさん 解法 動的計画法を使う。dp[i][j][p]に「i文字目まででAをj文字使った時にペアpに到達可能かどうか」を記録しておく。 if (!dp[i][j][p]) { dp[i + 1][j + 1][p] = true;// i+1文字目をAにする dp[i …

解法 i文字目時点での文字cの連続長の期待値をメモしておき、最後に全部足す。 コード public class SquareScores { public double calcexpectation(int[] p, String s) { int N = s.length(); // expScore[i][c]:= i文字目時点でのc連続長の期待値 double e…

問題 TopCoder Statistics - Problem Statement色んな国から来たN人が1列に座っていて、同じ国から来た人は隣り合って固まって座っている。何人かに、同じ国から来た人数を聞いた。その情報だけで、まだ聞いてない人がどう答えるか当てることが出来るか。 解…

問題 ボブが1からNまでの自然数を並び替えて数列pを作る（ここではpは1-indexedとしておく）。アリスはf(1)=p[1]、f(m)=p[f(m-1)]となるようにfを考える。ボブがどのように数列pを作ってもf(x)=1となるような最小のxを求めよ。 解法 ボブがどんな数列を作っ…

問題 おみやげがN個あり、それぞれvalue[i]の価値がある。2人におみやげの数が同じようになるように分けた時、価値の合計値が同じになるように分けることは可能か判定せよ。 解法 DPで[N/2][sum/2]の状態に到達可能か判定する。 コード public class FoxAndS…