Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

2011-03-08

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

03:09 | SRM 499 Div2 950 -> 0 (チャレンジ成功で +250) - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 499 Div2 950 -> 0 (チャレンジ成功で +250) - kojingharangの日記 SRM 499 Div2 950 -> 0 (チャレンジ成功で +250) - kojingharangの日記 のブックマークコメント

  • 回文となるパターンは以下の２種類。
  • 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 | SRM 499 Div2 500 -> 411 - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 499 Div2 500 -> 411 - kojingharangの日記 SRM 499 Div2 500 -> 411 - kojingharangの日記 のブックマークコメント

  • ヒントの数字 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 | SRM 499 Div2 250 -> 217 - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 499 Div2 250 -> 217 - kojingharangの日記 SRM 499 Div2 250 -> 217 - kojingharangの日記 のブックマークコメント

  • ヒントから任意の２つを選ぶ。
  • その２つ(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;
	}
コメント

2011-02-27

SRM 498→一回やすみ

07:39 | SRM 498→一回やすみ - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 498→一回やすみ - kojingharangの日記 SRM 498→一回やすみ - kojingharangの日記 のブックマークコメント

日本時間深夜２時スタート。目覚ましで一度起きたけど寝てしまって普通に朝おきた（いまここ）

コメント

namakemono_srmnamakemono_srm2011/02/27 20:45Me too...

kojingharangkojingharang2011/03/09 03:11この時間は無理ですね。。まったりいきましょ～

2011-02-11SRM 497 Div1

250 -> 0 (Challenge suceeded)

13:14 | 250 -> 0 (Challenge suceeded) - kojingharangの日記 を含むブックマーク はてなブックマーク - 250 -> 0 (Challenge suceeded) - kojingharangの日記 250 -> 0 (Challenge suceeded) - kojingharangの日記 のブックマークコメント

反省点

DFSでという方針がそもそもだめだったらしい。撃墜された。。たぶん長いDDDDDDDDDDDDDDDDDDDDDDとかが入力されたのだと思う。

DFSのコードがなんかバグってて、いろいろcoutしまくってたのを submit して、入力が長いと標準出力のせいで実行時間制限にひっかかりそうなのでcoutを消してsubmitしたと思ったら修正してないやつをsubmitしてて、合計３回submitして大幅減点。ぬるい。で、結局撃墜。

他の人のコードをみると、DDDが続くかたまりを見つけて、その中だけで順序を反転させる、という処理だけで良いみたい。美しい...

というわけで Div2 に落ちそうです....

class PermutationSignature {
	public:
	int dfs(string& sig, int pos, int start, VI& ans)
	{
		//cout<<"pos "<<pos<<endl;
//printf("%s %d\n", __FILE__, __LINE__);
		int sz = sig.SZ;
		FOR(i, 1, sz+2)
		{
			//cout<<"try pos "<<pos<<" i "<<endl;
			int ok = 1;
			REP(j, pos)
			{
				if(ans[j]==i) {/*cout<<"NG dup "<<ans[j]<<endl;*/ok=0; break;}
			}
			if(!ok) continue;
			if(pos!=0)
			{
				if(sig[pos-1]=='I' && i<ans[pos-1]) {/*cout<<"NG "<<sig[pos-1]<<" "<<i<<" "<<ans[pos-1]<<endl;*/ ok=0;continue;}
				if(sig[pos-1]=='D' && i>ans[pos-1]) {/*cout<<"NG "<<sig[pos-1]<<" "<<i<<" "<<ans[pos-1]<<endl;*/ ok=0;continue;}
			}
			//cout<<"pos "<<pos<<" i "<<i<<" ok "<<ok<<endl;
			//if(!ok) continue;
			ans[pos] = i;
			if(pos==sz)
			{
				cout<<"FOUND "<<ans<<endl;
				return 1;
			}
			int ret = dfs(sig, pos+1, 0, ans);
			if(ret) return 1;
		}
		return 0;
	}
	vector <int> reconstruct(string sig) {
printf("%s %d\n", __FILE__, __LINE__);
		int sz = sig.SZ;
		VI ans(sz+1);
		dfs(sig, 0, 1, ans);
		return ans;
	}

550 -> Opened

13:14 | 550 -> Opened - kojingharangの日記 を含むブックマーク はてなブックマーク - 550 -> Opened - kojingharangの日記 550 -> Opened - kojingharangの日記 のブックマークコメント

なんとなく tagname, color を set にいれて重複をなくして、...とかやるのかなと思いつつとりあえず parse するコードを書いてたら残り５分になって、具体的にどうしたらいいかわからず終了。

反省点

真面目にparseしすぎ。。pos+=7 して id='（ココ）...'に飛んで、とか書くコードで無駄に時間を使ってしまった。

Petrのコードを見たら、全体を繋げて split("[<>]") して、さらに / で始まらなかったら split(" ") して、１番目がID, ２番目がstyle としていた。

確かに id='...' まで全部含めて id と扱ったところでなんの不都合もないわけか。こういう端折るテクニック大事。。

でparseした後の処理はまだ理解できず。

コメント