2015-02-01から1ヶ月間の記事一覧

PCK2012本選「イヅア辞書」

AOJ0271 想定解よりも良い解が見つかったので O(RNlogN) このlogNはかなり小さいのでほぼ無視してよい。探索により解を見つける場合、可能性はN!通りあるので現実的ではない。 が、同じ文字が複数出現しないことを利用すると計算により位置を求めることがで…

PCK2014予選「バトンリレーゲーム」

AOJ0301Nが非常に大きいこと、クエリ操作が必要なことから高度なデータ構造の問題のように思えるが、交換回数が非常に小さい事に着目すれば実際は尺取法であることに気付く。 M (5 ≤ M ai (1 ≤ ai ≤ 100) 文中の操作とまったく同じ操作を行えるデータ構造を…

SRM649

レート 0→1300 明日JOIの参加記を書く予定

JOI2014本選 「フクロモモンガ」

AOJ0601ダイクストラ法なのですが、コストの持ち方を工夫する必要があります。memo[N] = 累計コスト+(木の高さ-現在位置)このように持つと、正しくダイクストラ法により解を求めることが出来ます。木の上下移動は最小限に抑える必要がありますが、木の距離か…

PCK2014予選 「天体観測」

AOJに問題が登録されたので解いてみました。 AOJ0302予め星の輝きをソートしておきます。 ある星Aを決めると、(Aの輝き)以上かつ(Aの輝き+d)に最も近い星までが星座を作る星になるので、 その様に選んだ時の長方形の面積Sの大きさは S = (星座内で最も大きい…

セグメントツリーメモ

更新は再帰的に処理します。各操作O(logN) ///RMQ #define SIZE (1<<18) #define ll long long #define INF (1<<30)///必要に応じて増やす ll int MSEG[SIZE]; void update(int index){ if(index==0)return; int l = index*2,r = index*2+1,tmp = MSEG[index…