Codeforces Beta Round #23

プログラミング Codeforces コンテスト

続けてます。

順調にレーティング下げてます。
1530 => 1497
Div 2に戻りました。。。
まぁ、これぐらいなら Div 2 Only がきたら余裕で戻れるでしょう。
Div 2 Only がきたら・・・
・・・
次は Div 2 Only 来てくれ〜〜〜！！　←

ということで、また解説です。
詳細は続きを。

解説に入る前に

また今回も問題文などは簡略に書きます。
正式な文や入力の値域などは本家のをちゃんと確認しましょう！
http://codeforces.com/contest/23

A. You're Given a String...

今回の問題は総じて問題文がものすごく短いです。
そして短い分、問題もややこしいことはありません。

問題

問題Aは

文字列が与えられるので、その中で同じ部分文字列の最大の長さを返せ

ってな感じですかね。

問題文にある例を出すと、

ababa

であれば

ababa
ababa

ということで、3(="abc"の長さ)が答えとなります。
同様に

zzz

は

zzz
zzz

ということで2が答えとなります。

解法

これは愚直に、適当な文字列を切りだしてきてそれと同じ文字列が含まれるかどうかでやれば十分ですね。
そして同じ文字列がある中で最大の数字を返せばいいわけです。

解答例

string::substrを使おうかと思ったのですが、切り出しに時間がかかる気がしたので固定長配列使ってます。
＃これのせいでWAを出したのは内緒だ！（ぁ
やり方としては、文字列の長さ-1の数から順に1ずつ減らしながら、この数字分の長さの文字列を2つ切りだして比較するというのを繰り返します。
最大の長さから順に繰り返すので最初に見つかったものの長さが答えとなります。

ということで、以下がコンテスト中に出した答えです。

#include <cstdlib>
#include <cmath>
#include <map>
#include <utility>
#include <set>
#include <sstream>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
using namespace std;

#define	mp				make_pair
#define	pb				push_back
#define	sz(x)			((x).size())
#define	For(i,a,b)		for(int i=(a);i<(b);++i)
#define	rep(i,n)		For(i,0,(n))
#define	all(v)			(v).begin(),(v).end()


int main( void )
{
	char	str[500];
	int		s;

	cin >> str;

	s = strlen( str );
	for( int i = s - 1 ; i > 0 ; --i ) {
		for( int j = 0 ; j + i <= s ; ++j ) {
			for( int k = j + 1 ; k + i <= s ; ++k ) {
				bool	flag = false;
				rep( l, i ) {
					if( str[j+l] != str[k+l] ) {
						flag = true;
						break;
					}
				}
				if( !flag ) {
					cout << i;
					return 0;
				}
			}
		}
	}
	cout << 0;
}

最も外側のiのループが切り出す長さです。
次のjのループが切り出す1つ目の開始位置、次のkのループが切り出す2つ目の開始位置です。
最後のlのループ（マクロを使ってるのでrepになってますが、展開されるとforのループです）が切り出した1つ目と2つ目の比較です。
lのループで一つでも違いがあればflagをtrueにしてそのループを抜けます。
逆に違いがなければfalseのままループを抜けるのでその後のif文で文字数（=i）を出力して終了します。
iのループを全て回りきったときは同じ部分文字列はなかった事になるので0を出力して終わりです。

わかれば簡単ですね。

B. Party

問題文

N人の人がパーティに来ました。
最初にこの中に友達がいない人が帰りました。
その後、残った人の中で友達が1人いる人が帰りました。
次に、残った人の中で友達が2人いる人が帰りました。
以下同様にして、残った人の中で3人、4人、・・・、N-1人と繰り返し、最後までパーティに残った人が最大となる場合は何人かを求めなさい。

という問題です。
問題文は短いのですが、よくわからない問題です。
あ、ちなみに本来の問題ではデータセットはT個与えられるので注意です。

問題の意味

解法に移る前にまずは問題のよりわかりやすい意味を考えましょう。
例えば問題にあるデータを考えます。
3人の人がいて最大最後まで残るのは1人らしいです。
これはどういう状況か。

これを図で表すと以下のようになります。

この図において丸で示したのが人で線で結ばれてる関係が友達関係を表しています。
これを見たらわかるとおり、この問題はグラフの問題に置き換えられそうですね。

さて、なぜこれが答えなのか。
まずこの図において全部で3人（N=3）です。
まず最初に友達が1人もいない人が帰りますが、全員誰かがいるので誰も帰りません。
次に友達が1人いる人が帰ります。
これは誰かというと、

この図で水色を付けた人です。
この人達が帰ると、

という状態になります。
次に残っている人の中で、友達が2人いる人が帰ります。
最初の状態であれば現在残っている人は友達が2人いましたが今残っている中で友達が2人の人はいません。
（全部で1人しかいないのですから当然ですね）
友達がN-1=2人まで終わったのでここで終了です。
現在残っているのは1人、つまりこれがN=3の時に先のルールの元で最後まで残る人が最大となる場合であり答えです。

この問題がどういうのかわかったでしょうか？

解法

