ツバサの備忘録

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

bitDP

MIS.W新歓コンテスト2020

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

AOJ 2703 - サイコロスタンプ

問題 提出コード 解法 あらかじめ、番目のサイコロが転がった結果記される数字と座標のペアリストを作成しておきます。 サイコロの集合について、これらを最適な順番で転がした際に得ることができる得点の最大値 とすると、答えはです。 の求め方について考…

AOJ 2965 - F グリッドの番号

問題 提出コード 解法 小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。 番目までの数字を入れ終えて、上段に配置した個数が個かつ、直近手の上下の配置情報がのときの配置の通り数 とし…

ABC142 E - Get Everything

問題 提出コード 解法 制約がbitDPをしろと言っているので、bitDPをします。 現在開けた宝箱の状態がのときに、そこからかかる費用の最小値 とします。 を整数型の変数1つで表し、2進数の桁に宝を割り振り、0:まだ開いていない、1:開いている、とすると 初期…

AOJ 1619 - 弁当作り

問題 提出コード 解法 制約にと書いてあります。これがすべてです。 が大きいパターンとが大きいパターンで場合分けをします。 なので、実はが、簡単にビットで情報を持つことができます。 が小さいパターン 全探索をします。 それぞれの材料について、その…

Educational DP Contest / DP まとめコンテスト U - Grouping

問題 提出コード 解法 制約から見てbitDPです。 現在グループを組めていないウサギの状態がのときに、それ以降のグループ分けで得ることができる得点の最大値 とします。すると、の部分集合を用いて、 と書くことができます。 ただし、は、というグループを…

九州大学プログラミングコンテスト2018 F - Team Making

問題 提出コード 解法 制約にbitDPをしてくださいと書いてあります。 ので、実際にbitDPを考えてみます。 今チームを組み終わっている人の状態がであるときの、これ以降のチームの組み方 とすると、まだチームを組めていない人の中で組めるようなチームの集…

AOJ 2254 - 最短ルート

問題 提出コード 解法 制約を見ればbitDPと書いてあるのでbitDPをすることにします。 まず、番のステージをクリアした後に、再び番目のステージを行くことは考えなくていいです。2回以上同じステージに行くことで得をすることはありません。 ということで、…

WUPC2019のお話(解法編)

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

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

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

Typical DP Contest M - 家

問題 提出コード 解法 bitDPです。だんだん詰め合わせ感が増えてきました。 同じ階層でからに移動するパターン数 とすると、これをの行列に見立てて乗すると、が答えになります。 を求めることさえできれば、あとはこの行列式のを求めていき、程度で答えが求…

Typical DP Contest J - ボール

問題 提出コード 解法 bitDPです。 期待値の考え方については、こちらの問題のおかげですんなりいきました。 ARC085 C - HSI - ツバサの備忘録 座標においてある物の状態がである場合に、そこから全ての物を倒すまでに投げるボールの回数の期待値 とします。…

第4回 ドワンゴからの挑戦状 予選 D - ディスクの節約

問題 提出コード なんかこの問題の解説すごくむずかしいですね 解法 Nの制約が少ないので、現在のメモリの状態に対していろいろすることを考えます。ということで、bitDPです。 2進数に対し、小さい桁から順番に頂点の番号を割り当てていきます。 例えば、10…

ABC056 C - 部門分け

問題 提出コード 高速化がなかなか思いつきませんね… 解法 まずは、制約からbitDPをエスパーで思いつきます。 グループの状態がのとき、これを分割したときに作成できるスコアの最大値 とします。はビットにより表現できます。 を分割して、とに分けたときに…

AOJ 2709 - 真っ暗な部屋

問題 提出コード 解法 真っ暗な部屋が多くて16個しかないので、真っ暗な部屋に関する何かしらの情報をbitで持つことができます。 基本的な考え方は、幅優先探索です。 例えば回指示を出すとしたとき、指示列の選び方は種類になります。全ての部屋に対して、…

AOJ 1175 - そして,いくつになった?

問題 提出コード 個人的にICPCの中でも結構好きな部類の問題です。 解法 今回もc言語です。 メモ化再帰をしていきます。 円盤の枚数はたかだか24で、状態としては”残っている”か、”取り去られている”の2通りです。なので、全体で種類の状態が存在しますが、…

AOJ 1138 - Traveling by Stagecoach

問題 提出コード 解法 単一始点最短路問題なので、なんとなくダイクストラ法が使いたいなぁ、という気持ちになりました。 その後、馬車券の枚数を見ると、制約が8ととても少なく、都市の数自体も30以下とかなりすくないことから、馬車券を使ったかどうかbit…

SnackDown 2016 - Jealous Numbers

問題 与えられた集合から、任意の2つの元が互いに素になっているような部分集合をつくり、最大となる要素数を出力する、というものです。 これをT回繰り返します。 解法 まずはじめに、1はすべて部分集合にいれることができるので、1が入力された回数だけ別…

ABC041

バチャコン3回目です。初めてbitDPの問題に触れました。 A - 添字 提出コード 今回のA~Cはかなりシンプルでした。 A問題は、素直に文字列sのi番目の文字を出力すれば良いです。配列の最初が0になっていることだけ気を付ければ大丈夫です。 B - 直方体 提出コ…