ツバサの備忘録

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

Range Minimum Query(RMQ)

AGC005 B - Minimum Sum

問題 提出コード 解法 番目の数字、が採用される区間について調べてみます。 となる区間について、がその区間の最小値になるには、かつとなる任意のについて、が成り立たなければなりません。 こうなるようなの候補の最小値、の最大値を求めてみます。 これ…

WUPC2019のお話(解法編)

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

ゆるふわ競プロオンサイト参加記

2/9に東京で行われました、@matsu7874さん主催の競プロオンサイトイベント、に参加してきました! コンテスト自体は全8問で、2時間のセットでした。自分は、ABCDEGの6完でした! B式A+B 集合写真 線香 最短経路は何本ありますか ガソリンスタンド 射的 感想 …

Educational DP Contest / DP まとめコンテスト Q - Flowers

問題 提出コード 解法 とりあえず、最終的に残る花は、かつを満たすので、LISっぽいことを考えてみます。 一番高さが高い(つまり右端)花の番号がになるような並べ方の中での、美しさの総和の最大値 とします。 すると、次のような操作を、が小さい方から行え…

ABC062 D - 3N Numbers

問題 提出コード やること自体は同じだったのですが、想定解がすごい綺麗で感動しました。ここでpriority_queueが使えるのですね~ 解法 この問題は、初期値を(前からNの長さの部分の総和)-(後ろからNの長さの部分の総和)とし、 真ん中のNの長さの部分を、 …

AGC024 B - Colorful Slimes

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