Codeforces Beta Round #25 (Div. 2 Only)

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

むきー＞＜

どう考えても"evenness"が問題です。
本当にありがとうございました。
以下腹が立ったので解説。

A. IQ test

問題

数字の列の中でevennessにおいて他のとひとつ異なるのがある。
それを入力の順番の番号（1ベース）で返せ

さて、辞書で"evenness"を調べてみると

均一、一様

という言葉が出てきます。
次にテストケースを見ると

Input

5
2 4 7 8 10

Output

3

Input

4
1 2 1 1

Output

2

さて、あなたはどういう問題かわかりますか？

解法

言葉の意味とサンプルを見ると「入力の数列はある一定の規則に従っているが1つだけ外れているのがあるからそれを返せ」って思いません？
実はこれは違って「”奇数”と”偶数”において片方が1つだけあるからそれを返せ」です。
これはどう考えても詐欺です＞＜。
はっきり言ってこの問題は「問題文を読み取る事」が問題です。
どうもありがとうごｚ（ｒｙ

解答例

まともに解法を示してないですが問題の意味がわかればそれほど難しいとは思わないので私が投げたソースから判断してください＞＜

#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		a[2] = { 0, 0 };
	int		n;
	vector<int>		v;

	cin >> n;

	rep( i, n ) {
		int		tmp;

		cin >> tmp;
		v.pb( tmp );
		a[tmp%2]++;
	}
	if( a[0] == 1 ) {
		rep( i, n ) {
			if( !( v[i] % 2 ) ) {
				cout << i + 1;
				return 0;
			}
		}
	}
	rep( i, n ) {
		if( v[i] % 2 ) {
			cout << i + 1;
			return 0;
		}
	}
}

B. Phone numbers

問題

n桁の数字が与えられる。
2桁、もしくは3桁ごとに'-'を入れて区切れ。

答えはユニークではないので答えはいくつでもあります。

解法

単に2桁、もしくは3桁ごとに'-'を入れればいいことが味噌です。
何も気にせず2桁ずつどんどん切りましょう。
そして残りが3桁以下になった時点で次のステップに移ります。
残り3桁以下になった時点で考えられるのは以下の2通りしかありません。

  • 残り3桁
  • 残り2桁

なぜなら0桁になる前に2桁になるし、1桁の前には3桁になるので必ず上記どちらかの条件に引っかかります。
あとは残り3桁であれば3桁で、残り2桁であれば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 )
{
	int		n;

	cin >> n;

	while( n > 3 ) {
		char c;

		cin >> c;
		cout << c;
		cin >> c;
		cout << c;

		cout << '-';

		n -= 2;
	}
	rep( i, n ) {
		char c;

		cin >> c;
		cout << c;
	}
}

説明の必要はないですね。

C. Roads in Berland

問題

各街から全て街へ（つまり全ての経路）の最短経路が行列で与えられる。
ここで、道を新しく作る。
そのとき、新しく作った道ごとに全ての最短経路を足しあわせた数を出力せよ。

説明わかりにくいですが、もう書く気がないので本家で確認してください。　←

解法

新しく作った道が現在の同じ2点間を結ぶ道よりも短ければ当然その2点間を結ぶ最短距離は新しく作った道によって更新されます。
問題はこの道によって別の街間の最短距離も更新される可能性があるということです。
ではどうすればいいのでしょうか？

全てのノードから全てへのノードの最短距離を求める方法としてワーシャル-フロイド法がありますがその計算は必要ありません。
なぜなら新しく道を作ったとき、それ以外の道は変わらないためです。
よって、考える必要があるのは新しく作った道を通る経路だけです。
つまり、ある2点間iとjの経路を考えたとき今までの最短距離をi <=> jとして、新しく追加された道がa <=> bとすると新しいi <=> jの最短距離は、

新i <=> j = min( 旧i <=> j, i <=> a <=> b <=> j, i <=> b <=> a <=> j )

となります。
あとはその時点での最短距離を全て足し合わせるだけです。

解答例
#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		n, k;

	cin >> n;

	vector<vector<int> >	r( n, vector<int>( n, 0 ) );

	rep( i, n ) {
		rep( j, n ) {
			int		tmp;
			cin >> tmp;
			r[i][j] = tmp;
		}
	}
	cin >> k;
	rep( i, k ) {
		int		a, b, c;
		long long		res = 0;

		cin >> a >> b >> c;

		a--; b--;
		if( r[a][b] > c ) {
			r[a][b] = c;
			r[b][a] = c;
		}

		rep( j, n ) {
			For( k, j + 1, n ) {
				if( r[j][a] + r[a][b] + r[b][k] < r[j][k] ) {
					r[j][k] = r[j][a] + r[a][b] + r[b][k];
					r[k][j] = r[j][a] + r[a][b] + r[b][k];
				}
				if( r[j][b] + r[a][b] + r[a][k] < r[j][k] ) {
					r[j][k] = r[j][b] + r[a][b] + r[a][k];
					r[k][j] = r[j][b] + r[a][b] + r[a][k];
				}
			}
		}
		rep( j, n ) {
			For( k, j + 1, n ) {
				res += r[j][k];
			}
		}

		cout << res << " ";
	}
}

あとがき

本当は時間ないから解説書くつもりなかったのですが、あまりに（解けない自分に）腹が立ったので書きました。
でも怒りに任せて書いたのでろくな解説になってません。
また時間があるときに気が向いたら直します。
とりあえずごめんなさい＞＜

最後に今回の成績を・・・

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

1470 => 1502

ＣはＡが解けなくて苛立ってろくに直しもせずに何度かやったのでひどいことにｗ
一応青には戻れましたが・・・うーん