ツバサの備忘録

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

貪欲法

ABC153 F - Silver Fox vs Monster

問題 提出コード 解法 について、で割り、切り上げをしておきます。これで、が 番目のモンスターを倒すまでにかかる攻撃回数 となります。加えて、全てのモンスターを、の昇順で並び替えます。 1番目のモンスターについて考えると、回どこかで攻撃しなければ…

ABC138 E - Strings of Impurity

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

AOJ 2298 - Starting Line

問題 解法 解法 が間に合うことに注目すると、任意の距離1の区間区間それぞれについて、速度で走るかで走るかを決めていけば良いです。 にんじんを食べるタイミングは貪欲に決めることができ、 今スピードアップしてなければ拾ったタイミングで食べる 今スピ…

ABC131 D - Megalomania

問題 提出コード 解法 やることから先に言うと、 をの昇順でソートし、を満たす任意のについて、 が成立すれば答えがYesになり、1つでもこれが成立しなければNoになります。 結局、時刻の時点では、締め切りが以下の仕事については全て終えている必要がある…

第3回 ドワンゴからの挑戦状 予選 C - スキーリフトの相乗り

問題 提出コード 解法 まず、順番は全く関係なく、できるだけ多くの4人グループを作成していくことだけを考えればよいです。 先にグループを決めてしまえば、決めたグループの中の誰かが先頭に来た時点で、他の人達と相乗りをすればよいです。 ということで…

エクサウィザーズ 2019 C - Snuke the Wizard

問題 提出コード 解法 後ろから見ると見通しがよくなるパターンの問題です。 ”消滅しないロボットの左端"をとします。これを、で求めていきます。同様に右端をとし、最後にその区間に含まれるロボットの数、つまりを求めれば答えとなります。 左端と右端は、…

AGC032 A - Limited Insertion

問題 提出コード 解法 操作を逆順で見ていき、数字を取り除いていくことを考えます。今現在の数列をで表すと、となった場合に番目の数字を取り除くことができます。 この操作を行った場合、番目以降の数字は順番が一つ前になります。 ですが、番目より手前の…

ABC091 C - 2D Plane 2N Points

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

WUPC2019のお話(解法編)

ということで、今回は各問題についての簡単な解法と、その感想です。 まだ解けていない問題もいくつかあるので、ご容赦ください… 運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。 emtubasa.hateblo.jp 各問題の方針と感想 A - WAse…

ABC121 C - Energy Drink Collector

問題 提出コード 解法 とにかく値段が安いものから買っていきたいです。 よって、値段と個数の上限をセットにしつつ、値段の昇順でソートすると、あとは個買えるまで貪欲に買っていけば答えを求めることができます。 感想 問題がすごくわかりやすくて解きや…

みんなのプロコン 2019 C - When I hit my pocket...

問題 提出コード 解法 とにかくビスケットが増えるように操作を行います。 まず、ビスケットが枚になるまでは、ビスケットをたたいて1枚増やす操作しか行うことができないので、たたきます。 この時点で回に達していれば、その時点で操作は終了です。 枚にな…

ABC116 D - Various Sushi

問題 提出コード 解法 ある程度までは貪欲にとっていき、その後一部入れ替えてみて探索していく、という形になります。 まずは、全ての寿司を美味しさの降順でソートします。 そして、上位個を食べたときのスコアを計算します。 この時、種類数を数えるのと…

ABC117 C - Streamline

問題 提出コード 解法 最初は端にコマを置いていけばいい、と思ったのですが全然違いました。 ある座標の周辺に、目標の座標が密集していると、この通りにはいきません(そもそもサンプル1でこの解法は落ちます)。 そこで、どうするかというと、目標の座標の…

AGC029 B - Powers of two

問題 提出コード 解法 実は貪欲法です。 大きい数字から、ペアを決めていきます。 ペアのうち大きい数字をとし、もう片方をとします。すると、とで作ることができる2べきの数は、1種類しか存在しません。 より大きい2べきの数のうち最小のものをとすると、で…

ABC065 D - Built?

問題 提出コード 解法 考察でごり押したら最小全域木とかいうやつを使っていたみたいです。 初期状態だと辺の可能性が約本あるので、これだと何をするにも不便です。 ですが、実は本程度まで減らすことができます。 個の座標をxについてソートした場合の隣り…

ABC057 D - Maximum Average Sets

問題 提出コード 解法 平均値の計算方法を思い出すと、 ですので、データの個数はより少なく、そしてデータの値の総和はより大きいものを選んだ方が得になります。 ということで、一番少ない個数になるのは個だけ選んだ時で、データの選び方は降順にソートし…

