https://codeiq.jp/ace/nabetani_takenori/q957

LongerAndLonger.cs

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		
		//String InputFile="./data.txt";
		//StreamReader SR=new StreamReader(InputFile);
		Stream stdin=Console.OpenStandardInput();
		StreamReader SR=new StreamReader(stdin);

		String s="";
		bool chk=true;
		List<int> L=new List<int>();
		while((s=SR.ReadLine())!=null && s!=""){ 
			var ss=s.Split(' ');
			Sol mySol =new Sol(ss);
			chk=mySol.Solve();
			if(!chk)L.Add(int.Parse(ss[0]));
		}
		Console.WriteLine("");
		Console.WriteLine("Answer--result does not match with expectation -Total {0}",L.Count);
		for(int i=0;i<L.Count;i++){
			Console.Write(i==0?"{0}":",{0}",L[i]);
		}
		Console.WriteLine("");
		
	}
}

class Sol{
	public bool Solve(){
		bool ret=true;
		int N=S.Length;
		int[] dp=new int[N];//n文字目で終わるときの最大項数
		String[] dps=new String[N];//n文字目で終わるときの最終項(小さいほど良い）
		for(int i=0;i<N;i++){
			dp[i]=0;
			dps[i]="";
		}
		
		dp[0]=1;
		dps[0]=S.Substring(0,1);
		
		
		for(int i=0;i<N;i++){
			//最終項に次の1文字を加えても増加列となる（必ず最善手とはならない点に注意）
			if(dp[i]==0 || (i>0 && dp[i]<dp[i-1]) || (i>0 && dp[i]==dp[i-1] && CompAsNum(dps[i],dps[i-1]+S.Substring(i,1))>0)){
				dp[i]=dp[i-1];
				dps[i]=dps[i-1]+S.Substring(i,1);
			}
			
			//次候補があればFeedForwardする

			//先頭0はNGなので次候補なし
			if(i+1<N&&S[i+1]=='0'){
				continue;
			}
			
			//(前回コードの繰り返し部分を少し修正）
			// 次候補を探す(同じ文字数で大きいものが選べるか（無理なら１文字長くする）
			String Next="";
			if(i+1+dps[i].Length-1<N){
				if(CompAsNum(dps[i],S.Substring(i+1,dps[i].Length))<0){
					Next=S.Substring(i+1,dps[i].Length);
				}else if(i+1+dps[i].Length-1+1<N){
					Next=S.Substring(i+1,dps[i].Length+1);
				}
			}
			
			// 次候補を選んだ上で、項数を増やせるか、あるいは項数は変わらなくても最終項が小さい場合だけ更新
			if(Next!=""){
				if(dp[i+Next.Length]<dp[i]+1){
					dp[i+Next.Length]=dp[i]+1;
					dps[i+Next.Length]=Next;
				}else{
					if(CompAsNum(dps[i+Next.Length],Next)>0){
						dps[i+Next.Length]=Next;
					}
				}
			}
		}			
		
		if(dp[N-1]!=expect)ret=false;

//一致しないケースの差異・ログなど
if(!ret){
	Console.WriteLine("Case:{0},expect={1},dp[N-1]={2}",idx,expect,dp[N-1]);

	List<String> LS=new List<String>();
	for(int jj=N-1;jj>=0;){
		LS.Add(dps[jj]);
		jj-=dps[jj].Length;
	}
	for(int jj=LS.Count-1;jj>=0;jj--){
		Console.Write(jj==LS.Count-1?" {0}":",{0}",LS[jj]);
	}
	Console.WriteLine("");
	
	//Console.WriteLine(S);
	//for(int jj=0;jj<N-1;jj++){
	//	Console.WriteLine("{0} {1}",dp[jj],dps[jj]);
	//}
	
}
//ここまで

		return ret;
	}
	
	static int CompAsNum(String s,String t){
		//先頭0のエラーチェック無し（呼び出し側で注意）
		if(s.Length>t.Length)return 1;
		if(s.Length<t.Length)return -1;
		for(int i=0;i<s.Length;i++){
			if(s[i]!=t[i]){
				return s[i]>t[i]?1:-1;
			}
		}
		return 0;
	}
	
	
	int idx;
	String S;
	int expect;
	public Sol(String[] ss_){
		idx=int.Parse(ss_[0]);
		S=ss_[1];
		expect=int.Parse(ss_[2]);
	}

}