cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM445 の成績・ソース (要ログイン) : WA/WA/- : 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL
あとで | |
0.5刻みで全部試すコード。
class TheNewHouseDivOne { public: double distance(vector <int> x, vector <int> y, int k) { double minD = 1e+99; for(double X=-50; X<=+50; X+=0.5) for(double Y=-50; Y<=+50; Y+=0.5) { vector<double> d; for(int i=0; i<x.size(); ++i) d.push_back( abs(x[i]-X) + abs(y[i]-Y) ); nth_element(d.begin(), d.begin()+k-1, d.end()); minD = min(minD, d[k-1]); } return minD; } };
というところか。なるほどなー。
あとで | |
6個にグループ分けでメモ化探索という方針はあってた
static const LL MODVAL = 1234567891; class TheEncryptionDivOne { public: map<pair< pair<pair<int,int>, int>, pair<pair<int,int>, int> >, LL> memo; int count(string msg, string encMsg) { // accumulate unused characters char cs[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; set<char> ori(cs+0, cs+52), enc(cs+0, cs+52); for(int i=0; i<msg.size(); ++i) ori.erase(msg[i]), enc.erase(encMsg[i]); // obviously-invalid cases for(int i=0; i<msg.size(); ++i) if( toupper(msg[i]) == toupper(encMsg[i]) ) return 0; if( ori.size() != enc.size() ) return 0; // count int t0x=0, tx0=0, t11=0, t12=0, t21=0, t22=0; for(char c='a'; c<='z'; ++c) { int oc = ori.count(c)+ori.count(c+'A'-'a'); int ec = enc.count(c)+enc.count(c+'A'-'a'); if( oc == 0 ) t0x += ec; else if( ec == 0 ) tx0 += oc; else if(oc==1 && ec==1) t11 ++; else if(oc==1 && ec==2) t12 ++; else if(oc==2 && ec==1) t21 ++; else if(oc==2 && ec==2) t22 ++; } return rec(tx0, t0x, t11, t12, t21, t22); } LL rec(int tx0, int t0x, int t11, int t12, int t21, int t22) { pair< pair<pair<int,int>, int>, pair<pair<int,int>, int> > key(make_pair(make_pair(tx0,t0x), t11), make_pair(make_pair(t12,t21), t22)); if(memo.count(key)) return memo[key]; if( t11 ) { LL val = 0; if( t0x ) val += t0x * rec(tx0, t0x+1-1, t11-1, t12, t21, t22); if(t11>1) val += (t11-1) * rec(tx0+1, t0x+1, t11-1-1, t12, t21, t22); if( t12 ) val += t12 * 2 * rec(tx0, t0x+1, t11-1+1, t12-1, t21, t22); if( t21 ) val += t21 * rec(tx0+2, t0x+1, t11-1, t12, t21-1, t22); if( t22 ) val += t22 * 2 * rec(tx0, t0x+1, t11-1, t12, t21+1, t22-1); return memo[key] = val%MODVAL; } if( t12 ) { LL val = 0; if( t0x ) val += t0x * rec(tx0, t0x+2-1, t11, t12-1, t21, t22); if( t11 ) val += t11 * rec(tx0+1, t0x+2, t11-1, t12-1, t21, t22); if(t12>1) val += (t12-1)*2*rec(tx0, t0x+2, t11+1, t12-1-1, t21, t22); if( t21 ) val += t21 * rec(tx0+2, t0x+2, t11, t12-1, t21-1, t22); if( t22 ) val += t22 * 2 * rec(tx0, t0x+2, t11, t12-1, t21+1, t22-1); return memo[key] = val%MODVAL; } if( t21 ) { LL val = 0; if( t0x ) val += t0x * rec(tx0, t0x-1, t11+1, t12, t21-1, t22); if( t11 ) val += t11 * rec(tx0+1, t0x, t11+1-1, t12, t21-1, t22); if( t12 ) val += t12 * 2 * rec(tx0, t0x, t11+1+1, t12-1, t21-1, t22); if(t21>1) val += (t21-1) * rec(tx0+2, t0x, t11+1, t12, t21-1-1, t22); if( t22 ) val += t22 * 2 * rec(tx0, t0x, t11+1, t12, t21-1+1, t22-1); return memo[key] = val%MODVAL; } if( t22 ) { LL val = 0; if( t0x ) val += t0x * rec(tx0, t0x-1, t11, t12+1, t21, t22-1); if( t11 ) val += t11 * rec(tx0+1, t0x, t11-1, t12+1, t21, t22-1); if( t12 ) val += t12 * 2 * rec(tx0, t0x, t11+1, t12+1-1, t21, t22-1); if( t21 ) val += t21 * rec(tx0+2, t0x, t11, t12+1, t21-1, t22-1); if(t22>1) val += (t22-1)*2*rec(tx0, t0x, t11, t12+1, t21+1, t22-1-1); return memo[key] = val%MODVAL; } LL f=1; for(LL n=1; n<=tx0; ++n) f = (f*n)%MODVAL; return memo[key] = f; } };
あってたけど、この腐った手作業条件分岐を時間内に正しくデバッグし通せる見込みは全くないなあ。どんだけ時間が切羽詰まっててもちゃんとしたコードを書く習慣を付けなければ…
改訂版
static const LL MODVAL = 1234567891; class TheEncryptionDivOne { public: map<vector<int>, LL> memo; int count(string msg, string encMsg) { // 平文側(ori)、暗号文側(enc) でそれぞれ // 使われてない文字 = これから割り当て決めなきゃいけない文字 を集める char cs[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; set<char> ori(cs+0, cs+52), enc(cs+0, cs+52); for(int i=0; i<msg.size(); ++i) ori.erase(msg[i]), enc.erase(encMsg[i]); // 探索の前にあきらかにダメなケースをはじく for(int i=0; i<msg.size(); ++i) if( toupper(msg[i]) == toupper(encMsg[i]) ) return 0; if( ori.size() != enc.size() ) return 0; // メモ化探索 // - 9元ベクトルsが状態。 // - sは、アルファベット(A-Z)26種を9パターンに分けて持っている // - s[a*3+b] == 平文側にa個、暗号文側にb個、未割当の字が残ってるアルファベットの総数 // - たとえば入力が "a"->"W" なら初期状態は // (0,0,0, 0,0,1, 0,1,24) // となる: 1個-2個 のもの (A,aA) が1種、2個-1個の (wW,w)が1種、その他24種 vector<int> s(9); for(char c='a'; c<='z'; ++c) { int oc = ori.count(c)+ori.count(c+'A'-'a'); int ec = enc.count(c)+enc.count(c+'A'-'a'); s[oc*3+ec] ++; } return rec(s); } LL rec( const vector<int>& s ) { if( memo.count(s) ) return memo[s]; for(int a=1; a<=2; ++a) for(int b=0; b<=2; ++b) if( s[a*3+b] ) // 平文側の未割当のものを順に割り当て { LL val = 0; for(int c=0; c<=2; ++c) for(int d=1; d<=2; ++d) if( s[c*3+d] ) // 暗号文側の未割当のものを全通り選ぶ { vector<int> t = s; t[a*3+b] --; if( LL choices = t[c*3+d]*d ) { t[(a-1)*3+b] ++; t[c*3+d] --; t[c*3+(d-1)] ++; val += choices * rec(t); // 再帰 } } return memo[s] = val%MODVAL; } return 1; } };
presented by
cafelier/k.inaba
under