ABC053 C - X: Yet Another Die Game

問題 提出コード 誤読をしないように注意しましょう。 以上になればいいので(ちょうどでなくて大丈夫です!!!)、できるだけ大きい数字をひたすらもってくればよいです。 ということで、6と5を順番に上の面に持ってくればよいです。 2回で1セットとみて、11点…

ABC052 D - Walk and Teleport

問題 提出コード 解法 この手の問題は、まずテレポートをする回数を固定しましょう。 ということで、テレポートする回数を回とします。このとき、徒歩で移動する区間の個数は個になります。 徒歩で移動する区間はどこになるかというと、区間の距離が小さい方…

AGC024 B - Colorful Slimes

問題 提出コード 解法 スライムを好きなタイミングで捕まえることができ、捕まえる、魔法を唱える、捕まえる魔法を唱える…といったような順番で操作を行うことができます。ので、魔法を唱えるを唱える回数をまずは固定してしまって、捕まえるスライムの種類…

ABC048 C - Boxes and Candies

問題 提出コード 解法 貪欲法で問題ありません。 とについてみて、以下なら次に進みます。 より大きかった場合、になるようにキャンディを減らしていくのですが、このときの方を優先的に減らしていきます。すると、とについてみたときに、よりキャンディを減…

Tenka1 Programmer Contest (2018) C - Align

問題 提出コード 時間内に解きたかったですね… 解法 解説に詳しい証明が載っているのですが、並べた後の数列が凸凹になっていると、効率がよりよくなります。 みたいな感じです(逆もあり得ます)。 このとき、以下のような図で表現できます。上にある頂点は隣…

AGC027 B - Garbage Collector

問題 提出コード 解法 ゴミを回収しに行く回数(=ゴミを捨てる回数)を回と決め打ちし、そのときの最小値を求めます。 そして、最後にについて全探索して答えを求めることを考えます。 回ゴミを回収しに行くとき、ゴミを拾う回数は回、捨てる回数は回なので、…

ARC086 D - Non-decreasing

問題 提出コード 隣り合った要素を比較すると、正負によって4パターンに分けることができます。 前後が正だった場合 前の方が大きいならば、前の値を後ろに足してあげれば、1回の操作で条件を満たします。 前後が負だった場合 前の方が大きいならば、後ろの…

ARC086 C - Not so Diverse

問題 提出コード 書かれている数ごとに分けてボールの個数をカウントしていきます。 ボールの個数が多い数字は、変更しない方がいいので、少ない方から順番に選んでいきます。 (現在の種類数)-Kが変更するべき種類数なので、その種類数だけ、個数が少ない数…

ARC103 C - /\/\/\/

問題 提出コード 解法 自分が人生初のno submissionを決意した諸悪の根源(二度としません)です。 基本的には奇数番目と偶数番目に分けて、それぞれで個数の多い数字を1つずつ選べばそれが答えになります。 ただ、コーナーケースがサンプルの最後にあるような…

AOJ 2386 - Sightseeing Tour

問題 N個の都市があり、任意の頂点を2つとったときに両方の向きの有向辺が1つずつ存在します。 これを、ハミルトンパスが存在するように、全てどちらか片方のみ取り去ったときの、取り去るコストの最小値を求めなさい、というものです。 提出コード 解法 WA…

AOJ 2900 - 凸凹数列

問題 提出コード 解法 半分ぐらい貪欲です。 前から貪欲に、凹凸がズレていたら操作、ということを行うだけで条件を満たす数列を作成できます。 なので、最大でも数字の個数分の回数しか操作を行うことはありません。 ということで、基本的には貪欲に操作を…

AOJ 3039 - Aizu Competitive Programming Camp 2018 Day 2 A Special Chat

問題 解法 大きい値段から貪欲に払えるだけ払えば答えが求まります。 じつは、求められているものが合計金額なので、500についてのみ考えればいいらしいです。 提出コードはこちらになります。 #include <bits/stdc++.h> using namespace std; int memo[4] = {10000, 5000, </bits/stdc++.h>…

AGC027 A - Candy Distribution Again

問題 提出コード 貪欲法です。 を昇順にソートし、少ない方から順番に配っていけばよいです。配ったら残っているキャンディの量を減らしていきます。 最後だけ注意が必要で、残っている数と必要な数が等しいなら人数をカウントすることができ、そうでなけれ…

ABC085 D - Katana Thrower

D - Katana Thrower 提出コード 刀を投げることによるダメージは、1回のみであれば、振る行動の後に行っても何ら問題はありません。ということで、振る行動、投げる行動問わずダメージ量の降順でソートをし、貪欲にとっていけば良いです。 次の要素が投げる…