コンテストページ:AtCoder Beginner Contest 275 - AtCoder
コンテスト中AC:A,B,D
コンテスト後AC:E,F(自力)
Cでハマったのと、Eで回数制限があることを忘れて考察してしまいました。

C - Counting Squares

点 $P_0,P_1,P_2,P_3$ が、正方形の頂点を半時計回りに順番に並べた点である

これが成立するには以下の条件を満たす必要があります。

辺の長さが等しい
凸多角形
辺のなす角が全て90°

これは、 $0\leq i \leq 3$ の全てについて、ベクトル

$\vec{v_0} = \vec{P_{(i+1)\ mod\ 4}P_i}$
$\vec{v_1} = \vec{P_{(i+2)\ mod\ 4}P_{(i+1)\ mod\ 4}}$

が以下の3つを満たすことと同値です。

$|\vec{v_0}| = |\vec{v_1}|$
$\vec{v_0}\times \vec{v_1} \lt 0$
$\vec{v_0}\cdot \vec{v_1} = 0$

2は外積( $sin\theta$ )、3は内積( $cos\theta$ )です。
1、3は正方形なので自明かと思います。2は1本目の辺と2本目の辺の位置関係が半時計回りである必要があるということです。

2は要らなくて3だけでよいのではと思ってしまいますが、内積だけだと時計回りの角度が半時計回りの角度がわからないので必要になります。

全ての点のあり得る4つの組に全てについて、上の条件を満たすものをカウントすると、同じ正方形が4回数えられるので、条件を満たす個数を1/4したのが答えとなります。

コンテスト中は3の条件が必要だと思っておらず、解けませんでした。
提出コード:Submission #36108492 - AtCoder Beginner Contest 275

D - Yet Another Recursive Function

メモ化再帰の問題。種類数の見積もり方法がわからずにとりあえず通しました。見積もり方法は公式解説参照。

提出コード:Submission #36064977 - AtCoder Beginner Contest 275

E - Sugoroku 4

操作回数を考慮しない点で異なりますが、期待値DPと同じような考え方ができます。
$N=10,M=3$ の例で考えてみます。

まず、DPを以下のようにしてみます。
$dp[i]$ :=マス $i$ からゴールできる確率

例えば、 $i=1$ なら、
$dp[1] \leftarrow \frac{1}{M}(dp[2]+dp[3]+dp[4])$
という風に計算できます。
$dp[10]=1$ なので、後ろから順に更新できそうと思ってしまいますが、今回は $N$ を超える場合には戻ってくるので、例えば $i=9$ の場合、

$dp[9] \leftarrow \frac{1}{M}(dp[10]+dp[9]+dp[8])$

となり計算できません。
問題文をよく読むと操作回数に限度があります。操作を1回すると残りの操作回数が1減るので、残りの操作回数が0となってしまえばそれ以上の操作はできず、確率が確定します。
そこで、DPに操作回数の情報を持たせ、以下のように変更します。
$dp[i][j]$ :=残りの操作回数が $i$ 回で、マス $j$ からゴールできる確率

初期値は、

$0\leq j \leq K$ について、 $dp[i][N]\leftarrow 1$
$0\leq j \leq N-1$ について、 $dp[0][j]\leftarrow 0$

と、設定します(その他もすべて0で初期化します) 。
テーブルの更新はメモ化再帰でもいけそうですが、実装では普通のループにしました。

操作回数 $i=1,\cdots , K$ の順に、マス $j\ (0\leq j\leq N-1)$ について、
$dp[i][j]\leftarrow \frac{1}{M}(dp[i-1][j+1] + dp[i-1][j+2] + \cdots + dp[i-1][j+M])$

と更新します。
なお、 $j+k\gt N\ (1\leq k \leq M)$ の場合には戻るようにする必要があります。

答えは $dp[K][0]$ の値です。
計算量は $O(KNM)$ です。これでも通りましたが、和を求める部分は区間和となっているので、累積和を使えば、 $O(KN)$ に落とせそうです。
提出コード:Submission #36076090 - AtCoder Beginner Contest 275

F - Erase Subarrays

部分和DPを応用します。今回DPテーブルには操作回数の最小値を記録します。

普通の部分和DPのように考えると、

$dp[i][j]$ := $A$ の $i$ 番目までの要素まででできる部分列の和が $j$ であるときの操作回数の最小値

となりますが、このままだと操作回数の最小値は求められないので、どうするかを考えます。

例えば、 $N=10$ で $2,3,6,8$ 番目の要素で部分列を作ったとします。 $i$ 番目を選んだら1、選ばなかったら0とした数列 $B$ を考えます。

$B=\{0,1,1,0,0,1,0,1,0,0\}$

となり、この時の操作回数の最小値は、閉区間 $[1,1],\ [4,5],\ [7,7],\ [9,10]$ に操作したときの 4回です。

実は、最初の0を除いて $B_i = 1\wedge B_{i+1}= 0$ となる数をカウントすれば最小の操作回数に一致します。最初の0のみ、例外として+1しておきます。

以上より、 $i$ 番目の要素を部分列として選んだ状態と選んでいない状態の2つをDPの情報として追加すれば良いです。すなわち、

$dp[i][j][k]$ := $A$ の $i$ 番目までの要素まででできる部分列の和が $j$ であり、かつ状態が $k$ の時の操作回数の最小値
但し、 $k=\{0,1\}$ で、 $k=1$ なら $i$ 番目を選んでおり、 $k=0$ なら選んでいないことを表す。

初期値は、
$dp[0][A_0][1]\leftarrow 0$
$dp[0][0][0]\leftarrow 1$
とし、他は $\infty$ にしておきます。
遷移については実装を見てもらう方が早いと思います。
ポイントとしては、 $i-1$ 番目が $k=1$ の状態から $i$ 番目が $k=0$ の状態に遷移する時に操作回数に+1します。