JOI本選2018

JOI本選2018(オープン)

参加しました。252点でした。3問目の全探索が通らず。
備忘録のため、コードを貼ります。

1問目

問題:1次元上に$N$個の点が与えられます。$K$個の区間で, 全ての点を覆います。「各区間のmax - min」の和を最小化してください。(最小値 + Kを出力します)
解法:$K=1$の答えからいくつ減らせるかを考えます. これは「隣接する2点の距離」を大きい方から$K-1$個取ったときの和と同じです。$O(NlogN)$


#include 
#include 
#include 
using namespace std;

int n, k;
int t[100000];
int kt[100000];

int main() {
	int i;
	
	cin >> n >> k;
	for (i = 0; i < n; i++) cin >> t[i];
	
	for (i = 0; i < n - 1; i++) {
		kt[i] = t[i + 1] - t[i];
	}
	sort(kt, kt + n - 1, greater());
	
	int ans = t[n - 1] - t[0];
	for (i = 0; i < k - 1; i++) {
		ans -= kt[i];
	}
	ans += k;
	cout << ans << endl;
	return 0;
}

 

2問目

問題:大きさと価値がある商品がN個あります。いくつか選んで、価値の和 - (大きさの最大値 - 大きさの最小値)を最大化してください。
解法:
・$O(N^3)$:大きさの最大値と最小値の組み合わせは$O(N^2)$あります。これを固定すると、取ることができる商品が定まります。
・$O(N^2)$:商品を大きさ昇順でソートしておくと、取ることができる商品は一つの区間で表せます。よって、価値の累積和を用いると、先ほどの解法が$O(N^2)$に落ちます。
・$O(NlogN)$:上記の解法を改善します。商品L~Rを取る場合のスコアf(L, R)は、g(L) + h(R)の形に変形できるので、Rを動かしながらg(L)の最大値を求める感じでできます。


#include 
#include 
#include 
#define int long long
using namespace std;
typedef pair<int, int> P;

int n;
P p[500000];
int a[500000], b[500000];
int rb[500001];
int fl[500001];	//fl[l] = a[l] - rb[l]
int fr[500001];	//fr[r] = rb[r + 1] - a[r]
				//fr[r] + fl[l] = 区間[l, r]を選んだときのスコア

signed main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
	sort(p, p + n);
	for (i = 0; i < n; i++) { a[i] = p[i].first; b[i] = p[i].second; }
	for (i = 1; i <= n; i++) { rb[i] = rb[i - 1] + b[i - 1]; }
	for (i = 0; i < n; i++) fl[i] = a[i] - rb[i];
	for (i = 0; i < n; i++) fr[i] = rb[i + 1] - a[i];
	
	int maxL = fl[0];
	int ans = -1;
	for (i = 0; i < n; i++) {
		maxL = max(maxL, fl[i]);
		ans = max(ans, fr[i] + maxL);
	}
	cout << ans << endl;
	return 0;
}

 

3問目

一言:これはリーディングハードです。誤読しなかった方はプロですね。
問題(間違いの可能性があります):
n行m列のR,G,Bからなる文字列が与えられます。連続する3行または3列を, 互いに重ならないように, かつ上または右から読んだときに"RGB"の順になるように取ります。最大で何組取れるでしょうか。
解法(n,m≦4):取り方を全探索します。なぜか通りませんでした(0点) . 残念.
解法以前の問題ですね。全探索の練習をしてきます。


//縦3マス, または, 横3マスでペアを作る
//上から読んだとき or 左から読んだときに、"RGW"になっているペアの個数を最大化せよ -> ではなくて、"RGW"の順で刺さないとダメらしい。
//という問題。ペアが交差したらNG, 内側から刺してもOKな点に注意.(この誤読で1時間以上溶かした)
#include 
#include 
#include 
#include 
using namespace std;

int h, w;
string s[10];

int dfs(int used) {
	int r, c, res, ret = 0;
	
	for (r = 0; r < h; r++) {
		for (c = 0; c + 2 < w; c++) { 
			if ((used >> (r * w + c)) % 8) continue;
			if (s[r][c] != 'R' || s[r][c + 1] != 'G' || s[r][c + 2] != 'W') continue;
			res = dfs(used + (7 << (r * w + c)));
			ret = max(res + 1, ret);
		}
	}
	
	for (c = 0; c < w; c++) {
		for (r = 0; r + 2 < h; r++) {
			if ((used >> (r * w + c)) & 1) continue;
			if ((used >> ((r + 1) * w + c)) & 1) continue;
			if ((used >> ((r + 2) * w + c)) & 1) continue;
			if (s[r][c] != 'R' || s[r + 1][c] != 'G' || s[r + 2][c] != 'W') continue;
			res = dfs(used + (1 << (r * w + c)) + (1 << ((r + 1) * w + c)) + (1 << ((r + 2) * w + c)));
			ret = max(res + 1, ret);
		}
	}
	return ret;
}

