SRM diary(Sigmar)

SRM516 Div1 250 NetworkXOneTimePad

SRM516, Div1 | 22:16 |

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

SRM516, Div1 | 22:16 |

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