ツバサの備忘録

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

二分探索

AGC029 C - Lexicographic constraints

問題 提出コード 解法 種類以下で問題の条件を満たすような文字列たちを作成できるか?という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、あるについて問題の条件を満たすかどうか、を見ながら二分…

MIS.W新歓コンテスト2020

自分の大学にあるサークルが主催するコンテストに参加しました。 自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。 長いのでかなり端折る部分があり…

AOJ 2826 - ゲームバランス

問題文 提出コード 解法 倒すまでに最小回以上かかるなかで最大となるを二分探索で求めます。 ゲームクリアできない場合、になります。二分探索時は、ゲームクリアまでに回以上かかっている、と仮定します(最後に求まったを確認した場合にゲームクリアできな…

ABC149 E - Handshake

問題 提出コード 解法 明らかに、得点の和が高いペアから順番に握手をしていくのが最適です。 ある得点が達成できるとすると、明らかに未満の任意の得点は、全く同じ手を選ぶことで達成でき、達成できないときは以上の得点はどう頑張っても達成できないので…

ARC050 B - 花束

問題 提出コード 解法 個の花束を作成できるかどうか、を調べます。 まず、2種類の花束どちらも、1つの花束につき少なくとも1本使用することになるので、最低本ずつ使用することになります。 この部分を除くと、 赤い花を本使用する 青い花を本使用する の2…

ABC033 D - 三角形の分類

問題 提出コード 解法 直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、 直角三角形→直角の個数 鈍角三角形→鈍角の個数 鋭角三角形→から上2つの個数を引いたもの が答えになります。 あ…

AOJ 1232 - Calling Extraterrestrial Intelligence Again

問題 提出コード 問題概要 3つの整数が与えられます。 かつとなるようなのうち、が最大となるようなペアを求めてください。 制約は、です。 解法 まずはエラトステネスの篩を利用して、素数を洗い出します。 について全探索をすると、の最適解は、あるに対し…

ABC138 E - Strings of Impurity

問題 提出コード 解法 に含まれ、に含まれない文字が存在する場合、答えは-1になります。逆に、それ以外の場合は、必ず答えを見つけることができます。 の部分列でを作る際、お互いの先頭から順番に、一致する部分を選んでいけばよいです。 作りたい文字列は…

AtCoder Petrozavodsk Contest 001 C - Vacant Seat

問題 提出コード 解法 インタラクティブ問題なので、二分探索を考えていきます。 まずは、どこか1つの席の情報がわかっていないと何も始まらないので、番の席を特定します。 ここが空席ならばその時点で終了、女性だったならば、男性だった場合と真逆のこと…

ABC102 D - Equal Cut

問題 提出コード 解法 パッと見とっつきにくい問題。 まずは、3つのうち、どこか1つの仕切りを固定して考えるとして、どの仕切りを固定すると見通しがよくなるかを調べます。 まず、右端の仕切りを固定することと、左端の仕切りを固定することによる見通しの…

九州大学プログラミングコンテスト2018 D - Novelist

問題 提出コード 解法 王都から都市へ移動する依頼をうけるとき、その後に王都からへ移動する依頼を受けるには、一旦から王都へ戻る依頼を受ける必要があります。 ということで、王都を出て、また王都へ戻る期間を、金貨が2枚もらえる1つの区間と見て、期間…

ABC091 C - 2D Plane 2N Points

問題 提出コード 解法 2次元のままこの問題を考えると、いろいろと大変なことになるので、どちらか片方の条件を無視してよくなるような条件を探します。 すると、赤の点と青の点を同時にの昇順、の昇順の優先度でソートを行うと、番目の赤い点と、番目の青い…

AOJ 2933 - 矢 / Arrow (RUPC2019 Day3 D)

問題 提出コード 解法 簡単のため、にも送風機があるとしてよいです。 矢の長さがのときの損失回数がわかっていれば、各クエリに対して二分探索をして答えを求めることができます。 ということで、長さがのときの損失回数を頑張って求めます。 送風機と送風…

ABC119 D - Lazy Faith

問題 提出コード 解法 すごく簡単にいうと、それぞれのクエリに対して、解の候補が8通りしかありません。なので、調べればよいです。 今いる地点をとしたときに、より左側にある寺(神社も同様)のうち、一番近いものを1つみつけてひっぱってきます。右側も同…

ABC023 C - 収集王

問題 提出コード 解法 まずは行目を選択すると固定して考えてみることにします。 行目を選択した場合にアメが個得られるとします。 同様に、列目を選択した場合に個得られるとします。 この時、個のアメを得るには、を満たすものならばいいように見えるかも…

ABC023 D - 射撃王

問題 提出コード 解法 最大値の最小値を求めよ、といえば!二分探索です、ということで二分探索をしていきます。 点を達成できるかどうか、を二分探索で調べていきます。 ここでの達成できるか、はぴったりではなく、点以上を達成できるかどうか、になります…

BAPC2018 F - Financial Planning

問題 提出コード 問題 個の投資先があり、番目の投資先は、費用が (初日のみ)で、1日にユーロの利益が出ます。 投資費用を返済した上で円の利益を得るために必要な最小日数を答えてください。 というものになります。 です。 解法 二分探索をして答えを出し…

Typical DP Contest K - ターゲット

問題 提出コード 解法 区間スケジューリングのように、区間の終わりの部分に注目すると、LISに帰着させることができます。 まず、中心座標はx軸上に存在しているので、それぞれの円について、中心座標とがわかっているとき、円と軸が接する2点は、とになりま…

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]等で求められるので、ありうるすべての取り方を記録します。 …