int main() {
	int i;
	cin >> h >> w;
//	if (h > 4 || w > 4) return 0;
	for (i = 0; i < h; i++) cin >> s[i];
	cout << dfs(0) << endl;
	return 0;
}

4問目


問題:N頂点M辺の連結で自己ループや多重辺がない無向グラフが与えられます. $S$->$T$最短路を一つ選び, 経路上の辺のコストを全て0にできるとき, $U$->$V$最短路の長さの最小値を求めてください.
解法(S = U):S = Uの場合, S->V->TがS->Tの最短経路の一つであれば0, そうでなければS->Vの距離が答えです。
解法(M = N - 1):S->T間の最短路が1通りなので, S->T最短路に含まれる辺のコストを0にして, U->V最短路を求めればよいです。
自分の解法(31点):S->T最短路に使われうる辺の集合について, 辺のコストを0にし, U->V最短路を求めました。嘘解法なので、満点は取れません。


//S->T最短経路に使われうる辺をコスト0に置き換えたのち, U->V最短路を求める.
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
typedef pair<int, int> P;

int INF = 1e+15;
int n, m, s, t, u, v;
int a[200000], b[200000], c[200000];
vector et[100000];
vector ec[100000];
int minCost[3][100000];

priority_queue<P, vector, greater

> que; void dijkstra(int minCost[], int start) { int i; for (i = 0; i < n; i++) minCost[i] = INF; que.push(P(0, start)); minCost[start] = 0; while (!que.empty()) { P now = que.top(); que.pop(); int cst = now.first; int pos = now.second; for (i = 0; i < et[pos].size(); i++) { int npos = et[pos][i]; int ncst = cst + ec[pos][i]; if (minCost[npos] > ncst) { minCost[npos] = ncst; que.push(P(ncst, npos)); } } } } signed main() { int i; cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; for (i = 0; i < m; i++) { cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--; et[a[i]].push_back(b[i]); et[b[i]].push_back(a[i]); ec[a[i]].push_back(c[i]); ec[b[i]].push_back(c[i]); } dijkstra(minCost[0], s); dijkstra(minCost[1], t); for (i = 0; i < m; i++) { if (minCost[0][a[i]] + c[i] + minCost[1][b[i]] == minCost[0][t]) { c[i] = 0; } else if (minCost[0][b[i]] + c[i] + minCost[1][a[i]] == minCost[0][t]) { c[i] = 0; } } for (i = 0; i < n; i++) { ec[i].clear(); } for (i = 0; i < m; i++) { ec[a[i]].push_back(c[i]); ec[b[i]].push_back(c[i]); } dijkstra(minCost[2], u); cout << minCost[2][v] << endl; return 0; }


 

5問目

問題:長さ2^Lの配列と, Q個の質問が与えられます. 各質問では0,1,?を用いて該当する要素の番号を指定しています. 該当する要素の和を各質問について答えてください.
制約:L≦20 , Q ≦ 10^6
解法(22点):
「先頭が0の質問, 1の質問, ?の質問」を順に処理することを考えると、?の質問以降では、配列を真ん中で分けて前半i番目と後半i番目を足したものをi番目の要素とした配列に縮約して処理できることが分かります.
よって、これを再帰的に実装します。(計算量は$O(3^L + QL)$くらい)
75点狙えると思いきや、意外とメモリ計算量が多いらしく、通せませんでした。


#include 
#include 
#include 
#include 
using namespace std;
typedef pair<string, int> P;

int l, q;
string s;
vector pre;

void dfs(int cnt, vector v) {
	if (cnt == 0) {
		//cout << v[0] << endl;
		pre.push_back(v[0]);
		return;
	}
	
	int i;
	
	//0
	vector nv;
	for (i = 0; i < v.size() / 2; i++) {
		nv.push_back(v[i]);
	}
	dfs(cnt - 1, nv);
	nv.clear();
	
	//1
	for (i = v.size() / 2; i < v.size(); i++) {
		nv.push_back(v[i]);
	}
	dfs(cnt - 1, nv);
	nv.clear();
	
	//?
	for (i = 0; i < v.size() / 2; i++) {
		nv.push_back(v[i] + v[i + v.size() / 2]);
	}
	dfs(cnt - 1, nv);
	nv.clear();
}

