SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
2011-08-31SRM516 Div1
SRM516 Div1 250 NetworkXOneTimePad
コーディングフェーズ
適当に平文と暗号文を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
コーディングフェーズ
問題文むずい
何とか理解した
いかにもオーバーフローしそうなもの同士を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