AOJ埋め5

AOJ

2005年のセット．
なんかこう，昔になるにつれて段々探索ゲーが増えてきている感じがします．

1257 Sum of Consecutive prime Numbers

やるだけ．いくらでもやり方はありそうだけど，前もって答え全部生成して答えるようにした．

1258 Book Replacement

シミュレーションするだけだけどやることがややこしい．問題文をよく読んでやること．
題意の読解に苦戦して50分くらい掛かってしまった．

1259 Colored Cubes

さいころ系問題．
さいころの回転は24通りあるので，対応付けを24^{n-1}通り全部生成して最小色数を求める．
さいころ回転の生成は，x軸回転，y軸回転，z軸回転をそれぞれX,Y,Zとして ZZZZXZZZZYZZZZXZZZZYZZZZXZZZZY みたいにするとできる．

1260 Organize Your Train

難しい探索．
探索空間の大きさがとても見積もりにくいし，実装もそれなりに面倒．
答えがかならず6以下で収まるというのが重要．
よく分からないので愚直にBFSするコードを書いたところ，深さ3程度までならあまり時間が掛からないがそこから先になると結構時間が掛かるようだったので，両側探索にしたら通った．
サンプルだとアルファベットがa,b,cしか現れないものしかないが，実際には10種類全部出てくるようなケースもありうるので気をつけないといけない．
a,b,cだけだと普通にBFSしても間に合うが，10種類出ると状態数が一気に増えてとても時間が掛かるようになってしまう．

1261 Mobile Computing

nが6以下ととても小さいので愚直な方法で間に合うみたい．
struct S { double left,right; };
みたいな区間を格納する構造体を定義して，
vector<S> dfs(double pos,int rest) を，x座標posを中心にしてrestでビットが立ってる重りを吊るした場合の区間を返す関数 として再帰したらできた．

Atomic Car Race

DP．
T[i][j]:=a[i]でタイヤ補給をして区間a[j]からa[j+1]を走るのに掛かる時間 をあらかじめ計算してもっておいて，
dp[i][j]:=スタート時点から走り出して，a[i]でタイヤ補給をしてa[j]までタイヤ補給をしないで走るときの最速時間，
dp2[i]:=スタートからa[i]まで走るときの最速時間
として計算．

1263 Network Mess

木を構築する問題．
コンピュータ(葉)の頂点集合{1,2,...,N}をL(N)，L(N)に対する解となるグラフをG(N)とすると，
G(N)はG(N-1)の葉でないノードにいくつか頂点を直鎖状にくっつけたものになる．

これより，N=1からスタートして，N=2,3... まで解を求めて行けばいい．
O(N^4)くらいかかる気がするけど，Nが50以下なことから間に合う．
解が一意になることがよくわからなかったのだけどそういうもんなのかな．