Codeforces #192 Div1 D. The Evil Temple and the Moving Rocks

かなりパズル的な問題。
http://codeforces.com/contest/329/problem/D

問題

Nが与えられるので、N*Nのグリッドを考える。
このうち任意の数のマスに上下左右を向いた矢印を配置できる。

このうち、任意の矢印を移動対象に指定して以下のシミュレーションを開始できる。

• 移動対象の矢印はその向きに１マスずつ移動していく。
  • 次のマスに進むと画面外に出る場合、シミュレーションは終了する。
  • 次のマスに進むと他の矢印と重なる場合、その矢印は移動を中止する。代わりに重なる対象の矢印が次の移動対象となる。
    • この際、矢印が１マス以上動いた後に他のマスに重なる場合、１回音が鳴る。

X回以上音が鳴るような矢印配置と最初の移動対象を求めよ。

解法

テストケースは３つあり、２つはサンプル解が与えられているので、実質問題はN=100, x=10^5の１問のみ。
N*Nでも10^4しか行かないので、何周かループしなければならない。

回答としては以下のような感じでループを作ればよい。

>>>>>>>>>>>.>.>.>.>.v
^v.<.<.<.<.<<<<<<<<<<
^>>>>>>>>>>.>.>.>.>.v
^v.<.<.<.<.<<<<<<<<<<
^>>>>>>>>>>.>.>.>.>.v
^v.<.<.<.<.<<<<<<<<<<
^>>>>>>>>>>.>.>.>.>.v
^v.<.<.<.<.<<<<<<<<<<
^>>>>>>>>>>.>.>.>.>.v
^v.<.<.<.<.<<<<<<<<<<

１周でN^2/4程度の音が鳴り、N/2周程度できるので、N^3/8程度の音を鳴らすことができる。
実際、下記の(若干矢印の数は適当に配置した)コードでも120149回音がなる。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>x>>y;
	if(x==5) {
		_P(">...v\n");
		_P("v.<..\n");
		_P("..^..\n");
		_P(">....\n");
		_P("..^.<\n");
		_P("1 1\n");
	}
	if(x==3) {
		_P(">vv\n");
		_P("^<.\n");
		_P("^.<\n");
		_P("1 3\n");
	}
	if(x==100) {
		_P(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.v\n");
		FOR(i,49) {
			_P("^v.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n");
			_P("^>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.v\n");
		}
		_P("^<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n");
		_P("1 1\n");
	}
	
}

まとめ

こういう問題がDで出るの珍しいな。