int getId(string query) {
	int i, ret = 0;
	for (i = 0; i < query.size(); i++) {
		ret *= 3;
		
		int val;
		if (query[i] == '0') val = 0;
		else if (query[i] == '1') val = 1;
		else val = 2;
		ret += val;
	}
	return ret;
}

int main() {
	int i;
	
	cin >> l >> q;
	cin >> s;
	
	vector v;
	for (i = 0; i < (1 << l); i++) v.push_back(s[i] - '0');
	dfs(l, v);
	
	for (i = 0; i < q; i++) {
		string query;
		cin >> query;
		cout << pre[getId(query)] << endl;
	}
	return 0;
} 

感想

3問目で嵌ってしまいました. 全探索は書けるようにしたいですね.
最近は, 些細なミス(誤読、変数名間違えなど)が目立っているので, 注意力を鍛えたい.

AOJ 1169. 最強の呪文

問題文

問題文

考えたこと(箇条書き)

start --(S1, S2) --> v --T--> goalと行く場合を考える(vは注目した1頂点. S1,S2,Tは文字列)。
まず、S1 < S2 ⇒ S1 + T < S2 + Tは偽なので、各頂点で辞書順最小を作る方法では「最強の呪文」を作ることができない。(反例:S1 = "a", S2 = "ab", T = "c")
しかし|S1| = |S2|なら上の命題が真になるので、dp[文字数][頂点] = 辞書順最小とすることができる。(今いる頂点と文字数が同じなら, 辞書順最小が良い。)
よって、このDPをする。

最強の呪文が定まる場合、最強の呪文がなす経路はパス(同じ頂点を2度通らない)になることが示せる。(1つのサイクルを含む場合について証明すればよい)
よって, 最強の呪文(dp[--][goal])がサイクルを1つ以上含んでしまった時点で"NO"が確定する。
サイクルを1つ以上含むことで, パスの場合よりも強い呪文を作れるとすると、同じサイクルをn個含む「パスの場合よりも強い呪文」が任意の正整数nについて存在する。すなわち、
パスの場合よりも強い呪文が存在する ⇔ 経路長n未満の場合よりも強い, 経路長n以上2n以下の呪文が存在する
が成り立つ。よって、経路長2n以下まで, すなわち文字数12n以下まで調べれば十分である。
(もう少し考えると、パスの場合よりも強い呪文が存在する ⇔ 文字数6n未満の場合よりも強い, 文字数6n以上12n以下の呪文が存在する. も成り立つことが分かる)

はまった点

・dp[頂点] = 辞書順最小, を立てようとして嵌った。
・dp[枝を通った回数][頂点][長さ] = 辞書順最小, としてMLEした。
・dp[今までの文字数][今いる頂点] = 辞書順最小, としたが, 長さ昇順にループを回さないせいでTLEした。
・文字数 ≦ 6 * nまでしか考えていなくて、WAした。

…考察を詰める集中力がほしい。

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, s, g;
vector<int> et[40];
vector<string> ec[40];
string dp[481][40];

int main() {
    int i, j, k;
    
    while (cin >> n >> m >> s >> g) {
        if (!n) break;
        for (i = 0; i < n; i++) { et[i].clear(); ec[i].clear(); }
        for (i = 0; i <= 12 * n; i++) { for (j = 0; j < n; j++) { dp[i][j] = "{"; } }
        for (i = 0; i < m; i++) {
            int a, b; string spell;
            cin >> a >> b >> spell;
            et[a].push_back(b);
            ec[a].push_back(spell);
        }
        
        dp[0][s] = "";
        for (i = 0; i < 12 * n; i++) {
            for (j = 0; j < n; j++) {
                for (k = 0; k < et[j].size(); k++) {
                    int v = et[j][k];
                    int len = ec[j][k].length();
                    if (i + len > 12 * n) continue;
                    dp[i + len][v] = min(dp[i + len][v], dp[i][j] + ec[j][k]);
                }
            }
        }
        
        int id = 0;
        for (i = 1; i <= 12 * n; i++) {
            if (dp[id][g] > dp[i][g]) id = i;
        }
        if (id >= 6 * n || dp[id][g] == "{") { cout << "NO" << endl; }
        else { cout << dp[id][g] << endl; }
    }
    return 0;
}

