Project Euler

■142
明らかに，計算量を減らす必要がある．
x+y=a²
x-y=b²
x+z=c²
x-z=d²
とする．
x=(a²+b²)/2
y=(a²-b²)/2
より，aとbを適当に決めることでxとyを決定できる．
次に，dを適当に決める．
c2=2x-d²
z=(c2-d²)/2
とすれば，
z<yかつc2が平方数である事を確認する事で，条件を満たすかどうかを判定できる．

■144
実装ゲー．
まず，直線と楕円の交点の方程式を解く．
次に，傾きaの直線が傾きmの接線によってどう反射すれば良いかを考える．
要するに，θ=tan^-1(m)だけ逆回転→y軸対称に反転→θ回転でよい．
元の光線のベクトルをv=(1, a)する．反射した光線のベクトルをuとすれば，
u=R(θ)SR^-1(θ)v
R(θ)は回転行列，Sはy軸対称に反転させる行列．
後は，適当に問題の条件を実装．ビジュアライザを作るのがオススメ．

■149
最大値の計算は全ての縦横斜めについて行う．
a[0],…,a[n-1]の部分総和の最大値の求め方．
dp[k]をa[0],…,a[k]までの部分総和の最大値とすると，
dp[k+1]=max{a[k+1], dp[k]+a[k+1]}
となる．

■150
愚直に計算するとO(n³)だが，n=1000なので現実的時間内に求められる．強いてい言うなら，横方向の総和を先にメモ化しておくと良い．
sum[n]=Σ_0≦k≦na[k]
↑こんな感じ．
a[i]+…+a[j]はsum[j]-sum[i-1]で求められる(i=0の時は単純にsum[j])．

■164
dp[桁数][上から1桁目][上から2桁目]=条件を満たす数字の個数
でDP．
初期値は，
dp[0][0][0]=1
更新式は，
i+j+k≦9なるi,j,kについて，
dp[d+1][j][i]+=dp[d][k][j]

■179
約数の数はO(√n)で求められるので，計算量はO(n√n)だが，nの最大値が10⁷と小さいので，特に工夫せず求めた．

■191
条件が変なDP．
・前日=出席，遅刻無
・前々日=出席，前日=欠席，遅刻無
・前々日=欠席，前日=欠席，遅刻無
・前日=出席，遅刻有
・前々日=出席，前日=欠席，遅刻有
・前々日=欠席，前日=欠席，遅刻有
の6変数を用いる．更新式が少し複雑になるので注意．