kojingharangの日記

Google Code Jam 2011 Round1C -> 40pt(通過)

01:19 |

結果 |OO|O-|O-| 40pt, rank 736 でした。ぎりぎり通過。ほっと一息。

ツイートする

A. Square Tiles

01:19 |

• 青と白のタイルがグリッド状に敷き詰められている。青のとこだけ全部2x2の大きい赤タイルに置き換えたい。全部変えられる？

• こういうやるだけ問題（シミュレーション）が 10 分ちょいでできるようになったのは大きな進歩である。。
• 残り時間たっぷりの状態で残りの２問に取り掛かれるのは精神的にもよいです。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int R,C;
		cin>>R>>C;
		string v[R];
		REP(y, R)
		{
			cin>>v[y];
		}
		int ok=1;
		REP(y, R)
		{
			REP(x, C)
			{
				if(v[y][x]=='#')
				{
					if(y==R-1||x==C-1||v[y][x+1]!='#' || v[y+1][x]!='#' || v[y+1][x+1]!='#')
					{
						ok=0;
						goto END;
					}
					v[y][x]=v[y+1][x+1]='/';
					v[y+1][x]=v[y][x+1]='\\';
				}
			}
		}
		END:;
		cout<<"Case #"<<t+1<<":"<<endl;
		if(ok)
		{
			REP(y, R)
			{
				cout<<v[y]<<endl;
			}
		}
		else cout<<"Impossible"<<endl;
	}
	return 0;
}

ツイートする

B. Space Emergency

01:19 |

• 0..N の星を順に移動したい。星間の距離は与えられる。１時間につき0.5単位進める。
• ブーストを使うと１時間につき１単位進める。
• ブーストは最大 L 個使えて、別々な星のところに置ける。
• ブーストを準備するのに t 時間かかる。スタートと同時に全ブーストの準備を開始できる。
• 最短何時間で星 N に辿りつける？

• Small はブーストの数が最大２なので、総当りで。少し考えてアイデアが出なかったら泥臭く確実に点を取りに行く作戦。
• L==0 の場合、L==1 の場合、L==2 の場合でコードを分けたりして相当泥臭いｗｗ
• 着実に Small クリア。

• Large は、0<=L<=N なので計算量がやばそう。
• 基本的には距離が長いところから順にブーストを割り当てていけばいいが、t が大きい時はブーストが準備できずに通りすぎてしまう。
• その辺考慮してどういう戦略がいいのか思い浮かばなかった。
• C に行って戻ってきて、とりあえず使用ブースト数が L-1 のときの解にブーストを１個最適に追加したものが最適解になりそうな気がしたので１個ずつ追加していく O(N^2) のコードを書いたが Large じゃやっぱり終わらず。

• 解説や上位陣のコードを見ると、単純に t 秒以降にいるエリアの中で距離でソートして短縮できる時間が大きい物順に L 個取るという方法で行けるみたい。
• 言われてみるとそうだ orz
• t 秒以降に行けるエリアは、その前にブーストを置くことで変わってしまうのではないかと思ってわざわざ難しく考えてしまったが、そもそも t 秒より前にブーストを置いても効果がないので杞憂であった。
• このくらい解けないとまずいな....

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(ttt, T)
	{
		ll L,t,N,C;
		cin>>L>>t>>N>>C;
		int v[N];
		REP(i, C) cin>>v[i];
		FOR(i, C, N) v[i]=v[i-C];
		//REP(i, N) cout<<v[i]<<endl;;
		
		ll mintt = -1;
		if(L==0)
		{
			ll tt=0;
			REP(i, N)
			{
				tt+=v[i]*2;
			}
			//cout<<"tt "<<tt<<endl;
			if(mintt==-1 || tt<mintt) mintt=tt;
		}
		else if(L==1)
		{
			FOR(ba, 0, N)
			{
				// use in ba
				ll tt=0;
				REP(i, N)
				{
					if(i==ba)
					{
						if(t<=tt) tt+=v[i];
						else if(t<tt+v[i]*2) tt+= (t-tt) + v[i]-(t-tt)/2;
						else tt+=v[i]*2;
					}
					else
					{
						tt+=v[i]*2;
					}
				}
				if(mintt==-1 || tt<mintt) mintt=tt;
			}
		}
		else
		{
			FOR(ba, 0, N-1)
			FOR(bb, ba, N)
			{
				// use in ba, bb
				ll tt=0;
				REP(i, N)
				{
					if(i==ba||i==bb)
					{
						if(t<=tt) tt+=v[i];
						else if(t<tt+v[i]*2) tt+= (t-tt) + v[i]-(t-tt)/2;
						else tt+=v[i]*2;
					}
					else
					{
						tt+=v[i]*2;
					}
				}
				if(mintt==-1 || tt<mintt) mintt=tt;
			}
		}
		
		cout<<"Case #"<<ttt+1<<": "<<mintt<<endl;
	}
	return 0;
}

ツイートする

C. Perfect Harmony

01:19 |

• 他の人が鳴らす音の周波数が分かっている。
• 自分が鳴らす音を L～H の範囲で決めて、全員とハーモニーするようにしたい。
• ２人がハーモニーしてるとは、２人が出す周波数が「どっちかがどっちかで割り切れる」ことである。

• 8pt だし早速何人か解いてて正解率も高かったので問題を見てみると、Small だけなら総当りでいけそうなのでさくっと書いて点を取りに行く作戦。
• Large は gcd と lcm を求めて L～H に入っているかどうか調べれば行けるかと思ったら全然そうではなくて、どっちかがどっちかで割り切れればよいので gcd～lcm の間にも解が有りうることに途中で気づいた。でお手上げ。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int N,L,H;
		cin>>N>>L>>H;
		int v[N];
		REP(i, N) cin>>v[i];
		
		int ok=0;
		int ans=0;
		FOR(f, L, H+1)
		{
			int lok=1;
			REP(i, N)
			{
				if(f<v[i])
				{
					if(v[i]%f!=0) {lok=0; break;}
				}
				else if(f%v[i]!=0) {lok=0; break;}
			}
			if(lok) {ok=1; ans=f; break;}
		}
		
		if(ok)
			cout<<"Case #"<<t+1<<": "<<ans<<endl;
		else
			cout<<"Case #"<<t+1<<": NO"<<endl;
	}
	return 0;
}

ツイートする