ツバサの備忘録

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

貪欲法

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回のみであれば、振る行動の後に行っても何ら問題はありません。ということで、振る行動、投げる行動問わずダメージ量の降順でソートをし、貪欲にとっていけば良いです。 次の要素が投げる…

ABC011 C - 123引き算

C - 123引き算 提出コード 何故かハマってしまいまったく歯が立たなかった問題になります。 100回”以内”でゴール(0にする)すればいいので、とりあえず3をどんどん引いて行ってしまうのが最善の手になります。 もし3引いたときにNG数字にひっかかってしまうよ…

ABC100

はい、記念すべき100回目です。 …だったのですが、本当にボロボロでした、過去の成績の中でもパフォーマンスがワースト2位です。 今日ABCに初参加だった大学のお友達にも負けてしまったので本当に悔しいです。猛省します。 A - Happy Birthday! 提出コード …