Codeforces Round #16 (Div2 only)

Codeforces 参加記録

今回からDiv2 onlyのコンテストにも（レーティング変動なしで）レーティング1500以上の人も参加できるようになったみたい。

Result

27位(Div1の人含) rankalee 5AC penalty272
00:03 00:21(2WA) 00:29 01:11(1WA) 01:08(1TLE)

A. Flag
問題

nxmマスの色のついた小正方形からなる旗が、ストライプであるかどうかを判定せよ。
ただし、ストライプであるとは、

  • 同じ行にあるマスの色は全て等しい
  • となりあう列の縞の色は全て異なる

という条件を満たすものをいう。

試行錯誤

条件にしたがって実装。
送信。AC.

ソースコード
void run()
{
	int h,w; cin>>h>>w;
	vs str(h);
	
	bool ok=1;
	
	rep(i,h)
	{
		cin>>str[i];
		rp(j,str[i])if(str[i][j]!=str[i][0])ok=0;
	}
	for(int i=1;i<h-1;i++)if(str[i-1][0]==str[i][0]||str[i+1][0]==str[i][0])ok=0;
	
	cout<<(ok?"YES":"NO")<<endl;
}
B. Burglar and Matches
問題

m種類のマッチ箱の入ったコンテナがある。
i番目のマッチ箱がa[i]個あり、a[i]個のそれぞれに等しくb[i]本のマッチ棒が入っている。


今、n個のマッチ箱の入るリュックサックにn個のマッチ箱を選んで入れたい。
このときリュックに入る最大のマッチの本数を求めよ。
マッチ箱の中のマッチを移し変えてはならない。


n≦2*10^8,
1≦m≦20,
1≦ai≦10^8,
1≦bi≦10である

試行錯誤

ナップサック問題かー（←誤読）
aが大きくてmが小さいから全通り試せって問題だな！


ビット使って書いた。サンプル合わない。
あ、1つの箱に何個も入れる場合あるのか。じゃあ深さ優先探索に書き換え。


あれ？サンプル合わないぞ。問題を読み直す。
あ、ああ貪欲につめるだけか……orz


送信。WA.
あれ？ひょっとしてlong longいる？訂正。送信WA.


なんぞ。あ、ループの回数でmとnミスってる箇所あるorz
もう！！！！UAPCの失敗から学べよ！！！！


送信。AC.

ソースコード
int n,m;
pi p[20];

void run()
{
	cin>>n>>m;
	rep(i,m)
	{
		int a,b;
		cin>>a>>b;
		p[i]=mp(b,a);
	}
	sort(p,p+m,greater<pi>());
	ll ans=0;
	rep(i,m)
	{
		ll t=min(p[i].second,n); //注：llは必要ない
		ans+=t*p[i].first;
		n-=t;
	}
	
	cout<<ans<<endl;
}

C. Monitor

貪欲法のBでハマるとか酷いｗ

問題

縦a,横bのパネルを切って縦x:横yのパネルで、
縦横の辺の長さが整数かつ、面積が最大になるようなものを作りたい。
そのようなパネルの縦の長さと横の長さを求めよ。不可能なときは0 0を出力せよ。


1≦a,b,x,y≦2*10^9である。

試行錯誤

えーと？不定方程式を解くのかな？でも10^9だからループとかしてると死ぬ。
素因数分解……


あ、いや縦横の辺の長さをmxとmyとしてmx≦aかつmy≦bな最大のmを求めればいいだけか。（x,yはあらかじめgcdで割る）
これで求めると切り出せない場合もm=0になって含まれる。


送信。AC.

ソースコード
void run()
{
	int a,b,x,y; cin>>a>>b>>x>>y;
	int g=__gcd(x,y);
	x/=g,y/=g;
	int m=min(a/x,b/y);
	
	cout<<m*x<<" "<<m*y<<endl;
}

D. Logging

なんか今回Div2 onlyにしても問題簡単？

問題

[date:time]: messageの形でログが与えられる。
date:timeは12時間形式で12:13 a.mのように指定される。
ログが時間順に並んだ後で日付を削除されている時、全てのログを出力するには最短で何日間かかるかを求めよ。


1分以内に10個より多くのログは出力されない。

試行錯誤

まず12時間形式の時間を0:00からの経過分で表す。
(12%h)*60+mと。


で、時間が逆転してたり、time[i]>time[i-1]の連続数を数えて10以上だったら日付をめくればいいのかな（←間違いtime[i]==time[i-1]の連続数を数えるべき）


書いた。送信。WA.なんぞー。
よくわからないので次の問題解いてからにしよう。

E. Fish

あ、iwi先生が40分かからずに全部の問題解いてる。すげーｗ

問題

湖にn匹の魚が棲んでいる。
一日の終わりに湖の中の魚のうちどれか二匹がランダムに選ばれ、
選ばれた魚をiとjとすれば、確率pijで1匹目が2匹目を食べ、
確率1-pijで2匹目が1匹目を食べる。


これが湖に二匹以上魚がいる限り続けられるとき、それぞれの魚が生き残る確率を求めよ。

n≦18である。

試行錯誤

nが18だからビットDPすればよさげ。
計算量はn^3*2^nくらいだから間に合いそう。


書いた。サンプル合わない。あぁ魚が1匹になるのはn日目じゃなくてn-1日目かｗ
訂正。送信。


TLE.
あれ、これ確率が0になるような配列もわざわざ呼び出すとダメ？


うーん。ビットを選ぶ部分をnext_permutation使って書き直そう。
訂正。一発でサンプルもあった。


送信。AC.

ソースコード
int n;
double p[18][18];
double dp[20][1<<18];

void run()
{
	cin>>n;
	rep(i,n)rep(j,n)cin>>p[i][j];
	rep(i,20)fill_n(dp[i],1<<n,0);
	
	dp[0][(1<<n)-1]=1;
	for(int i=1;i<n;i++)
	{
		int tmp[n];
		rep(j,n)tmp[j]=j>=i-1;
		
		do
		{
			int bit=0;
			rep(j,n)bit*=2,bit+=tmp[j];
			
			double meet=(n-i+1)*(n-i)/2.0;
			
			rep(j,n)if(bit&1<<j)rep(k,j)if(bit&1<<k)
			{
				dp[i][bit^1<<j]+=dp[i-1][bit]*p[k][j]/meet;
				dp[i][bit^1<<k]+=dp[i-1][bit]*p[j][k]/meet;
			}
		}while(next_permutation(tmp,tmp+n));
	}
	
	rep(i,n)cout<<dp[n-1][1<<i]<<(i==n-1?"\n":" ");
}

E（再）

あー、1分間に10個のログまで、だからtime[i]==time[i-1]のときに連続を数えるのか。
訂正。


送信。AC.

ソースコード
void run()
{
	int n; cin>>n; cin.ignore();
	int time[100];
	
	rep(i,n)
	{
		string s,a,b;
		getline(cin,s);
		a=s.substr(1,2); b=s.substr(4,2);
		
		int h,m; stringstream(a)>>h; stringstream(b)>>m;
		time[i]=(h%12)*60+m;
		if(s[7]=='p')time[i]+=720;
	}
	
	int ans=1,suc=0;
	for(int i=1;i<n;i++)
	{
		if(time[i]<time[i-1])
		{
			suc=1;
			ans++;
		}
		else if(time[i]>time[i-1])
		{
			suc=1;
		}else
		{
			suc++;
			if(suc>10)
			{
				suc=1;
				ans++;
			}
		}
	}
	cout<<ans<<endl;
}

すごくアドホックに直した感が出てるｗ