ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

二分探索

ABC063 D - Widespread

問題 提出コード 解法 全員を倒すまでにかかる回数が、最悪回なので、かぐらいまで計算量を落としたいです。 すると、倒すのにかかる回数を二分探索すると、うまくとlogの計算量に落ち着きそうです。 倒すのにかかる回数を二分探索するということで、 回魔法…

ABC056 D - No Need

問題 提出コード サンプル3についてなんとなく考えると、不必要なカードは2,3,4の3つであり、これはすべてのカードの中で小さい3つを選ぶ形になります。 ということで、なんとなく、昇順にソートすると前の方が不必要、後ろの方が必要なカードになりそうなこ…

ABC077 C - Snuke Festival

問題 提出コード 中段について、番目のパーツを使うとしたときに、使うことができる下段のパーツはとなるパーツ番号の場合です。このようなのうち最小のものをもとめれば、それより大きい個のパーツはすべて使用できます。 ということで、まずはそれぞれのパ…

codeFlyer (bitFlyer Programming Contest)予選 C - 徒歩圏内

問題 提出コード これを自力で解けなかったのは結構悔しいです…最近思い通りになかなか解けないですね 解法 ,,となるようなの組を探します。 要素が3つ存在するので、まずは真ん中を決め打ちしたときののペアの個数を求めることを考えます。 あるについて、…

Benelux Algorithm Programming Contest 2016 E Charles in Charge

問題 N個の頂点と、M個の重み付きの辺があるグラフが与えられます。 頂点1から頂点Nに行く最短経路に、X%加えた新しい距離以内で、頂点1から頂点Nにたどる道の中で辺の重みの最大値が、最も小さくなるときの、辺の重みの最大値を求めなさい、というものです…

ABC006 D - トランプ挿入ソート

問題 提出コード 解法 基本的に、1つのトランプは1回操作するだけで必ず正しい位置に戻せるので、最悪N回の操作が必要になります。 そして、操作の回数を最小にするには、そもそも操作しないトランプの枚数を最大化すればいいことになります。 これはつまり…

AOJ 2372 - IkaNumber

問題 提出コード 自力でなんとか解けました!時間は4時間くらいかかりました… くコ:彡 くコ:彡 くコ:彡 くコ:彡 解法 問題を読んだだけではかなり自由度が高いので、一つ一つ見ていくことにします。 まず、Taroの家の位置を固定します。 Taroの家、にんじん…

ABC014 D - 閉路

D - 閉路 提出コード 初めてLCAを扱う問題に触れました。 現在の木の根を適当に決めます。どこでもいいです。 新しく追加する辺の2つの頂点の番号をa,bとします。このとき、閉路の長さは、 (aの根からの深さ)+(bの根からの深さ)-2×(aとbの共通の祖先で最も近…

ABC013 C - 節制

C - 節制 提出コード 数学に強い系か、実装のほうができる系によって解き方がかわる面白い問題です(これに限らず時々おこりますが...) 素直に全探索について考えてみます。 普通の食事をi日、質素な食事をj日、食べない日をk日として3重ループすると、間に合…

ABC107 D - Median of Medians

D - Median of Medians 提出コード 初めてBITを使った問題です。 この問題では、中央値となる条件をうまく言い換えていき、最終的に転倒数を求める問題に帰着させます。転倒数を求める段階で、BITを利用します。蟻本をみたらそこにも載っていた問題になりま…

AOJ 2015 - Square Route

Square Route 提出コード まずは累積和で、上端から、および左端からi番目の道路までの距離を求めておきます(s[i]とします)。 すると、ある道路からある道路までの幅が、累積和の引き算s[i]-s[j]等で求められるので、ありうるすべての取り方を記録します。 …