SRM 550
結果報告
300-500-850のセット。
| Level | ProblemName | Status | Point |
| Easy | RotatingBot | PassedSystemTest | 136.99 |
| Medium | CheckerExpansion | Opened(practiced) | 0.0 |
| Hard | ConversionMachine | Unopened(pracitced) | 0.0 |
Easy落ちてたら死んでた。
Easy RotatingBot
問題
境界orすでに通った枡に到達するまで直進し、前述のマス目に進みそうになったら左折するロボットがある。
ちなみに、左折した先にもすすめなかったらそこで動作を停止する。また、ロボットは手動で止める事もできる。
ロボットが曲がるまでに直進した枡の長さを配列で渡すので、
それが実現可能なフィールドの最小マス数を答えよ。
実現不可能なときは-1を返せ。
考えたこと
何も無いところで左折する＝そこに境界があるということだから、
それを保存しておいて、矛盾するなら-1を返して、そうでなければその情報を元にフィールドの広さを求めればよいだろう
……って思って実装したけど、途中で停止した場合だとか、
５進んで曲がって３進んで曲がって２進んで曲がる…なんてことはありえない、だとか
細かい条件を色々考えだしたらかなり実装するの大変だった。
テストケースが親切で助かったのかな。
コード
int minArea(vector <int> moves) { bool field[120][120]; int x=55; int y=55; int boundary[]={-1,-1,-1,-1}; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0, -1}; memset( field, false, sizeof(field)); field[x][y] = true; for( int i = 0 ; i < (int)moves.size(); i++ ){ int cur_dx = dx[i%4]; int cur_dy = dy[i%4]; for( int j = 0 ; j < moves[i]; j++ ){ x+=cur_dx; y+=cur_dy; //cout << x << ", " << y << endl; if( field[x][y] == true ) return -1; else{ int cord = x; if( i%2 != 0 ) cord = y; if( (i%4)<2 && boundary[i%4] != -1 && cord > boundary[i%4] ) return -1; if( (i%4)>=2 && boundary[i%4] != -1 && cord < boundary[i%4] ) return -1; field[x][y] = true; } } if( i+1 != (int)moves.size() ){ //sequence must continue //cout << "tmp" << endl; //cout << x+cur_dx << "," << y+cur_dy<<endl; if( field[x+cur_dx][y+cur_dy] != true ){ //but it must because the next cell has already been arrived int cord = x; if( i% 2 != 0 ) cord = y; if( boundary[i%4] == -1 ){ if( i%4 == 2 && cord > 55 ) return -1; if( i%4 == 3 && cord > 55 ) return -1; //cout << "boundary[" << i%4 << "]=" << cord << endl; boundary[i%4] = cord; } else if( boundary[i%4] != cord ) return -1; else{ // no problem } } else{ // no problem } } else{ if( field[x+cur_dx][y+cur_dy] != true ){ //but it must because the next cell has already been arrived int cord = x; if( i% 2 != 0 ) cord = y; if( boundary[i%4] == -1 ){ if( i%4 < 2 && cord > 55 ){ boundary[i%4] = cord; //cout << "boundary[" << i%4 << "]=" << cord << endl; } if( i%4 >=2 && cord < 55 ){ boundary[i%4] = cord; //cout << "boundary[" << i%4 << "]=" << cord << endl; } } //else if( boundary[i%4] != cord ) return -1; else{ // no problem } } else{ // no problem } } } for( int i = 0 ; i < 4; i++ ){ if( boundary[i] == -1 ) boundary[i] = 55; //cout << boundary[i] << " " ; } //cout << endl; return (boundary[0]-boundary[2]+1)*(boundary[1]-boundary[3]+1); }
後日談
最初にすべての左折点を求めてフィールドの境界を決定した後で、矛盾するかしないかを確認したほうがやりやすかった
Medium CheckerExpansion
AliceとBobで以下のゲームを行う
最初はAliceが0,0の領土を獲る。以後は以下を繰り返す
- (x-1,y-1)が相手に取られていて、（x-2,y)が空ならば、(x,y)をとれる。
- (x-2,y)が相手に取られていて、(x-1,y-1)が空ならば、(x,y)をとれる。
tターン終了した時の、(x0,y0)から(x0+w,y0+h)までのマス目の取得状況を答えよ
考えたこと
入力がlonglongだし、見るからに規則系ゲーですよね。
なんとなく規則性が見えた気もしつつ、綺麗な形に解釈する前に時間切れになった。
と言うか、フラクタルだったのね……
復習
Editorialを見ながらガシガシ書いた。方針わかっててもものすごい実装に時間がかかった。。。
このあたりをサッと確実に解けないとレート上昇は厳しいんだろうか。
あと、bit演算使う方はまだわかってない。bit演算で解いた人は一体どういう頭脳を持っているのだろう。
コード
bool check( long long x, long long y, long long t ){ cout << x << "," << y << "@" << t << endl; long long sum = x+y; if( t == 0 ) return false; if( t == 1 ) return (x==0 && y==0); //if( t == 2 ) return (x==0 && y==0) || (x==1&&y==1) || (x==2&& y== 0); if( sum > 2*t ) return false; long long mask = 2LL; while( mask*2 <= sum ) mask*=2; long long tim = mask/2; if( y >= tim && x >= tim && x < 3*tim && y < 2*tim){ return check( x-tim, y-tim, t-tim ); } if( x >= 2*tim && y <tim && x-y >= tim ){ return check( x-2*tim, y, t-tim ); } if( x < 2*tim && y< tim && x+y < tim){ return check( x, y , tim ); } return false; } vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h) { vector <string> result; for( int i = 0 ; i < h ; i++ ){ string tmp=""; for( int i = 0 ; i < w ; i++ ) tmp += "."; result.push_back(tmp); } for( int i = 0 ; i < w; i++ ){ for( int j = 0 ; j < h ; j++ ){ ll x = x0+i; ll y = y0+h-1-j; if( y>x ) continue; if( (x+y) > 2*t-2 ) continue; cout << x << y << endl; if( check(x,y,t) ){ cout << "true" <<endl; if( (x + y)%4 == 0 ){ // might be allice result[j][i]='A'; } else if( (x+y) %4 == 2 ){ result[j][i]='B'; } } } } return result; }
時間による位置の分割ではなく、
セルの位置に対して分割の仕方を変える方針にしたところ、無限ループが大量発生してわらった。
Hard ConversionMachine (practice)
問題
a,b,cからなる文字列2つ(word1,word2)と、a->b,b->c,c->aへの変換コストが与えられる。
与えられたmaxCost以下のコストで、word1をword2に変化させる方法は何通りあるか？
考えたこと
(ここから誤り)
んー、word1からword2にするまでのコストを求めたら、
あとは、a->b->c->aみたいな、3回変換をする方法しかあり得ない。
これをどの文字で何回行うかをcombinationで求めれば良いのではないか？
(ここまで誤り)
…なんて思ったけれど、"abc"->"bbc"->"cbc"->"abc"->"acc"と"abc"->"bbc"->"cbc"->"ccc"->"acc"は別扱いですか。
という訳でEditorialを眺める。
なるほど、(2回変換が必要な文字数、1回変換が必要な文字数)はひとつの状態とみなして良いのか。。。
そうすると、あとは各状態の間で何種類の遷移があるか、を重みとするグラフを生成し、
(0,0)->endpoint, endpoint->endpointに重み1の枝を貼れば、
K+1回の遷移で初期状態->endpointに遷移する回数＝K回以内の遷移で初期状態->(0,0)に遷移する回数が求められる。
後半の点は教訓にしたいな。
あと、何気に行列演算函数とかさくっと書こうと思ったらバッグバグで萎えた。
そろそろ予め函数を持っておくべきかもしれない
コード
mat mul( mat A, mat B ){
mat Ret(ssize,vec(ssize,0));
for( int i = 0 ; i < ssize ; i++ ){
for( int j = 0 ; j < ssize; j++ ){
for( int k = 0 ; k < ssize; k++ ){
Ret[i][j] += A[i][k]*B[k][j];
Ret[i][j] %= 1000000007;
}
}
}
return Ret;
}
mat pow( mat A, int k ){
mat R(ssize,vec(ssize,0));
mat Ret(ssize,vec(ssize,0));
for( int i = 0 ; i < ssize ; i++ )R[i][i]=1,Ret[i][i]=1;
R = mul(R,A);
for( int i = 0 ; (1<<i)<=k ; i++ ){
if((k&(1<<i))!=0){
Ret=mul(Ret, R);
/*
for( int ii = 0 ; ii < ssize ; ii++ ){
for( int j = 0 ; j < ssize ; j++ ){
cout << Ret[ii][j] << " ";
}
cout <<endl;
}
cout << endl;
*/
}
R = mul(R,R);
}
return Ret;
}
int countAll(string word1, string word2, vector <int> costs, int maxCost) {
int rotcost = 0;
for( int i = 0 ; i < 3 ; i++ ){
rotcost+=costs[i];
}
long long curcost = 0;
int n_step=0;
int size = word1.size();
int dist[3]={};
for( int i = 0 ; i < (int)word1.size(); i++ ){
int c = 0;
while( word1[i] != word2[i] ){
curcost+= costs[word1[i]-'a'];
word1[i]++;
n_step++;
c++;
if( word1[i] > 'c' ) word1[i] = 'a';
}
dist[c]++;
}
cout << curcost << "," << maxCost << endl;
if( curcost > maxCost ) return 0;
int rottime = (maxCost-curcost)/rotcost;
n_step += rottime*3;
// create matrix
map<pair<int,int>, int> indexes;
int ind = 0;
for( int i = 0 ; i <= size; i++ ){
for( int j = 0 ; j <= size; j++ ){
if( i+j <= size ){
indexes.insert( make_pair( make_pair(i,j),ind ) );
ind++;
}
}
}
mat A( ind+1, vec(ind+1,0) );
ind = 0;
for( int i = 0 ; i <= size; i++ ){
for( int j = 0 ; j <= size; j++ ){
if( i+j <= size ){
if( j > 0 ) A[ind][indexes[make_pair(i+1,j-1)]]=j;
if( i > 0 ) A[ind][indexes[make_pair(i-1,j)]] = i;
if( i+j!=size) A[ind][indexes[make_pair(i,j+1)]] = size-i-j;
ind++;
}
}
}
A[0][ind] = 1;
A[ind][ind] = 1;
ssize = ind+1;
/*
for( int i = 0 ; i < ssize ; i++ ){
for( int j = 0 ; j < ssize ; j++ ){
cout << A[i][j] << " ";
}
cout <<endl;
}
cout << "pow: "<<n_step+1;
cout << endl;*/
mat R =pow( A, n_step+1 );
/*
for( int i = 0 ; i < ssize ; i++ ){
for( int j = 0 ; j < ssize ; j++ ){
cout << R[i][j] << " ";
}
cout <<endl;
}
*/
int ans= R[indexes[make_pair(dist[1],dist[2])]][ind];
return ans;
}
