Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

 | 

2012-07-22

SRM 550 Div1 300 RotatingBot

11:55 | SRM 550 Div1 300 RotatingBot - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 550 Div1 300 RotatingBot - kojingharangの日記 SRM 550 Div1 300 RotatingBot - kojingharangの日記 のブックマークコメント

  • ロボットが長方形の壁の中のどこかにいて、東を向いていて、壁かすでに訪れたとこに当たったら左に回転する。動けなくなったらおわり。
  • 連続して進んだ回数が配列 M で与えられるので、動いた範囲を含む長方形の面積の最小値をもとめる。ありえない場合は-1を返す
  • |M| in [1, 50], M の要素 in [1, 50]
  • |M|≦3のときは無矛盾。
  • |M|＞3のときは M[0]～M[3] で壁の幅と高さが決まる。
  • （M[0]～M[3]が正しくないとするとそもそもいずれM[0]～M[3]の動き検証で矛盾になるので正しいとしていい）
  • 以降シミュレートして矛盾がないか確かめる。
  • 最後以外は止まった時目の前に既に訪れたフラグがないとだめ
  • challenge phase
  • n≧3 のときにM[0]≧M[2]なら矛盾としてるコードを見つけたので 10 6 3 的な無矛盾のテストを投げたところ失敗 -25
  • 実際のところ n＞3 と書いてあって、投げる0.2秒くらい前にいや n＞3 と書いてあるぞなんか変だぞと思ったが右人差し指を止めることはできなかった orz
  • チャレンジは焦るべからずってどっかに書いておこうかなｗ
  • passes system test
class RotatingBot {
	public:
	int minArea(vector <int> M) {
		ll N=M.size();
		if(N==1) return M[0]+1;
		if(N==2) return (M[0]+1)*(M[1]+1);
		if(N==3) return max(M[0]+1, M[2]+1)*(M[1]+1);
		ll W=max(M[0]+1, M[2]+1);
		ll H=max(M[1]+1, M[3]+1);
		ll sX = W-M[0]-1;
		ll sY = M[1];
		VVI w(H+2, VI(W+2));
		REP(x, W+2) w[0][x]=w[H+1][x]=1;
		REP(y, H+2) w[y][0]=w[y][W+1]=1;
		w[sY+1][sX+1]=1;
		int dx[4]={1,0,-1,0};
		int dy[4]={0,-1,0,1};
		REP(i, N) {
			int dir=i%4;
			REP(j, M[i]) {
				sX += dx[dir];
				sY += dy[dir];
				if(w[sY+1][sX+1]) return -1;
				w[sY+1][sX+1]=1;
			}
			if(i!=N-1 && w[sY+dy[dir]+1][sX+dx[dir]+1]==0) return -1;
		}
		return W*H;
	}
};

SRM 550 Div1 500 CheckerExpansion

11:55 | SRM 550 Div1 500 CheckerExpansion - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 550 Div1 500 CheckerExpansion - kojingharangの日記 SRM 550 Div1 500 CheckerExpansion - kojingharangの日記 のブックマークコメント

  • 残り47分ほど
  • シミュレートしてみてフラクタルっぽい
  • フラクタルで検索
  • いくつか名前が出たので全部クリック
  • 図からしてシェルピンスキーのギャスケットである
  • どうやって描くんだこれ
  • 超でかい三角形から始めて再帰的に分割しながら出力範囲に入ってる時だけ書き込んでいくのだろうか
  • BVH みたいに出力範囲と重ならない場合はそれ以上深掘りしなくてよくて出力範囲は充分小さいからそれでいけるんだと思う
  • カタカタカタカタ
  • おわり
  • あとで→ nCr とか偶奇とかそんな方法もあるらすぃ

see

http://d.hatena.ne.jp/kusano_prog/20120721/1342897977

コメント
 |