Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-07-29SRM477 Div1

SRM477 Div1 250 Islands

| 01:44 | SRM477 Div1 250 Islands - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM477 Div1 250 Islands - SRM diary(Sigmar) SRM477 Div1 250 Islands - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→英文が難しい・・・

→ともかく、六角形の区画で海と陸の区切りとなる辺の数を求めればいいらしい。revenueとか普段使わないような変な単語使わないでほしい。。

→とりあえず横幅を2倍にすれば解けそうな気がする

→横幅2倍にして、奇数行を1文字ずらして、海と陸の境界線をカウントする

→サンプル通る→提出

→・・・

→もう少しよく考えてみよう

→む・・よく見たら・・偶数行の最後にパディングするのを忘れている

→でも、サンプル実行でアクセス違反にならないなぁ

→デバッグしてみると、stringのサイズを超えて添字アクセスしても実行時エラーにはならない

→実際にはもっと多くメモリをアロケートしているからなのかな?

→どうしよう・・再提出するか・・・

→まあ・・・多分大丈夫かな・・・・・・・やめとこ

→500へ


チャレンジフェーズ

→突っ込みどころが思い当たらない

→何もせず


システムテスト

→Passed

→よかった。。後で考えるとやっぱり通るか確実でないものを放置するのは危なかった。本来なら再提出ですね。


以下、ソースです。

class Islands { 
public: 
  int beachLength(vector <string> kingdom) { 
    int res=0; 
    int h=kingdom.size(), w=kingdom[0].size(); 
    int w2=w*2+1; 
    int dr[4]={1,0}, dc[4]={0,1}; 
    vector <string> k2; 

    for(int i=0; i<h; i++) { 
      k2.push_back(string()); 
      if(i%2==1) k2[i].push_back('0'); 
      for(int j=0; j<w; j++) { 
        k2[i].push_back(kingdom[i][j]); 
        k2[i].push_back(kingdom[i][j]); 
      }
      //本来ならここにk2[i].push_back('0')のような文を入れる 
    } 

    for(int i=0; i<h; i++) { 
      for(int j=0; j<w2; j++) { 
        for(int l=0; l<2; l++) { 
          int nr=i+dr[l], nc=j+dc[l]; 
          if(nr<0 || nr>=h || nc<0 || nc>=w2) continue; 
          if(k2[i][j]=='#' && k2[nr][nc]=='.') res++; 
          else if(k2[i][j]=='.' && k2[nr][nc]=='#') res++; 
        } 
      } 
    } 
         
    return res; 
  } 
};

SRM477 Div1 500 PythTriplets

| 01:44 | SRM477 Div1 500 PythTriplets - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM477 Div1 500 PythTriplets - SRM diary(Sigmar) SRM477 Div1 500 PythTriplets - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→またもや英語が・・・難しい。legって脚かと思いきやここでは三角形の辺のことを言ってるんですかね。

→つまり、ピタゴラス数となる3つの数の組のうちの小さい方の2つの数の組の数を最大化するということですね。

→うーん・・DPとかですかね・・

→いや・・違うな。。ペアリングの数を最大化するのだから、2部グラフの最大マッチングの可能性が高いと見た

→どうやって2部グラフにするのか。。

→とりあえず全部の要素をソース側とシンク側において、あとで2分の1すれば良いような気もするけど・・何となく反例がありそうな気もするなあ・・(←実はこれでも良かったみたい)

→何となくピタゴラス数の一覧を見ていると、必ず偶数と奇数の組み合わせになるような気がしてきた

→あまりよろしくないけどGoogle先生の力を借りるか・・

→必ず偶数と奇数のペアになるという証明を発見

→マッチングのプログラムを書く

→サンプル通る→提出

→うーん・・間違ってないよなあ・・さすがに偶奇ペアのところは大丈夫だろうし、最大マッチングもライブラリコピペだし・・

→要素数も最大200だし。。→最大ケース試す→全く問題なし

→単純なプログラミングミスもないな。よし!問題なし!久々に500ができた!


チャレンジフェーズ

→最大ケースで落ちそうな人は・・・1人いたが速攻で誰かに落とされる

→他の人のでも読んでみるか

→何か他の人はGCDとかしてるなぁ

→あれ?GCDっていらないんだっけ??

→あれ?問題文にもきっちり書いてある。というか、証明のほうにもきっちり互いに素の場合だけって書いてある(当たり前だが・・)

→あれ?あれ?あれ?何で僕のプログラムはGCD取ってないの??なんで???

→(T-T)...

→なぜかチャレンジを2回受けるものの落とされずに残る


システムテスト

→当然Failed


