課題とコードはこの辺。
csny/segment-tree · GitHub
segment-tree/main.m at master · csny/segment-tree · GitHub
前回頓挫してたのはこんな感じ。
セグメント木の累積和が上手くいかんなぁ - せでぃのブログ
前回解決しきれなかったコードを眺めてて、コイン両替問題と同じ、経路探索であることに気づいて、幅優先探索でやってみた。幅優先探索は、構造上、何も考えんと最短経路を出すから助かる。答えは間違いなく出すけど、最適なコードかどうかはわかりませんw 流れはこんな。
- セグメント木の累積和、セグメント木の区間幅、セグメント木の開始番号の配列を3つ用意する
- 累積和用のキューと番号の飛び方のキューを用意する
- もし飛び方キュー(最初は開始番号)が終了番号と合致していれば答えを出力してループ終了
- もし飛び方キューに次の区間幅を加えても終了番号に届かなければ処理に移り、オーバーしていたら何もしない
- 開始番号に合致するかセグメント木をifで検索し、合致しなければ何もしない
- 合致したら累積和のキューに累積和を加え、番号の飛び方キューに区間幅を加えて3へ
セグメント木はいろいろ融通が利いて便利だけど、補助的な配列が多くて結構疲れた。セグメント木の補助的な要素の求め方は、この辺で助けてもらいました。このボリュームのコードでも疲れましたわ。時間制限ありでやるのは辛そう。
Segment Treeをちょっと高速化したい - komiyamの日記
補助的な配列
経路探索にもっていくには、経路のコスト(区間幅)と開始または終了位置が必要になる。
2を底とする対数を使って上から0,1,2,3と階層を出し、その階層を使って16を2の累乗で割ると区間幅が出る。開始番号は適当に。
Objective-CではhighestOneBitという関数が見つからなくてこんな感じになりました。
// セグメント木のセグメント区間幅[0][0-30]と区間の開始番号[1][0-30] int treeattr[2][TOTALNUM*2-1]; // セグメント木作成 void init_tree(){ for (int i=TOTALNUM-2;i>=0;i--){ if (tree[i]==-1){ tree[i]=tree[i*2+1]+tree[i*2+2]; } } // 区間幅と開始番号の配列treeattr初期化 int treewidth=TOTALNUM; for (int i=TOTALNUM*2-2;i>=0;i--){ // セグメント木の区間幅 // 2を底とするi+1の対数の整数部分が階層。上から0,1,2となる。 double result1 = log2(i+1); // 16を2の累乗で割る int result2 = pow(2, floor(result1)); treeattr[0][i]=TOTALNUM/result2; // セグメント木の区間の開始番号 treeattr[1][i]=treewidth-treeattr[0][i]+1; treewidth -= treeattr[0][i]; if (treewidth == 0){ treewidth = TOTALNUM; } } }
本題
累積和を格納するキューと番号の飛び方を格納するキュー、ついでに経路表示用の文字の配列を用意して、FIFOの定型に入れる。
// start番目の番号からgoal番目までの累積和と計算回数を表示する /* Queue First-In First-Out方式 */ const int SIZE = 500; // キューとして使う配列のサイズ // [0][i]累積和のキュー[1][i]番号の計算キュー int queue[2][SIZE]; NSString *path[SIZE]; // 経路出力用に文字列の配列を用意 // 幅優先探索で、開始番号start=rから終了番号goal=s+1までの累積和を表示する // 探索の根幹は#1.2.3.4.5のループ void sum_sequence( int start, int goal ){ // キュー入出力用に使う変数。frontは先頭、rearは末尾。 // rearは次のノードの取り込み位置、frontは親ノード兼次の削除位置として利用。 int rear = 1, front = 0; queue[0][front]=0; // 累積和の最初の親ノード queue[1][front]=start; // 番号の一番最初の親ノード path[front]=@"経路"; while( front < rear ){ // #0.ループ設定 front=rearはキューが空の状態を表す for(int i = 0; i < TOTALNUM*2-1; i++){ // #1.子ノード取り込み処理開始 if(queue[1][front]==goal){ // #2.条件判定等の処理 // 探索結果出力 NSLog(@"%d",queue[0][front]); NSLog(@"%@",path[front]); //NSLog(@"%@",path[rear]); return; // キューのサイズが足りないので、答えが出たら探索途中でwhileループ終了 }else if(queue[1][front] + treeattr[0][i]<=goal){ if(queue[1][front]==treeattr[1][i]){ queue[0][rear] = queue[0][front] + tree[i]; // #3.キュー取り込み queue[1][rear] = queue[1][front] + treeattr[0][i]; path[rear]=[NSString stringWithFormat:@"%@,%d",path[front],tree[i]]; rear++; // #4.キューに取り込んだら、次に取り込む位置に移動 } } // キューサイズ節約のため、startがgoalより大きくなったらキューに取り込まない } front++; // #5.キューの先頭の枝1本を探索済み・削除扱いして、次の枝の取り込みへ } }