SRM 589 DIV1 本番 - antaの競技プログラミング練習日記

一番自明なことに気づかないとかChallengeしない主義者！とか

Coding

Easy (250)

なんか変な解法を思いついて、それはExampleを通るものの、まあ嘘だなと思い考えなおす。
考えてみた：「文字aを文字bに変え、その後に文字bを文字cに変えることは意味がない」
考え：a→bのコストがx、b→cの独立のコストがyだとして、a→b, b→cの順番にやると一回目でx、二回目で(x+y)のコストがかかってしまう。それは独立にやった時の(x + y)以下なので、意味がない。
さて、推移が無いとするとサイクルも無いので、全ての書き換えを独立に考えることが出来る。
そうすると、書き換えがStarグラフの集合のグラフになる。
集合はUnionFindでやって、それぞれのStarに対して真ん中をgreedyに選べば良い。
結構時間かかってしまった。

Medium (450)

最初にどうせ2部マッチングとかフローとかだろ、とか思ってた。
しかしどうも考えをまとめることができなくて、フローのグラフを試行錯誤したりして時間を潰していた。
そのうち、これ頂点被覆か？と思った。
それぞれの色に対して方向を全探索して、「辺があって向きが同じ2点」に辺を張る。
でも頂点被覆とかNP-Hardだろーとか思って指数時間アルゴリズムが問題の制約でなんかあれなのかなーとか思いながらタイムアウト。

結局、本当に自明に二部グラフなのであった。
何故なら、3つとも同じ向きということは無意味だからでからである。絶対向きをバラけさせたほうが良いので。これが感じられなかった。
そして、頂点被覆と考えても独立集合と考えても(たぶん)良い。

Challenge

Easy絶対落とせるだろうなーと眺めて、怪しいgreedyをいっぱい見つける。
しかし考えているうちにどんどん他の人に落とされていく。
他の人のChallengeも遅くて、考えてケースを作れる十分な時間の余裕があったのにもかかわらず、何もできない。
結局他の人に8Challengeをされた。

SystemTest

Easyは通った。みんなMedium解けてるし、Easy点数低すぎる。

結果

Easy: 183.16/250
Challenge: 0/0 = +0
Division Place: 261/758
Rating: 2045→2015

レーティングは順調に下がっていて

コード

Easy

#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define INF 0x3f3f3f3f

using namespace std;
typedef vector<int> vi;  

struct UnionFind {
	vector<int> data;
	UnionFind(int size_) : data(size_, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

struct GooseTattarrattatDiv1 {
	int getmin(string S) {
		int n = S.size();
		UnionFind uf(26);
		rep(i, n/2) {
			char a = S[i], b = S[n-i-1];
			uf.unionSet(a-'a', b-'a');
		}
		int r = 0;
		for(int a = 0; a < 26; a ++) if(uf.root(a) == a) {
			vi v;
			for(int b = 0; b < 26; b ++) if(uf.findSet(a, b))
				v.pb(b);
			int x = INF;
			each(i, v) {
				int y = 0;
				each(j, v) if(*i != *j) y += count(all(S), (char)('a' + *j));
				x = min(x, y);
			}
			r += x;
		}
		return r;
	}
};