問題が大体わかったところ（ということにして）でNが変わったときに最後まで残る人が最大にするにはどうすればいいでしょうか。
途中で帰る条件が友達が（その時点で残っている人の中で）0〜N-1人なので全員残るということは出来ず、必ず誰かが帰ることになります。
これは先のようにグラフを書けば視覚的にもわかりますね。
（重複がないため辺は0〜N-1までしか引けないため。以下ではグラフで説明します。）
では最後までノードが残る条件とはどういうのでしょうか？

先程書いたように必ずあるノードは消えます。
そのことによってそのノードとつながっていた辺は消えるため、消されてしまうノードとつながっていたノードは辺の数が減ります。
このことによって、その時点でノードが消える条件である「i本の辺を持っているノード」のi本以下に辺の数がなればそのノードは最後まで消えることがありません（下図参照）。

つまり、「必ず消えるノード」を最小にしつつ「そのノードが消えたことによって消えなくなる（条件に引っかからなくなる）ノード」を最大にすればいいわけです。
ではどうすればいいでしょか？

実はこの問題はわかれば非常に簡単です。
はっきり言って処理たる処理は一切ありません。
以下にN=4、5、6の場合の解答を示します。
これでわかりますでしょうか？

つまり、あるノードが消えることによって影響が出る（=辺が減る）ノードを最大にすれば、そのノードが消えたときに辺の数が減るノードを最大にすることが出来ます。
あとはこの消えるノードの辺の数と、影響を受けるノードの辺の数の差を1にしておけばノードが消えたときに条件から1少ない辺の数になるためそのノードは消えなくなります。
ある1つのノードだけ辺の数を1つだけ少なくすることは出来ない（辺は常に対になってる）ため、もう1つ消えるノードを用意します。

もうおわかりですね？
答えは N-2 です。
ね？　ものすごく簡単でしょ？
ただし、N=1の場合があるのでこの境界値には気を付けましょう。
N=1の場合は0ですからね？　＠自分
＃・・・くそぅ＞＜。

解答例

問題自体は難しいですが、答え自体がものすごく簡単なんで載せるまでもないですが一応載せておきます。

#include <cstdlib>
#include <cmath>
#include <map>
#include <utility>
#include <set>
#include <sstream>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
using namespace std;

#define	mp				make_pair
#define	pb				push_back
#define	sz(x)			((x).size())
#define	For(i,a,b)		for(int i=(a);i<(b);++i)
#define	rep(i,n)		For(i,0,(n))
#define	all(v)			(v).begin(),(v).end()


int main( void )
{
	int		T, N;

	cin >> T;

	rep( i, T ) {
		cin >> N;
		if( N > 1 )
			cout << N - 2 << endl;
		else
			cout << 0 << endl;
	}
}

＃あとでmax取ればよかったことにtwitterで他の方の発言で気づいた・・・

C. Oranges and Apples

問題

2N-1個の箱があり、それぞれにはりんごとオレンジが入っている。
あなたがすべきことは全てのりんごとオレンジをそれぞれ半分以上を容れられるN個の箱を選び出すことである。

という問題です。
結局問題がよく分からずに終わってしまったのでこの問題は解けませんでした。

ちなみに解けもしなかったのに解説書くのはコンテスト終了後にようやくわかったからです。
ということで、解けなかったけど解説書きます。
ちゃ、ちゃんとAcceptedしたから問題ないんだもん＞＜；
＃人様のソース見てわかっただけだけどね・・・

問題の意味

さてさて、もう少し問題を具体的にしましょう。
ここでもサンプルを使います。

1つめのデータセットは図にすると、

こんな感じですね。
赤丸はりんごを、オレンジ丸はオレンジを表しています。
今はN=2で箱は全部で2N-1=3個、りんごは全部で35個、オレンジは40個あります。
ここで、N=2個の箱を選んでその箱全体がりんご、オレンジそれぞれの半分を持てればいいわけです。
この例では1つ目の箱と3つ目の箱が選ばれています。
なぜなら1つ目の箱と3つ目の箱のりんご、オレンジそれぞれを足すとりんごは30個、オレンジは33個となってそれぞれ半分以上となります。

ちなみに“以上”なので2つ目のデータセット、りんご0個、みかん0個でもちゃんと答えが存在することに注意です。

解法

さて、では答えを考えていきましょう。
（公式の）問題文を読めばわかる通り、そもそも解があるかどうか、そして解があるならその解を出力しなければなりません。
では解がある条件とはどういう条件なのでしょうか？

実はこの問題においては解が“必ず”存在します。
よって“NO”を出力することはありません。
私はこの問題を解けてないので順を追って答えを導くことは出来ません。
よって、いきなり答えから書いていきます。

この答えはまずりんごかオレンジのどちらかで箱を降順にソートします。
以下はりんごでソートした場合で話をします。
次に、ソートした箱で偶数番目の箱のオレンジを全て足します。
この時、この偶数番目のオレンジを全て足しあわせた数が全てのオレンジの総数の半分以上であればその偶数番目の箱の番号が答えとなります。
逆に、半分未満であれば奇数番目の箱と0番目の箱（=りんごが最大の個数の箱）の箱の番号が答えとなります。

