Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-08-31SRM516 Div1

SRM516 Div1 250 NetworkXOneTimePad

| 22:16 | SRM516 Div1 250 NetworkXOneTimePad - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM516 Div1 250 NetworkXOneTimePad - SRM diary(Sigmar) SRM516 Div1 250 NetworkXOneTimePad - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

適当に平文と暗号文をXORして鍵の候補を出せばいいのでは

答え合わない

鍵の候補の出し方が間違ってた

直した

合った

提出

時間かかりすぎ・・・


チャレンジで鍵の候補を出すだけ出して、全部の暗号文を生成できるか全くチェックしてない人がいたので2人落とした。ラッキー。


どうでも良いが同じ鍵を何回も使ってるので全然one timeじゃない気がした


ソースコード

class NetworkXOneTimePad {
public:
	int crack(vector <string> plain, vector <string> cipher) {
		int res;
		int n=plain.size(), m=cipher.size();
		int sz=plain[0].size();
		
		if(m>n) return 0;

		vector <ll> p, c;
		for(int i=0; i<n; i++) {
			ll v=0;
			for(int j=0; j<sz; j++) if(plain[i][j]=='1') v|=(1LL<<j);
			p.push_back(v);
		}
		for(int i=0; i<m; i++) {
			ll v=0;
			for(int j=0; j<sz; j++) if(cipher[i][j]=='1') v|=(1LL<<j);
			c.push_back(v);
		}

		res=0;
		for(int i=0; i<n; i++) {
			ll key=p[i]^c[0];
			int ok[52]={0};
			for(int j=0; j<n; j++) {
				for(int k=0; k<m; k++) {
					if((p[j]^key)==c[k]) ok[k]=1;
				}
			}
			bool ok2=true;
			for(int j=0; j<m; j++) {
				if(!ok[j]) ok2=false;
			}
			if(ok2) res++;
		}

		return res;
	}
};

SRM516 Div1 500 RowsOrdering

| 22:16 | SRM516 Div1 500 RowsOrdering - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM516 Div1 500 RowsOrdering - SRM diary(Sigmar) SRM516 Div1 500 RowsOrdering - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

問題文むずい

何とか理解した

いかにもオーバーフローしそうなもの同士をmod取らずに比較せよとあるので、多分実際にindexの和を計算して比較するのは無理なんだろう

ということはGreedyとかであろうか。1桁決めればあとは全部決まるとか?

決まらない。むしろ逆だと気づいた。ある桁のpermutationを決めても、他の桁のpermutationに全く影響しない。

ということはそれぞれ独立に計算すればOK

書くのはあまり難しくなかった。10分ちょいくらい。

できた。オーバーフローしてないか確認。大丈夫。提出

再度見直す。大丈夫そう。


チャレンジフェーズ終わったところでPetr氏のコードを見ると、ほとんど同じだがびみょーーーーに違う

最後のSortの順番が逆である。比較関数がgreaterでなければならないのに、lessになっている。

まじか。そこはよく確認したはずだが・・・。

よく確認したつもりで間違った回答をしていたようだ。終わった。なぜ間違った結論に至ったのか全く分からない。

痛すぎる・・・


ソースコード

修正済み

const int MOD=1000000007;

class RowsOrdering {
public:
	int order(vector <string> rows) {
		int res;
		int n=rows.size(), m=rows[0].size();

		int sum[52]={0};
		for(int i=0; i<m; i++) {
			map <char, int> mp;
			for(int j=0; j<n; j++) {
				mp[rows[j][i]]++;
			}
			vector <int> vi;
			for(map <char, int>::iterator mpi=mp.begin(); mpi!=mp.end(); mpi++) {
				vi.push_back(mpi->second);
			}
			sort(vi.begin(), vi.end(), greater <int>());
			for(int j=0; j<(int)vi.size(); j++) {
				sum[i]+=vi[j]*j;
			}
		}

		sort(sum, sum+m, greater <int>());

		res=0;
		ll mul=1;
		for(int i=0; i<m; i++) {
			res=(res+mul*sum[i]%MOD)%MOD;
			mul=mul*50%MOD;
		}
		res=((ll)res+n)%MOD;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110831