SRM 474 :: DIV2
250 : system test pass
500 : failed system test
1000 : opened
500
いきなり500から開いて解く方針に切り替え。
N次元なのにNが10^9だと…、ビット演算さようなら。
どうしたらいいのこれ。座標で記録するのは無理だし…うーん。
移動が+と-の2種類しかない、もしかして移動状態を記録すればいいのでは?
適当に紙に書き出す。
(132,+) --> {(132,+)}
(51717,+) --> {(132,+),(51717,+)}
(620,+) --> {(132,+),(51717,+),(620,+)}
(3... ,+) --> {(132,+),(51717,+),(620,+),(3... ,+)}
(620,-) --> {(132,+),(51717,+),(3... ,+)}
(51717,-) --> {(132,+),(3... ,+)}
(3... ,-) --> {(132,+)} <--同じ状態が出てくる=同じ場所。it is NOT VALID.
これでいいんじゃね?
set< vector< pair
書く、バグ発生、初期状態のことすっかり忘れてた。
適当に修正、さらにバグ、え?
適当に修正、おk。Submit.
200
substrと+の連結でいいや。
あれ、substrの動作が不安…。
修正、なんか合ってるっぽい? Submit.
そして。
500落ちる\(^o^)/
あるぇー、考え方間違ってたかな?…
vector< pair
同じ状態でも、要素の順番が違えば異なるものとして判定されちゃうよ\(^o^)/
orz
250
struct PalindromesCount { int count(string A, string B){ int ret = 0; string str1 = A+B; string str2 = B+A; string rstr1 = string(str1.rbegin(), str1.rend()); string rstr2 = string(str2.rbegin(), str2.rend()); if( str1 == rstr1 )ret++; if( str2 == rstr2 )ret++; for(int i=1; i<A.size(); i++){ string str = A.substr(0,i) + B + A.substr(i,A.size()); string rstr = string( str.rbegin(), str.rend() ); if( str==rstr )ret++; } return ret; } };
500
struct RouteIntersection { string isValid(int N, vector <int> coords, string moves){ set< vector< pair<int,char> > > s; vector< pair<int,char> > t; REP(i,coords.size()){ char mov; if( moves[i]=='+' )mov='-'; else mov='+'; pair<int,char> p(coords[i],mov); int j; if( t.size()==0 ){ t.push_back( make_pair(coords[i],moves[i]) ); }else{ int f = 0; for(j=0; j<t.size(); j++){ if( t[j]==p ){ t.erase( t.begin()+j ); f = 1; break; } } if( t.size()>0 && !f ){ t.push_back( make_pair(coords[i],moves[i]) ); }else if( t.size()==0 ){ return "NOT VALID"; } } sort( all(t) ); if( s.find( t ) == s.end() ){ s.insert( t ); }else{ return "NOT VALID"; } } return "VALID"; } };