ツバサの備忘録

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

ABC023 D - 射撃王

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

ABC023 C - 収集王

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

ABC083 D - Wide Flip

問題 提出コード 解法 パズルっぽい問題です。 結局、"11111..."のように、最後を全て1にそろえた場合でも、区間の端から端を選択して操作すると0000...にすることができます。ので、結局は01や10のように、0と1が途中でひっくり返っている部分を消していく…

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

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

ABC022 D - Big Bang

問題 提出コード 解法 それぞれの操作をどのように実行したかを求めるのは、とてつもなく難しそうです。 ので、他の方法で高速に答えを求める方法を探ります。 そのためには、平行移動と回転の操作では変化せず、拡大したときのみ変化する部分が必要になりま…

ABC022 C - Blue Bird

問題 提出コード1 提出コード2 解法 まずは想定解です。 頂点1から出るときの辺と、頂点1に帰るときの辺は違うものでなくてはなりません。 そのときの頂点をとすると、からは純粋な最短経路問題に置き換えることができます。 この問題では、頂点の個数が300…

BAPC2019 E - Entirely Unsorted Sequences

問題 提出コード 問題 個の数字が与えられるので、その数字を使って作れる数列のうち、以下のような条件を満たす数列の個数をで割った値を求めてください。 全ての数字について、その数字より左側に自分より大きいものが存在する、もしくは右側に小さいもの…

BAPC2018 F - Financial Planning

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

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

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

ABC021 D - 多重ループ

問題 提出コード 解法 答えの本質となる部分は問題文にすでに書いてあります。 求める数は、となるようなの組み合わせの個数です。 さて、以上以下の数字を個重複を許しつつ抽出すると、それらの数字を利用して作成したの組み合わせは一意に決まります。なぜ…

ABC116 D - Various Sushi

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

ABC116 C - Grand Garden

問題 提出コード 解法 こちらの問題とほぼ同じ考え方をすることができます。 スタックを利用します。 現在のスタックの一番上の数字をとします。最初はを格納しておきます。 そして以下のような操作を繰り返せば、答えが求まります(初期値は0としておきます)…

Educational DP Contest / DP まとめコンテスト S - Digit Sum

問題 提出コード 解法 桁DPです。というより、こちらとまったく同じ問題です。 emtubasa.hateblo.jp ただし、入力の順番だけが異なります。 感想 だいぶ前に通したコードなので、改めて書き直しました。 つい先日のABCでも桁DPが解法になりうる問題が出てい…

Educational DP Contest / DP まとめコンテスト R - Walk

問題 提出コード 解法 与えられた入力をの行列とみなし、これを乗すれば、その行列の値の総和が、長さのパスの総数になります。 あとは、バイナリ法なるものを利用して高速に計算することができれば、答えとなります。 冪乗 - Wikipedia 感想 この計算をする…

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

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

Educational DP Contest / DP まとめコンテスト P - Independent Set

問題 提出コード 解法 を色としたとき(1:白、0:黒)の、根とする部分木の色の決め方 とします。 全体の根はで固定します。 の子をとします。 すると、を黒で塗るには、の子はすべて白でなければならないこと、を白で塗る場合は、の色は何色でもよいことを考え…

Educational DP Contest / DP まとめコンテスト O - Matching

問題 提出コード(1) 提出コード(2) 解法 bitDPです。 番目までの男子に対してペアを作成し終えた段階で、残っている女子の状態がの際の組み合わせの数 とします。 とりあえず、女子全員が残っている状態をとします。 1人目の男子に対してペアを組める女子を1…

Educational DP Contest / DP まとめコンテスト N - Slimes

問題 提出コード 解法 とします。 体のスライムを合体していくのではなく、体の大きさのスライムを、体に分解していく、というようにして考えていきます。 このとき、大きさのスライムを分解するときのコストはになります。 区間のスライムが1体になっている…

Educational DP Contest / DP まとめコンテスト M - Candies

問題 提出コード 解法 普通にDPを考えてみます。 人目までにキャンディを配り終え、個のキャンディが残っている状態になるような場合の数 とすると、が答えとなります。 さて、人目にキャンディを配るとき、~個の中で好きな個数を選ぶことができます。つま…

Educational DP Contest / DP まとめコンテスト L - Deque

問題 提出コード 解法 区間DPです。 の区間だけ数列が存在する場合についての、お互いが最善手を尽くした際のの値 とします。答えはとなります。 メモ化DPにするとやりやすいです。 初期値は、です。 が奇数ならそのまま、偶数なら-1倍します。 あとは、以下…

ABC117 D - XXOR

問題 提出コード 解法 2進数の桁DPです。 としたとき、は現在見ている桁を表し、下から桁目、は桁目で0を使うか1を使うか、は桁DPで毎回出てくる、以下が確定しているかどうか、です。 今回は、が大きい方から見ていきます。そして、現時点での答え、すなわ…

ABC117 C - Streamline

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

Educational DP Contest / DP まとめコンテスト K - Stones

問題 提出コード 解法 素直にグランディ数を求めれば良いです。例によってグランディ数についてはこちらがわかりやすいかと思います。 グランディ数 - zukky162のブログ 今回は、重要なのがグランディ数は0であるか1であるか、なので2以上の場合も1にしてし…

Educational DP Contest / DP まとめコンテスト J - Sushi

問題 提出コード Sushi問題は難しいことで有名です(要出典) 解法 ループする系の期待値は、こんな感じで立式すると見えてきます。 今回は、お皿にのっているお寿司の数を利用します。 3個のっている寿司が皿、2個が皿、1個が皿だとして、そこから全ての寿…

Educational DP Contest / DP まとめコンテスト I - Coins

問題 提出コード 解法 確率です。 番目までのコインを投げて、表が回出る確率、とします。 もちろん、です。 答えは、 (ただし、 )の総和になります。 番目までのコインを投げて回表が出ていた場合、番目のコインを投げると表の回数がになるか、になります。…

Educational DP Contest / DP まとめコンテスト H - Grid 1

問題 提出コード 解法 マスに移動する方法数 とします。 すると、に移動するには、もしくはを通るしかないので、 ならば、 そうでなければ となります。 答えはを見ればわかります。

Educational DP Contest / DP まとめコンテスト G - Longest Path

問題 提出コード あきらかにこれで使えそうな問題ですね… 解法 グラフにおいて、スタート地点(入次数が0である頂点)に近い方から順番に、その頂点がゴールだったと仮定した場合における最長の距離を確定させていきます。 幅優先探索のようなものをします。…

Educational DP Contest / DP まとめコンテスト F - LCS

問題 提出コード 明らかにMLEを起こしそうなコードを提出するのはやめましょう。 解法 求める文字列の長さだけなら、よくある問題です。 ですが、今回は文字列自体も求めなければいけないので、DPの遷移の際に、たどってきた1つ手前の値を一緒に記録してあげ…

Educational DP Contest / DP まとめコンテスト E - Knapsack 2

問題 提出コード 解法 番目までの品物を利用して合計が価値がとなるような組み合わせの中での合計重量の最小値 とします。 となります。あとは、をで、を0で初期化し、このDPを解くことで、となるの最大値を求めれば、これが答えになります。

Educational DP Contest / DP まとめコンテスト D - Knapsack 1

問題 提出コード 解法 こちらと全く同じです。 動的計画法(ナップサック問題について) - ツバサの備忘録 番目までの品物を使って、重さの合計がとなるような組み合わせの中での価値の最大値 とすると、 となります。 答えはの最大値です。