VBが遅い
昨日のSRM501 Div1のMediumをVBで書いてみたのですがTLEを回避出来ません。
ほぼ同じ内容のC++のコードだと最大ケースでも500msかからないというのに…。
配列のアクセスの速度とかが原因だとは思うけど酷い。
計算量がギリギリの問題はC++で解くべきかもしれない。
'Failed System Test Imports Microsoft.VisualBasic Imports System Imports System.Collections Imports System.Collections.Generic Imports System.Text Imports System.Math Imports Weight = System.Int32 Public Class FoxAverageSequence Public Const MOD_VALUE As Integer = 1000000007 Dim DP(1, 40, 40, 1600) As Integer Dim seq As Integer() Dim N As Integer Public Function Memo(ByVal now As Integer, ByVal Sum As Integer, ByVal Back As Integer, ByVal OK As Boolean) As Integer If now = N Then Return 1 If DP(IIf(OK, 1, 0), now, Back, Sum) >= 0 Then Return DP(IIf(OK, 1, 0), now, Back, Sum) Dim M As Integer Dim Res As Integer = 0 If now = 0 Then M = 40 Else M = Sum \ now Dim S As Integer = 0 If OK Then S = Back If seq(now) <> -1 Then S = seq(now) : M = Math.Min(M, seq(now)) For i As Integer = 0 To M If OK And Back > i Then Continue For If seq(now) <> -1 And seq(now) <> i Then Continue For Res = (Res + Memo(now + 1, Sum + i, i, IIf(Back > i, 1, 0))) Mod MOD_VALUE Next DP(IIf(OK, 1, 0), now, Back, Sum) = Res Return Res End Function Public Function theCount(ByVal seq_ As Integer()) As Integer Dim i As Integer, j As Integer, k As Integer, l As Integer N = seq_.Length seq = seq_ For i = 0 To 40 For j = 0 To 1600 For k = 0 To 40 For l = 0 To 1 DP(l, i, k, j) = -1 Next Next Next Next Return Memo(0, 0, 0, 0) End Function End Class
'Passed System Test #include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> #include <cstring> using namespace std; int n; int DP[41][1602][41][2]; vector<int> seq; const int MOD=1000000007; class FoxAverageSequence { int solve(int now,int sum,int back,int ok){ if(now==n)return 1; if(DP[now][sum][back][ok]>=0)return DP[now][sum][back][ok]; int m,res=0; if(now==0)m=40;else m=(int)(sum/now); for(int i=0;i<=m;i++){ if(ok==1&&back>i)continue; if(seq[now]!=-1&&seq[now]!=i)continue; res=(res+solve(now+1,sum+i,i,(back>i)?1:0))%MOD; } return DP[now][sum][back][ok]=res; } public: int theCount(vector<int> seq_) { seq=seq_; n=seq.size(); memset(DP,-1,sizeof(DP)); return solve(0,0,0,0); } };