感想

複雑な問題設定だと思っていたが、いざ実装してみるととても簡潔に書けたので、良問だなあと思った。
発想というよりは、典型テク(知識, 発想・証明法)を上手く使いこなす系の問題な印象。

AOJ 2708 ABC Gene

問題概要

文字列sについて, 以下の置き換え操作ができる。

  • ‘A’ -> “ABC”
  • ‘B’ -> “ABC”
  • ‘C’ -> “ABC”

‘A’, ‘B’, ‘C'のみから構成される文字列S(|S|≦5000)が与えられるので, “ABC"を何回か操作することで文字列Sにできるか判定せよ。

解法1

逆手順を考える。
最後に操作「x -> “ABC"」をして, 文字列Sを作ったとする。(xは'A', ‘B’, ‘C'のどれか)
このとき、Sに含まれる"ABC"は、操作前は「x」になっている必要がある。

  • 証明:(xを含まない文字列) -> “ABC"と変化することはない。また, x -> "ABC"と変化するので、(xを含む文字列) -> "ABC"と変化する ⇒ 変化前の文字列長 = 1が成り立つ。
  • もちろん, (文字)(文字) -> 「~AB」「C~」といった変化をすることはない。また, “ABC” -> 操作 -> “ABC"と, そのままになることもあり得ない。

よって, 「x -> “ABC"」の逆元は「"ABC” -> x」となる。
(文字列Sに「x -> “ABC"」を適用したあと、「"ABC” -> x」を適用すると、文字列Sが得られる。)

あとは, xを求めればよい。実は、「"ABC"に何回か操作した文字列は必ず、'A'で始まり'C'で終わる」ことから, xは(必要条件で)一意に定まる。

具体的には、以下の場合分けにより, x(の候補)を特定できる。

  1. S = “ABC~"のとき

    • “ABC"に何回か操作した文字列は必ず、'A'で始まり'C'で終わる。よって, x = ‘A'である。
  2. S = “~ABC"のとき

    • 同様の理由で, x = ‘C'である。
  3. それ以外

    • もしx = ‘A'またはx = 'C'のときは, 操作「x -> “ABC"」をしたときに, 先頭または末尾に"ABC"ができてしまう。これは仮定より文字列Sではないので, x = 'B'である。

ここで, 「x = ~である」という文は、正確には「x = ~である必要がある」となる。
すなわち、「"ABC" -> x -> “ABC"」をしたときに、元の文字列が得られることを確かめる必要がある。
(ちなみに, 文字列Sに現れる文字の種類数が2以下の場合は, 解が存在しない。)

あとは頑張るとO(N2)くらいになる。

解法2

「x -> “ABC"」の逆元が「"ABC” -> x」であることを求めてしまえば、あとは適当に逆再生できる。
(文字種が2種類以下⇒No, 「"ABC" -> x -> “ABC"」をしてSが得られる -> 「"ABC” -> x」をSに適用する, を繰り返すだけ)
こちらもO(N2)くらいである。ただし, 計算量の証明には解法1が用いられている。今回はこちらを実装した。

コード

#include <iostream>
#include <string>
using namespace std;

//x -> "ABC"
string operate(string s, char x) {
    string t;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == x) { t += "ABC"; }
        else { t += s[i]; }
    }
    return t;
}

//"ABC" -> x
string inverse(string &s, char x) {
    string t;
    for (int i = 0; i < s.length(); ) {
        if (i + 2 < s.length() && s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
            t += x;
            i += 3;
        }
        else {
            t += s[i];
            i++;
        }
    }
    return t;
}

//is all char appeared?
bool check(string &s) {
    int cnt[3] = {0};
    for (int i = 0; i < s.length(); i++) {
        cnt[s[i] - 'A']++;
    }
    return (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0);
}

int main() {
    string s;
    cin >> s;
    
    while (true) {
        if (!check(s)) { break; }
        if (s == "ABC") { cout << "Yes" << endl; return 0; }
        
        char last = 'z';
        for (char x = 'A'; x <= 'C'; x++) {
            if (operate(inverse(s, x), x) == s) {
                last = x;
                break;
            }
        }
        if (last == 'z') break;
        
        s = inverse(s, last);
    }
    
    cout << "No" << endl;
    return 0;
}

CodeFestival2015本選の問題(解法メモ)

備忘録に解法に至るアプローチを貼っておきます。

 