以下、GCDを取って修正したソースです。

なんというか、ついこないだちゃんと問題文は読まないと、という教訓を得たばかりなのに、なぜ見落としが出るのかよく分からないです。

チェック表でも作って確認するしかないかなぁ・・・

vector <int> val;
vector <int> dad;
vector <vector <bool> > am;
vector <vector <int> > eflow, esize;
const ll unseen=-2000000000;
const int INF=2000000000;

vector <int> strspltoi(string str, const char delim) {
    vector <int> result;
    int i=0, ssize=0, prev=-1;
    string tmps;

    ssize=str.size();

    for(i=0; i<ssize; i++) {
        if(str[i] == delim) {
            tmps.assign(str, prev+1, i-prev-1);
            result.push_back(atoi(tmps.c_str()));
            prev=i;
        }
    }
    tmps.assign(str, prev+1, ssize-prev-1);
    result.push_back(atoi(tmps.c_str()));

    return result;
}

ll gcd(ll a, ll b) {
	ll n=a;
	ll m=b;
	ll tmp;

	while(m) {
		n=n%m;
		tmp=n;
		n=m;
		m=tmp;
	}

	return n;
}

class PythTriplets {
public:
	//ソースからシンクへの経路選択関数(経路の流量が最大化されるように経路を選択)
	bool visit(int sc, int sk) {
		int m, c;
		priority_queue <pair<int, int> > q;
		pair <int, int> qt;

		q.push(make_pair(INF, sc));
		dad[sc]=sc; val[sc]=INF;
		while(!q.empty()) {
			qt=q.top(); q.pop();
			m=qt.second;
			if(val[m]>qt.first) continue;
			for(int i=0; i<(int)am[m].size(); i++) {
				if(m==i || !am[m][i]) continue;
				c=-eflow[m][i];
				if(esize[m][i]>0) c+=esize[m][i];
				c=min(qt.first, c);
				if(val[i]<c && c>0) {
					q.push(make_pair(c, i));
					val[i]=c; dad[i]=m;
					if(i==sk) return true;
				}
			}
		}

		return false;
	}

	//最大流を求める関数(流量を増やせる限り経路選択関数をコール)
	void maxflow(int sc, int sk) {
		int x, y;

		while(visit(sc, sk)) {
			y=sk; x=dad[sk];
			while(y!=sc) {
				eflow[x][y]+=val[sk];
				eflow[y][x]-=val[sk];
				y=x; x=dad[y];
			}
			dad.assign(dad.size(), -1);
			val.assign(val.size(), unseen);
		}
	}

	int findMax(vector <string> st) {
		int res=0;
		string s;
		vector <int> stick;

		for(int i=0; i<(int)st.size(); i++) s+=st[i];
		stick=strspltoi(s, ' ');

		int scsize=stick.size(), sksize=stick.size();
		int sc, sk;

		dad.assign(scsize+sksize+2, -1);
		val.assign(scsize+sksize+2, unseen);
		am.assign(scsize+sksize+2, vector <bool>(scsize+sksize+2, false));
		esize.assign(scsize+sksize+2, vector <int>(scsize+sksize+2, 0));
		eflow.assign(scsize+sksize+2, vector <int>(scsize+sksize+2, 0));

		//2部グラフの作成
		sc=0; sk=scsize+sksize+1;
		for(int i=0; i<scsize; i++) {
			am[sc][i+1]=true;
			esize[sc][i+1]=1;
			am[i+1][sc]=true;
			esize[i+1][sc]=-1;
		}
		for(int i=0; i<sksize; i++) {
			am[i+scsize+1][sk]=true;
			esize[i+scsize+1][sk]=1;
			am[sk][i+scsize+1]=true;
			esize[sk][i+scsize+1]=-1;
		}

		for(int i=0; i<scsize; i++) {
			if(stick[i]%2==0) continue;
			for(int j=0; j<scsize; j++) {
				if(stick[j]%2==1) continue;
				if(gcd(stick[i], stick[j])>1) continue;//この行が抜けてました
				ll sq=(ll)stick[i]*stick[i]+(ll)stick[j]*stick[j];
				ll rt=(ll)sqrt((double)sq);
				if(rt*rt==sq) {
					am[1+i][1+scsize+j]=true;
					esize[1+i][1+scsize+j]=1;
					am[1+scsize+j][1+i]=true;
					esize[1+scsize+j][1+i]=-1;
				}
			}
		}

		//最大流関数コール
		maxflow(sc, sk);

		//最大流を合計
		for(int i=0; i<scsize+sksize+1; i++) {
			if(am[sc][i]) res+=eflow[sc][i];
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100729