kojingharangの日記

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

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;
	}

ツイートする

SRM 499 Div2 500 -> 411

03:08 |

• ヒントの数字 a, b が異なる場合、a+1 匹の色と b+1 匹の色は異なるので無条件に加算できる。
• ヒントの数字 a, b が同じ場合、最大 a+1 匹が a と答えられる。ので、同じ数字は a+1 個まで１つにまとめられる。
• 以上、map に登録しながらうさぎの数を数える。

class ColorfulRabbits {
	public:
	int getMinimum(vector <int> re) {
		map<int, int> m;
		REP(i, re.SZ)
		{
			if(m.find(re[i]+1) == m.end()) m[re[i]+1] = 0;
			m[re[i]+1]++;
		}
		int ans = 0;
		for( map<int, int>::const_iterator p = m.begin(); p!=m.end(); p++ )
		{
			//cout << p->first << ": " << p->second << " " << endl;
			ans += (p->second + p->first - 1) / p->first * p->first;
		}
		return ans;
	}

ツイートする

SRM 499 Div2 250 -> 217

03:08 |

• ヒントから任意の２つを選ぶ。
• その２つ(a, b)は X+Y と X-Y に対応しているかもしれないので X=(a+b)/2, Y=(a-b)/2 を求める。整数にならないとだめ。
• X*Y の最大値を返す。
• なんかテンパッたらしくとりあえず最初にソートしました。。全然意味ないですね。。。

class SimpleGuess {
	public:
	int getMaximum(vector <int> hints) {
		sort(hints.B, hints.E);
		cout<<hints<<endl;
		int xy = 0;
		REP(i, hints.SZ)
		REP(j, hints.SZ)
		{
			if(i==j) continue;
			int x = hints[i] + hints[j];
			int y = hints[i] - hints[j];
			if(x&1) continue;
			if(y&1) continue;
			if(xy<x*y) xy=x*y;
		}
		return xy/4;
	}

ツイートする