SRM604
眠さに耐えつつ参加したらEasyで凡ミスして前回の大勝利を失う大敗北でした。寝不足にはなったしこの結果は許されない。
結果報告
| Level | ProblemName | Status | Point |
| Easy | PowerOfThree | FailedSystemTest | 0.0 |
| Medium | FoxConnection | Opened | 0.0 |
| Hard | ???? | Unopened | 0.0 |
Easy PowerOfThree
問題
(0,0)からスタートしてマイステップすこしずつ動くコマを考える。
各ステップk(=0,1,2,...)では、調度3^kの距離を、四方向のどこかに向けて動かなければならない。
X,Yを与えるので、頂点(X,Y)にたどり着くことができるか否かを答えよ
考えたこと
XとYの範囲がそれぞれ±10^9で与えられているので、k=20位まで探索すれば良さそうである。
方向も4方向しか無いんだし、正負だとか回転だとかを全て重複排除したら全探索でいけるんじゃないの？という方向でまず考えた。
暫く考えて後、この方針ではTLE不可避であることに気づく。
なぜなら、(a,b)からの移動の仕方として、(a+3^k,b),(a-3^k,b),(a,b+3^k),(a,b-3^k)はどうしても区別しないと行けないので、4^20くらいの計算時間が必要。
じゃあどうするか。
もし移動距離が２進数で移動方向が正方向のみだったら、XとYを２進数表記して各bitごとに片側にのみbitがたってるかを判定すれば良いわけだが…
と思ったところで、そういえば３進数って{-1,0,+1}を使って表現することもできる、みたいな話があることを思い出す。
よって、X、Yをそれぞれ上の形で３進数表記してあげて、各桁ごとに片側のみ非ゼロであるか否かを判定すれば良い。
…というところまではちゃんと考えられたのだが、Xの３進数表記を計算して後Yの３進数表記を計算仕様とした段で、キャリーの初期化を忘れてアボンした。
終了間際に気がついたのにresubがタッチの差で間に合わず、無念。
と言うか、コードコピペするくらいならちゃんと関数化しろってあれほど（ｒｙ
コード (SystemTest通過済み)
string ableToGet(int x, int y){ vector<int> xVec; vector<int> yVec; x = abs(x); y=abs(y); int car = 0; while( x != 0 ){ int curnum = car; curnum += x%3; car = 0; if( curnum >= 2 ){ curnum -= 3; car=1; } cout << curnum << ", "; xVec.push_back( curnum ); x/=3; } if( car != 0 ){ cout << car; xVec.push_back(car); } cout << endl; car = 0; //本番ではこの行を入れ忘れた。 while( y != 0 ){ int curnum = car; curnum += y%3; car = 0; if( curnum >= 2 ){ curnum -= 3; car=1; } cout << curnum << ", "; yVec.push_back( curnum ); y/=3; } if( car != 0 ){ cout << car; yVec.push_back(car); } cout << endl; while( xVec.size() < yVec.size() ) xVec.push_back(0); while( yVec.size() < xVec.size() ) yVec.push_back(0); for( int i = 0 ; i < (int) xVec.size(); i++ ){ if( abs(xVec[i])+abs(yVec[i]) != 1 ){ return "Impossible"; } } return "Possible";
落ちた人のコードを読んでみた
どうもチャレンジが下手すぎる感があるので、落ちていた人のEasyのコードを少し読んでみた。
一応、掲載コードは元ネタの唯の写経にするのではなくて不要部分を削除したり自分なりに書き換えて載せてます。
ケース1:条件分岐ミス
def ableToGet(self,x,y): x=abs(x) y=abs(y) dist=1 while x>0 or y>0: print(x,y) xmod=x%(3*dist) ymod=y%(3*dist) if xmod*ymod!=0: return 'Impossible' if xmod!=0: if xmod==dist: x-=dist else: x+=dist else: if ymod==dist: y-=dist else: y+=dist dist*=3 return 'Possible'
- 現在の距離distを足し引きする相手は、3*distで割り切れない方で、足すべきか引くべきかは3*distの割った結果がdistであるか否かで判定。
- 両方割り切れない場合はdistをどっちに割り振ってよいかわからないので破綻(つまり実現不可)
というもの。
一見ちゃんと動きそうに思えるのだけれど…意外にテストケース2(1,9)で無限ループに入る。
もっとわかりやすいケースで言えば、(0,3)で落ちる。
理由は、"xとyが両方共3*distで割り切れるケースはImpossible"という処理が抜けていること。
if( x*y != 0 ){//xとy両方が非ゼロの処理} else if( x!= 0 ){//xが非ゼロの処理} else{//yが非ゼロの処理}
この形の違和感に気づけるようにしたい。
ケース2:変数ミス
vector<pair<long long, long long> > EndOf11Step; vector<pair<long long, long long> > OffsetAfter11Step; long long pow3[21]; bool recUntil11Step(long long x, long long y , int step){ int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; if( x==0 && y==0 ) return true; if( step >= 11 ){ EndOf11Step.push_back(make_pair(x,y)); return false; } for( int i = 0 ; i < 4; i++ ){ if( recUntil11Step(x+dx[i]*pow3[step],y+dy[i]*pow3[step],step+1) ) return true; } return false; } void recAfter11Step(long long x, long long y , int step ){ int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; EndOf11Step.push_back(make_pair(x,y));//ここが間違い。本当は下記 //OffsetAfter11Step.push_back(make_pair(x,y)); if( step >= 21 ) return; for( int i = 0 ; i < 4; i++ ){ recAfter11Step(x+dx[i]*pow3[step],y+dy[i]*pow3[step],step+1); } } string ableToGet(int x, int y){ pow3[0]=1; for( int i = 1 ; i < 21; i++ )pow3[i]=pow3[i-1]*3; EndOf11Step.clear(); OffsetAfter11Step.clear(); if( recUntil11Step(x,y,0) ) return "Possible"; recAfter11Step(0,0,11); sort(EndOf11Step.begin(),EndOf11Step.end()); sort(OffsetAfter11Step.begin(),OffsetAfter11Step.end()); for( int i = 0 ; i < (int)EndOf11Step.size(); i++ ){ pair<long long, long long> a = EndOf11Step[i]; vector<pair<long long,long long> >::iterator it = lower_bound(OffsetAfter11Step.begin(),OffsetAfter11Step.end(),a); if( it!=OffsetAfter11Step.end() && *it==a ) return "Possible"; } return "Impossible"; }
最初そもそもコードが何をしているのかわからなかったんですが、ちゃんと読み解いたら理解した。
単純な全探索だと4^20=2^40=10^12くらいの時間がかかる所、
前半10ステップの終了状態(4^10=10^6)と後半ステップでとり得る値(1+4+16+...4^10=(4^11-1)/3個)それぞれ用意し、各前半のステップに対し、調度良い後半の要素を二分探索で求めるようにすると、10^6*log_2((4^11-1)/3)=2*10^7の時間でもとまる、というもの。
ちなみに実際に上記コードの誤り部を訂正すると1.9sくらいの実行時間とかも見えるけど通るっちゃ通る(ちゃんとした計算量の見積もりに比べると結構ギリギリ…どこかでオーダー10位ずれてる？）
ただ、残念なおとに後半部を格納すべきベクトルの名前が前半部のベクトルの名前だったためにこのコードでは11ステップ以降でマッチするケース(-570240,1412834とか)で落ちる。
コードの中身がわかってしまえば変数ミスは割りとわかりやすいけど、コードの意図がわからずにチャレンジフェーズで諦めてしまったのが良くなかったか。
と言うかこのコード、ぱっと見たらTLE狙って大きなケースとか投げてしまいたくなるな。テストケースに最大ケース入ってたから踏みとどまるとは思うけど。
Medium FoxConnection (Not Solved yet)
問題
木構造状に道路が配置された村の集合が与えられる。（道路の長さは全て１である）
各村には兎が一人居ることがあり、初期状態でどの村に兎がいるかも入力で与える。
今、兎たちが全員連結した位置に重複せず居るように、兎の位置を移動させたい。
兎の総移動距離の最小値を答えよ。
考えたこと
ある根ノードみたいなのを与えてあげて、その位置を含む連結成分に兎を寄せてあげる時の最小移動距離を、ノードをずらしながら行えばいいんじゃね？
などと考えてもみるものの、いまいち上記ことをコードとして実現できる感じはしない。
村の個数が最大50ということなので、dp[50][50][50]くらいのdpで計算するんじゃないか？と思い、
dp[i][j][k]=ノードiまでで、兎たちがj人親方向に連結しており、子方向に移動可能なフリーの兎をk人有する状態の最小移動数
なんて状態を考えてもみるも、そこから先に思考が続かなかった。