A: 575判定。cin >> s >> t >> u; cout << (s.length()==5&&t.length()==5&&u.length()==5) ? "YES":"NO" << endl;

 

B: N≧2における合計値の確率分布では平均が一番盛り上がっている。N=1では均一なので1が答え。

 

C: 前から文字列を見ていき、"01"か"10"が見つかったら即座にペアにしていって良い。(010…とあったとき、0「10」…としても「01」0としても前3文字までの分解数は同じ&0「10」とすると残った0とペアになる1が絶対なくなるが「01」0とすれば残った0とペアになる1があるかもしれない -> そのときは得!)などと考えたが、詳しい証明は分からない。

同じ文字を複数のペアに割り振らないように注意する。

 

D: 

①いつだれがどのスイッチを押すかと考えると闇 -> 人数だけ求めればよい!

②N点取る場合…区間が最大M個かぶっていたらM人以上必要、また、M人で十分。

③N-1点取る is 全区間 - {ある一つの区間}

④(ある区間にXを足す, 区間のMaxを求める)というクエリが沢山来る -> StarrySky木

もしくは、N点取る場合に区間が最大M個かぶっているとき、答えがMかM-1であることを利用すればO(N)。(M個区間が被っている時間の(左端, 右端)を覆えるかどうかで判定できる)

 

E:

答えはそんなに長くならない -> 反復深化で全探索しよう!判定は色んな入力を元のコード, 生成したコードの2つに与えて、出力の一致を確かめるなど…。

 

F:

①サイクルにする(グラフ問題にする)

②頂点と辺の通る回数に注目する

③辺を通る回数を考える

④連結判定

 

G:

・列の問題に落とせるらしい??

 

H:

・3枚重ねるのはタブー

・重なって損した量(ペナルティー)で辺を貼ると、最短経路問題になるらしい

競プロ始めたときに埋めた問題

について少しメモしておきます。

競プロを本格的に始めたのはARC(AtCoder Regulars Contest)18からです。
(当時は、B問題のバグに苦しめられていた。)

-1.5年~-0.5年

・JOI予選1~3問目を新しい年のものから埋めていました
(実力、JOI予選200点レベル)

・20行のコードのデバッグに20分以上かけてしまうこともしばしばありました。

-0.5年~0年

JOI予選4~6問目埋め

・このとき、AOJでは30問程度解いていました
・6問目は、2006, 2007年度の予選のものしか解けていませんでした
・一番印象を受けた問題は、「1年生」です。
・この問題をきっかけに、競技プログラミングが好きになりました

JOI本選1~3問目埋め

・楽しい問題、良質な解説…これに手を付けない手はありませんでした
・100枚1冊のレポート用紙に考察を書きこんでいたこと、今でも覚えています
(・2次元累積和に自力で気づいたり、JOI2008本選5番が解けたときは感動した)
(実力、AtCoderRegularsContestB問題が解けるかどうか)

0年~

AtCoderの定期コンテストに参加
・PCK, JOI, ICPC, JAGあたりを中心的に埋めた(AOJ200問解きました)
TopCoder, Codeforces…(深夜コンテストへの参加は不可能でした)
・YukiCoder☆2(1/4くらい面白そうな問題をやりました)

最近

・留年の危機()が迫ってきたので、TopCoder-Div1Easyに絞って練習しています。

(実力、CodeFestival本選5完、ARC2完、TopCoder-緑(1100付近))

最後に

文章がひどいですね…

【備忘録】SRMDiv1Easyを20問埋めてみたら

はじめに

最近、SRMDiv1Easyを20問解いたので、そろそろ何か書き残しておこうと思います。
殆ど自分用なので、かなりひどい文章です。ご容赦ください。

1.SRMを選んだ理由

・読みやすい問題文が多い
・実装が軽い
・良問が多い
・難易度が安定している
・↑のこともあり、TopCoderのレートを上げたくなった
・時間で得点が変わる&英語だから緊張感を得られる

2.Div1Easyを選んだ理由

・最初の方針が合っていれば解ける/嵌ると解けない
 →方針を合わせる練習になる
・1~2時間で解ける問題が半分くらいある
 →ギリギリ解けるのが面白い
・想定解は自分でも分かるくらい簡単
 →解説で分かると悔しい
・実装が軽い
 →お手軽

3.解くときの方針

手順
①1~2時間解いてみる
②解けなければブログ解説の解法だけを見る
③理解できなければ実装もチラ見する
④理解した(クリアだ!簡単だ!と思えた)ら実装して通す(必ず通す)

