第二回ニコ生オープン!!

TopCoder 参加記録

第二回も参加したよ。

(詳細：http://com.nicovideo.jp/community/co329335 )
今回も主催の診断人さん、参加者のみなさんお疲れ様でした。

Result

8位 rankalee 236.82 / 444.20 / 0.0(challenge succeeded) / 0 challenge 681.02

みんな1000通ってる……くやしいなー。
自前でテストケースを考えて作るようにしないとこういうことがまた起こりそう。


と、というかW=H=1000のケースも一応テストしたつもりだったんだけどorz
プラグインを改造しないといけないな……情報収集しよう。

Easy SumRectangle

問題

何かの数字の書いてある同じ大きさの正方形を、長方形の形に並べたSum Rectangleがある。このSum Rectangleは次の条件を満たす。
一番右の列、下の列を除き、ある正方形に書かれた数字は、その正方形の右、下、右下の正方形に書かれた数字の和に等しい。


一番左の列および一番上の行の数字が全て与えられたとき、右下の正方形の数字を求めよ。

試行錯誤

読んだ。ちょっと良くわからないのでサンプルを見る。
ある正方形の数字はその下、右、右下の3つの数字の和になってるってことか。
左上から一マスずつ順に求めていけばおｋ.


問題文に不気味な一文が。右下がユニークに決まらないときは0を返せ。
あれ？ユニークに決まらないことないよな？考え方間違ってる？


まあいいやサンプル合った。変なケースもないっぽいし送信。

ソースコード
class SumRectangle {
	public:
	int getCorner(vector <int> leftColumn, vector <int> topRow) 
	{
		int h=leftColumn.size(),w=topRow.size();
		vector<vi> sq(h,vi(w));
		
		rep(i,h)sq[i][0]=leftColumn[i];
		rep(i,w)sq[0][i]=topRow[i];
		
		for(int i=1;i<h;i++)for(int j=1;j<w;j++)
		{
			sq[i][j]=sq[i-1][j-1]-sq[i][j-1]-sq[i-1][j];
		}
		return sq[h-1][w-1];
	}
};

Medium WhatsThisChord

問題

ギターのそれぞれの弦はフレットを抑えないとE,A,D,G,B,Eの音が出る。
1番目のフレットを抑えると、出る音は半音あがり、i番目のフレットを抑えると半音i個分出る音が上がる。


各弦の押さえるフレットの番号が与えられたとき、ギターの出す和音のコードを求めよ。
ただし-1はその弦を弾かないことを表す。

  • 音階はC,C#,D,D#,E,F,F#,G,G#,A,A#,Bの12個で、Bの次はCに戻る。
  • 考える和音はMajorとMinorのみで、それぞれ音の間隔がX,X+4,X+7およびX,X+3,X+7である。
  • ギターの出す和音が上の和音以外のときは空の文字列を返せ。
試行錯誤

問題文長いｗああでも音階とギターの説明してるだけか。


和音全部作ってmapに入れて参照すればいいんじゃないか。
書く。サンプル通った。送信。

ソースコード
string name[]={"A","A#","B","C","C#","D","D#","E","F","F#","G","G#"};
int open[]={7,0,5,10,2,7};
map<vi,string> cd;

class WhatsThisChord {
	public:
	string classify(vector <int> chord) 
	{
		rep(i,12)
		{
			vi v;
			v.pb(i),v.pb((i+4)%12),v.pb((i+7)%12);
			sort(all(v));
			cd[v]=name[i]+" Major";
			
			v.clear();
			v.pb(i),v.pb((i+3)%12),v.pb((i+7)%12);
			sort(all(v));
			cd[v]=name[i]+" Minor";
		}
		set<int> key;
		rp(i,chord)if(chord[i]>=0)key.insert((open[i]+chord[i])%12);
		
		vi v;
		fr(i,key)v.pb(*i);
		if(cd.count(v))return cd[v];
		return "";
	}
};

Hard CuttingGlass

問題

芝刈り……ではなくガラスを切る問題。
ガラスは幅W高さHの長方形で、カッターは最初(startX,startY)の座標にいる。
カッターの動かし方が次のような文字列で与えられるとき、カッターを動かした後でガラスが何枚のパーツに分かれたかを求めよ。

  • 'U'：カッターを上へ動かす(y座標-1)
  • 'D'：下へ(y座標+1)
  • 'L'：左へ(x座標-1)
  • 'R'：右へ(x座標+1)

W,H≦1000である。

試行錯誤

何のアルゴリズムの問題だろう。包除原理か何かか？
うん？1000x1000だと？これ単純に実装すればいいんじゃないだろうか。


カッターの切った線を覚えておいて、くっついてるガラスをdfsで求めて数えてやればパーツの数がわかる。最大ケースでたった100万だしおｋな気がする。


かりかり。書いた。サンプルも合った。自分にしてはめずらしく順調。
最大ケースをテスト。エラー出てないよな。送信。あれこれ2位じゃね？ｗ

ソースコード
int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int w,h;
string pg;
vector<vector<bool> > tate,yoko,V;

class CuttingGlass {
	public:
	int pieces(int W, int H, int x, int y, vector <string> program) 
	{
		w=W,h=H;
		pg=accumulate(all(program),string());
		
		tate=vector<vector<bool> >(h,vector<bool>(w+1));
		yoko=vector<vector<bool> >(h+1,vector<bool>(w));
		V=vector<vector<bool> >(h,vector<bool>(w));
		
		//cut
		rp(i,pg)
		{
			if(pg[i]=='U'||pg[i]=='D')
			{
				if(pg[i]=='U')
				{
					tate[y-1][x]=1;
					y--;
				}
				else
				{
					tate[y][x]=1;
					y++;
				}
			}else
			{
				if(pg[i]=='L')
				{
					yoko[y][x-1]=1;
					x--;
				}
				else
				{
					yoko[y][x]=1;
					x++;
				}
			}
		}
		
		//fill
		int ans=0;
		rep(i,h)rep(j,w)if(!V[i][j])ans++,dfs(i,j);
		
		return ans;
	}
	void dfs(int y,int x)
	{
		V[y][x]=1;
		rep(d,4)
		{
			int ny=y+dy[d],nx=x+dx[d];
			if(ny<0||nx<0||ny>=h||nx>=w)continue;
			if(d==0&&yoko[y][x]||d==1&&tate[y][x]||
				d==2&&yoko[y+1][x]||d==3&&tate[y][x+1])continue;
			
			if(!V[ny][nx])dfs(ny,nx);
		}
	}
};

（Challenge Succeeded）

Challenge Phase

1000落とされた；；
スタックオーバーフローだったらしい。あれ、最大ケース試したはずが……
入力ミスでちゃんと試せてなかったぽい？


しょっく。
再帰dfsではなくstackまたはqueueを使えという問題だったようだ。
テストはしっかりしろ！

System Test

250,500は何とか通った……よかった。