SRM 499 Div2 950 -> 0 (チャレンジ成功で +250)

2011-03-08

03:09 |

回文となるパターンは以下の２種類。
abc def fed cba のように逆順関係のペアだけからなるパターンと
... aba ... のように真ん中が回文になっていて他は逆順関係のペアからなるパターン
上記それぞれの場合について最大値を求める。
真ん中のカードは１つなので、回文になるカードの中から一番高得点のものを（必要なら）選べばいい。
逆順関係のペアは、高得点順にカードをソートしておき、２重ループでペアかどうかをチェックすればよい（と思う）
カードは１回しか使えないので、使ったかどうかを表す配列で管理する。

で、実際には、残り時間僅かになるまで高得点順にカードをソートする必要性を思いつかなかったため撃沈。
a(1) b(2) a(3) a(4) ... 正解は a(4) b(2) a(3) の並べ方で 9 の簡単なテストケースで失敗することが分かったので、
他の人のプログラムを見てみると同じくソートしてない
ので、a(1) b(2) a(3) a(4) でひたすらチャレンジ。５人撃墜して 250 点得ることに成功ｗｗ
粘ってみるものですね。。

というわけでレートは 1294、Div1 復活となりました。よかったにござい。

↓だめな例です。。

class PalindromeGame {
	public:
	int isV(string& s)
	{
		int a = s.size() / 2;
		REP(i, a) if(s[i]!=s[s.size()-i-1]) return 0;
		return 1;
	}
	int isPair(string& a, string& b)
	{
		REP(i, a.SZ) if(a[i]!=b[a.SZ-i-1]) return 0;
		return 1;
	}
	int getMaximum(vector <string> front, vector <int> back) {
printf("%s %d\n", __FILE__, __LINE__);
		int maxans = 0;
		REP(ca, 2)
		{
			VI used(front.SZ);
			//cout<<used<<endl;
			
			int ansv = 0;
			if(ca==0)
			{
				// find type V
				int ansv_idx = -1;
				REP(i, front.SZ) if(isV(front[i]) && ansv < back[i]) { ansv_idx = i; ansv = back[i]; };
				cout<<ansv<<endl;
				if(ansv_idx!=-1) used[ansv_idx] = 1;
			}
			//cout<<used<<endl;
			
			// find pairs
			int ansp = 0;
			REP(i, front.SZ)
			{
				int maxv_j = -1;
				int maxv = 0;
				FOR(j, i+1, front.SZ)
				{
					if(used[i]) continue;
					if(used[j]) continue;
					if(isPair(front[i], front[j]))
					{
						maxv = back[i]+back[j];
						maxv_j = j;
					}
				}
				if(maxv_j!=-1)
				{
					ansp += maxv;
					used[i] = used[maxv_j] = 1;
				}
			}
			//cout<<used<<endl;
			cout<<ca<<" "<<ansp<<endl;
			int ans = ansv + ansp;
			cout<<ca<<" "<<ans<<endl;
			if(maxans<ans) maxans = ans;
		}
		cout<<maxans<<endl;
		return maxans;
	}