心得
・証明不能な貪欲は大体嘘貪欲
・簡単な考察&軽実装で解ける(そうでないものは捨てる)
・必ず解けると思う、ただしあきらめも肝心(無理に通そうとしない)
・本番の環境に近づけるため、新しい問題からやる

4.埋める前に思ったこと

・闇雲に埋めてもダメ
・意識して埋めてれば実力は上がりそう
・どのくらい??
・というより長続きするの?(AOJ埋めは3日坊主で終わった)

5.埋めてみて思ったこと

・実力は微妙に上がった気がする
→考察の個数が「1つ」から「3つ」くらいになった
→埋める前に嵌った問題は、やはり嵌ったので微妙
・ギリ解ける問題解いてる時は勝手に集中してた
・細々とだが続いている
SRM(するめ)には中毒性がある

6.最後に

とりあえず、SRM600台は埋める予定。
これで解ける問題が増えたらラッキーなんだけど世の中そんなに甘くなさそうだ。

SRM 658 div1 easy: OddEvenTree

問題概要

N頂点(頂点0~N-1)の木の距離行列xが与えられる。
0 <= i, j <= N-1を満たす全ての(i, j)組について
x[i][j] = 'O'ならば頂点(i, j)間が奇数長
x[i][j] = 'E'ならば頂点(i, j)間が偶数長
が成り立つような、木は存在するだろうか。
存在しなければ{-1}を返し、存在すれば、そのような木を一つ出力せよ。

解法

木が存在するためには、以下の条件を全て満たす必要がある。
・xが対称行列
・全てのiについて、x[i][i] == 'E'
・任意の3頂点A, B, Cについて、AB間の距離 + BC間の距離 + CA間の距離が偶数
・一つ以上'O'が存在
なお、これは十分条件ではない(テストケース88は、これらすべてを満たすが、{-1}を返すべきケース)

上の条件をすべて満たしたとき、木の構築をする。
木の構築は、以下の貪欲アルゴリズムで行い、全部つなげなければ{-1}を返すようにしたら通った。
・頂点0を接続済み頂点にする。他の頂点は「接続済み頂点」ではない。
・全ての頂点を「接続済み頂点」にするか、つなげなくなるまで以下を繰り返す。
 ・「接続済み頂点A」と「接続済みでない頂点B」を見つけたら、頂点AとBを結ぶ。
 ・見つからなければ、{-1}を返す。

・このアルゴリズムを使って木を構築したとき、条件を満たさない木が出来たり、条件を満たす木が存在するのに{-1}を返したり しなかった。理由は良くわからない。

//必要条件だけで枝刈り&条件を満たしたらすぐにつなぐ、という嘘っぽいあれ。
//木の構築中に矛盾が生じたらfalseでも良かったけど、見落としがあると不味いので。
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class OddEvenTree{
    public:
    vector<int> False(){
        vector<int> ret;
        ret.push_back(-1);
        return ret;
    }
    vector<int> getTree(vector<string> x)
    {
        int i, j, k;
        int n = x.size();
        int Ecnt = 0;
        
        for( i = 0; i < n; i++ ){
            for( j = 0; j < n; j++ ){
                if( x[i][j] != x[j][i] )
                    return False();
                if( i == j && x[i][i] == 'O' )
                    return False();
                Ecnt += (x[i][j] == 'E');
            }
        }
        if( Ecnt == 0 ){
            return False();
        }
        for( i = 0; i < n; i++ ){
            for( j = 0; j < n; j++ ){
                for( k = 0; k < n; k++ ){
                    int d = (x[i][j] == 'O') + (x[j][k] == 'O') + (x[k][i] == 'O');
                    if( d % 2 == 1 )
                        return False();
                }
            }
        }
        
        //木の構築(エラーは検出済みなので、これで構築できなかったら最適な構築ではない)
        //ばばーん
        //(貪欲に構築しているため、条件を満たさない木が出来るかもしれない…)
        bool used[50] = {false};
        int sz = 1;
        vector<int> ans;
        
        used[0] = true;
        
        while( sz < n ){
            bool okflag = false;
            for( i = 0; i < n; i++ ){
                for( j = 0; j < n; j++ ){
                    if( used[i] && !used[j] && x[i][j] == 'O' ){
                        used[j] = true;
                        ans.push_back(i); ans.push_back(j);
                        okflag = true;
                        sz++;
                    }
                }
            }
            if( !okflag ){
                return False();
            }
        }
        return ans;
    }
};

提出コードのコメントがひどい