tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

TCO2013 Round2C

ざんねん! tozangezanの TCO2013は おわってしまった!
おや、 tozangezanの ようすが…?

デッデッデッデッデッデー
デッデッデッデッデッデー(ピコーン)
デッデッデッデッデッデー
デッデッデッデッデッデー(ピコーン)
デッデッデッデッデッデー
デッデッデッデッデッデー(ピコーン)
デッデッデッデッデッデー
デッデッデッデッデッデー(ピコーン)
パーンパーンパーン パパパパパパパーン

f:id:tozangezan:20130512031137p:plain
おめでとう! tozangezan
tozangezanに 変態*1した!


今日はMedium openすることにした。
550
この手の問題は真ん中を決めて観葉四分きゅうりを作って足せばよいだろう…
四つ角からDPして累積和を求めるだけ。ただコピペで面倒なことをした。
コピペ余裕勢にはこういうののデバッグは一瞬です><(コピペミスが2箇所あった)

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
class TheMountain{
	public:
	int dpTL[200][200];
	int dpTR[200][200];
	int dpBL[200][200];
	int dpBR[200][200];
	int dat[200][200];
	int sTL[200][200],sTR[200][200],sBL[200][200],sBR[200][200],sT[200][200],sB[200][200],sL[200][200],sR[200][200];
	int minSum(int a,int b,vector<int>c,vector<int>d,vector<int>e){
		for(int i=0;i<c.size();i++)dat[c[i]][d[i]]=e[i];
		dpTL[0][0]=dpTR[0][b-1]=dpBL[a-1][0]=dpBR[a-1][b-1]=1;
	
		
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				if(i){
					if(dpTL[i-1][j]==-1){
						dpTL[i][j]=-1;
						continue;
					}
					dpTL[i][j]=max(dpTL[i][j],dpTL[i-1][j]+1);
				}
				if(j){
					if(dpTL[i][j-1]==-1){
						dpTL[i][j]=-1;
						continue;
					}
					dpTL[i][j]=max(dpTL[i][j],dpTL[i][j-1]+1);
				}
				if(dat[i][j]){
					if(dat[i][j]<dpTL[i][j]){
						dpTL[i][j]=-1;
						continue;
					}
					dpTL[i][j]=max(dpTL[i][j],dat[i][j]);
				}
			}
		}
		for(int i=0;i<a;i++){
			for(int j=b-1;j>=0;j--){
				if(i){
					if(dpTR[i-1][j]==-1){
						dpTR[i][j]=-1;
						continue;
					}
					dpTR[i][j]=max(dpTR[i][j],dpTR[i-1][j]+1);
				}
				if(j<b-1){
					if(dpTR[i][j+1]==-1){
						dpTR[i][j]=-1;
						continue;
					}
					dpTR[i][j]=max(dpTR[i][j],dpTR[i][j+1]+1);
				}
				if(dat[i][j]){
					if(dat[i][j]<dpTR[i][j]){
						dpTR[i][j]=-1;
						continue;
					}
					dpTR[i][j]=max(dpTR[i][j],dat[i][j]);
				}
			}
		}
		for(int i=a-1;i>=0;i--){
			for(int j=0;j<b;j++){
				if(i<a-1){
					if(dpBL[i+1][j]==-1){
						dpBL[i][j]=-1;
						continue;
					}
					dpBL[i][j]=max(dpBL[i][j],dpBL[i+1][j]+1);
				}
				if(j){
					if(dpBL[i][j-1]==-1){
						dpBL[i][j]=-1;
						continue;
					}
					dpBL[i][j]=max(dpBL[i][j],dpBL[i][j-1]+1);
				}
				if(dat[i][j]){
					if(dat[i][j]<dpBL[i][j]){
						dpBL[i][j]=-1;
						continue;
					}
					dpBL[i][j]=max(dpBL[i][j],dat[i][j]);
				}
			}
		}
		for(int i=a-1;i>=0;i--){
			for(int j=b-1;j>=0;j--){
				if(i<a-1){
					if(dpBR[i+1][j]==-1){
						dpBR[i][j]=-1;
						continue;
					}
					dpBR[i][j]=max(dpBR[i][j],dpBR[i+1][j]+1);
				}
				if(j<b-1){
					if(dpBR[i][j+1]==-1){
						dpBR[i][j]=-1;
						continue;
					}
					dpBR[i][j]=max(dpBR[i][j],dpBR[i][j+1]+1);
				}
				if(dat[i][j]){
					if(dat[i][j]<dpBR[i][j]){
						dpBR[i][j]=-1;
						continue;
					}
					dpBR[i][j]=max(dpBR[i][j],dat[i][j]);
				}
			}
		}
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				sTL[i][j]=dpTL[i][j];
				if(i)sTL[i][j]+=sTL[i-1][j];
				if(j)sTL[i][j]+=sTL[i][j-1];
				if(i&&j)sTL[i][j]-=sTL[i-1][j-1];
			}
		}
		for(int i=0;i<a;i++){
			for(int j=b-1;j>=0;j--){
				sTR[i][j]=dpTR[i][j];
				if(i)sTR[i][j]+=sTR[i-1][j];
				if(j<b-1)sTR[i][j]+=sTR[i][j+1];
				if(i&&j<b-1)sTR[i][j]-=sTR[i-1][j+1];
			}
		}
		for(int i=a-1;i>=0;i--){
			for(int j=0;j<b;j++){
				sBL[i][j]=dpBL[i][j];
				if(i<a-1)sBL[i][j]+=sBL[i+1][j];
				if(j)sBL[i][j]+=sBL[i][j-1];
				if(i<a-1&&j)sBL[i][j]-=sBL[i+1][j-1];
			}
		}
		for(int i=a-1;i>=0;i--){
			for(int j=b-1;j>=0;j--){
				sBR[i][j]=dpBR[i][j];
				if(i<a-1)sBR[i][j]+=sBR[i+1][j];
				if(j<b-1)sBR[i][j]+=sBR[i][j+1];
				if(i<a-1&&j<b-1)sBR[i][j]-=sBR[i+1][j+1];
			}
		}
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				sL[i][j]=max(dpTL[i][j],dpBL[i][j]);
				if(j)sL[i][j]+=sL[i][j-1];
			}
			for(int j=b-1;j>=0;j--){
				sR[i][j]=max(dpTR[i][j],dpBR[i][j]);
				if(j<b-1)sR[i][j]+=sR[i][j+1];
			}
		}
		for(int i=0;i<b;i++){
			for(int j=0;j<a;j++){
				sT[j][i]=max(dpTL[j][i],dpTR[j][i]);
				if(j)sT[j][i]+=sT[j-1][i];
			}
			for(int j=a-1;j>=0;j--){
				sB[j][i]=max(dpBL[j][i],dpBR[j][i]);
				if(j<a-1)sB[j][i]+=sB[j+1][i];
			}
		}

		int ret=-1;
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				int now=max(max(dpTL[i][j],dpTR[i][j]),max(dpBL[i][j],dpBR[i][j]));
				//printf("%d\n",now);
				if(dpTL[i][j]==-1||dpTR[i][j]==-1||dpBL[i][j]==-1||dpBR[i][j]==-1){
					continue;
				}
				if(i&&j){
					now+=sTL[i-1][j-1];
				//	printf("%d\n",sTL[i-1][j-1]);
				}
				if(i&&(j<b-1)){
					now+=sTR[i-1][j+1];
				//	printf("%d\n",sTL[i-1][j-1]);
				}
				if((i<a-1)&&j){
					now+=sBL[i+1][j-1];
				//	printf("%d\n",sTL[i-1][j-1]);
				}
				if((i<a-1)&&(j<b-1)){
					now+=sBR[i+1][j+1];
				//	printf("%d\n",sTL[i-1][j-1]);
				}
				if(i){
					now+=sT[i-1][j];
				//	printf("%d\n",sTL[i-1][j-1]);
				}
				if(i<a-1){
					now+=sB[i+1][j];
				}
				if(j){
					now+=sL[i][j-1];
				}
				if(j<b-1){
					now+=sR[i][j+1];
				}
				if(ret==-1)ret=now;
				else ret=min(ret,now);
				
			}
		}
		return ret;
	}
};

250
最短距離-1にしたら落とされた。常識にとらわれていた。意表をつかれた。

1000
提出者多すぎでは?

challenge phase
大量に動いているし自分のも落とされているが何もしない。

System Test
通る

0 + 240.2 + 0 = 240.2(131st)
Rating: 2172 -> 2212 (-60)

目標達成したけど適性レーティン2400くらいだと思っている(自信過剰)なので2400まで上げることにします。

*1:metamorphosis,進化(evolution)は用語の使い方が誤っている