解答例

言葉だけじゃ分かりにくいと思うので実際のコードを紹介します。
これはこの解説のために今さっき書いたのでまだ綺麗・・・なはず＞＜；

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;

int main( void )
{
	int		T;

	cin >> T;

	for( int i = 0 ; i < T ; ++i ) {
		int									N;
		vector<pair<pair<int,int>,int> >	box;
		long long				ototal = 0;
		long long				ntotal = 0;

		cin >> N;

		for( int j = 0 ; j < 2 * N - 1 ; ++j ) {
			int		apple, orange;

			cin >> apple >> orange;
			ototal += orange;
			box.push_back( make_pair<pair<int,int>,int>( make_pair<int,int>( apple, orange ), j + 1 ) );
		}

		sort( box.begin(), box.end(), greater<pair<pair<int,int>,int> >() );

		for( int j = 0 ; j < N ; ++j )
			ntotal += box[2*j].first.second;

		cout << "YES" << endl;
		if( ototal <= 2 * ntotal ) {
			cout << box[0].second;
			for( int j = 1 ; j < N ; ++j ) {
				cout << ' ' << box[2*j].second;
			}
		} else {
			cout << box[0].second;
			for( int j = 0 ; j < N - 1 ; ++j ) {
				cout << ' ' << box[2*j+1].second;
			}
		}
		cout << endl;
	}
}
証明

ではなぜこれでいいのかの証明を行ないます。

分かりやすいように以下のように7つの箱があるとします。

まず、どちらかで降順ソートをします。
（先ほどと同じく以下ここではりんごとします。）
その結果がこうなったとします（箱1、箱2、…、箱7は省略して代わりにb0、b1、…、b6という名前を振り付けなおしてます）。

b0がりんごの数が最も多く、b6が最も少ないです。
ちなみに、重複が許されるため数式で書くと以下の関係になります。
b0.Apples \geq b1.Apples \geq b2.Apples \geq b3.Apples \geq b4.Apples \geq b5.Apples \geq b6.Apples

さて、この箱を以下のような分け方で分けます。

  1. 0番目 + 奇数番目

b1とb2、b3とb4、b5とb6を比較したとき各々は左側の方が大きい（または等しい）ので b1 + b3 + b5 \geq b2 + b4 + b6 が必ず成り立ちます。
ここにb0を加えるわけですから 0番目 + 奇数番目 は常にりんごに関しては半分以上あることになります。

  1. 0番目 + 偶数番目

今度はb0とb1、b2とb3、b4とb5を比較します。
すると同様に左側の方が大きい（または等しい）ので b0 + b2 + b4 \geq b1 + b3 + b5 が成り立ちます。
ここにb6を加えるわけですから 0番目 + 偶数番目 もやはりりんごに関して常に半分以上あることになります。

このような方法を取ればどちらでも常にりんごに関して半分以上がとれることがわかりましたね？
では次はオレンジに関してです。

ここで、ある数 A を考えましょう。
A を二つの数 B と C に分割します。
つまり、
A=B+C
です。
ここで、B と C の少なくとも片方は \frac{A}{2} であることはわかりますね？
簡単に証明できて、

  1. B \ge \frac{A}{2} の場合

B 自身が \frac{A}{2} 以上であるため自明

  1. B < \frac{A}{2} の場合

A=B+C より、C=A-B>A-\frac{A}{2}=\frac{A}{2}
ということで、全体を2分した場合は常にどちらかがその半分以上をもつことになります。

さて、オレンジを見てみましょう。
箱は全部でb0〜b6まであります。
ここで、りんごの 0番目 + 奇数番目 の分け方で考えましょう。
この時、0番目 + 奇数番目 と 偶数番目 でオレンジの数が2分されます。
さきほどの証明にあったように、必ずどちらかは全てのオレンジの半分以上となります。
0番目 + 奇数番目 がオレンジの半分以上であればこれが答えなのは自明ですね。

ではこれが半分未満だったらさきほどの証明より 偶数番目 のオレンジの数が半分よりおおいことになります。
ここに 0番目 を足すと、0番目 のオレンジの分だけ増えるので当然オレンジの数は半分以上であることに代わりはありません。
これはりんごでの 0番目 + 偶数番目 になるためりんごの方も半分以上あります。
よって、0番目 + 奇数番目 のオレンジが半分未満であれば 0番目 + 偶数番目 が答えとなります。

以上より、このような分け方をすれば常に両方とも半分以上を含んだ箱の分け方が出来ます。
おわかりいただけましたか？

あとがき

今回は説明に絵を多用しました。
その方が分かりやすいと思ったので。
その分書くのに疲れました。。。orz

あ、ちなみに今回の私の成績は

Ａ　：　WA　→　Accepted
Ｂ　：　WA　→　WA　→　Accepted
Ｃ　：　PE　→　WA

でした。
WAしすぎｗ
でもまぁ B が解けたので結構満足してたりします。

さて、最後に。
書くの遅くなってごめんなしあ＞＜；