Codeforces Round #42

Codeforces

EPOCH@まつやまにkohyatohと参加して優勝してきました！
参加記録は後で書けたら書こうかと思います。


今日はSRMに久々に参加する予定なので、CodeforcesのRound42の問題をちょっと解いて練習した。
ついでに最近まともに問題の記事を書いてないので書き方の復習する。

A. Football

問題概要

2チームがサッカーの試合をする。
n回、ゴールをしたチームの名前が与えられるとき、この試合の勝利チームを出力せよ。

解法

mapで得点をカウントする。

ソースコード
void run()
{
	int n; cin>>n;
	map<string,int> M;
	rep(i,n){
		string s; cin>>s; M[s]++;
	}
	int mx=-1;
	fr(i,M)mx=max(mx,i->second);
	fr(i,M)if(mx==i->second)cout<<i->first<<endl;
}

B. Letter

問題概要

新聞紙を切り貼りした脅迫状のようなものを作る。
元の文章と、作りたい文章が与えられるとき、作りたい文章を作れるかどうか判定せよ。

解法

それぞれのアルファベットの出現回数を数えて、元の文章での出現回数が全て多かったら作れる。

ソースコード
void run()
{
	string in,in2; getline(cin,in); getline(cin,in2);
	char cnt[256]={0};
	rep(i,in.size())if(in[i]!=' ')cnt[in[i]]++;
	rep(i,in2.size())if(in2[i]!=' ')cnt[in2[i]]--;
	
	rep(i,256)if(cnt[i]<0)
	{
		cout<<"NO"<<endl; goto END;
	}
	cout<<"YES"<<endl; END:;
}

C. Lucky Tickets

問題概要

n枚の切符の半分がある。
これを2つずつつないで、Lucky Ticketを作りたい。
Lucky Ticketとは書かれている数字が3の倍数であるような切符である。

解法

Lucky Ticketの作り方は、
(3で割りきれる切符)+(3で割りきれる切符)
(3で割って1あまる切符)+(3で割って2あまる切符)の2通り。


よって3で割った余りが0〜2の切符がいくつあるかそれぞれ数えれば作れる切符の数がわかる。

ソースコード
void run()
{
	int n,cnt[3]={0},t;
	
	cin>>n;
	rep(i,n)cin>>t,cnt[t%3]++;
	
	cout<<min(cnt[1],cnt[2])+cnt[0]/2<<endl;
}

D. Journey

問題概要

nxmマスのグリッドがある。
(1,1)のマスから出発して、各マスをちょうど1度ずつ通り、(1,1)に戻って来るような旅をしたい。

このような旅を可能にするため、任意のマスにテレポーターを置くことができる。
（テレポーターでは好きなマスへジャンプすることができる）


旅を可能にする最小のテレポーターの数と、そのときのパスを出力せよ。

解法

n,mの値で場合わけ。

一辺が偶数で、もう一辺が2以上の長さのとき、

↓←←←
↓→↓↑
↓↑↓↑
↓↑↓↑
→↑→↑

のようなパスが作れる。


一辺の長さが1のとき、
1x1ならテレポーターを最初のマスに置かないと最初のマスを2回訪問できない。
1x2なら→←でおｋ.
1x3以上だと最後のマスにテレポーターを置かないといけない。


両方の辺が奇数のとき、
最後のマスにテレポーターを置かなければならない。


以上をコードにすればよい。

ソースコード
void run()
{
	int n,m; cin>>n>>m;
	
	if(n==1||m==1)
	{
		if(n==1&&m==2||n==2&&m==1)cout<<0<<endl;
		else
		{
			cout<<1<<endl;
			cout<<n<<" "<<m<<" "<<1<<" "<<1<<endl;
		}
		if(n==1)rep(i,m)cout<<1<<" "<<i+1<<endl;
		else rep(i,n)cout<<i+1<<" "<<m<<endl;
		
		cout<<1<<" "<<1<<endl; return;
	}
	
	if(n%2==0||m%2==0)
	{
		cout<<0<<endl;
		if(n%2==0)
		{
			cout<<1<<" "<<1<<endl;
			rep(i,n/2)
			{
				rep(j,m-1)cout<<i*2+1<<" "<<j+2<<endl;
				rep(j,m-1)cout<<i*2+2<<" "<<m-j<<endl;
			}
			rep(i,n)cout<<n-i<<" "<<1<<endl;
		}
		else
		{
			cout<<1<<" "<<1<<endl;
			rep(i,m/2)
			{
				rep(j,n-1)cout<<j+2<<" "<<i*2+1<<endl;
				rep(j,n-1)cout<<n-j<<" "<<i*2+2<<endl;
			}
			rep(i,m)cout<<1<<" "<<m-i<<endl;
		}
	}
	else
	{
		cout<<1<<endl;
		cout<<n<<" "<<m<<" "<<1<<" "<<1<<endl;
		
		rep(i,n)rep(j,m)cout<<i+1<<" "<<(i%2?m-j:j+1)<<endl;
		cout<<1<<" "<<1<<endl;
	}
	
}