ツバサの備忘録

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

動的計画法(DP)

ABC018 D - バレンタインデー

問題 提出コード 解法 部分点が、どうせ男女の組み合わせについてすべてのパターンを試すんだろうなぁ、という感じがしたので、どうせ男子か女子どちらかのみを探索すると答えを求めるようにすることで高速化をするのかなぁ、という気持ちになります。 とい…

ABC017 D - サプリメント

問題 提出コード 解法 番目までのサプリメントを飲む方法数 とします。 番目のサプリメントを飲むときは、 番目のみを1日で飲む 番目と番目の2つを1日で飲む 番目から番目の3つを1日で飲む というように、同時に飲むこともできます。 しかし、番目から番目の…

ABC063 C - Bugged

問題 提出コード 解法 CはDPのC!(n回目)解説PDFによるとオーバーキル解法だそうです… までを利用して、合計得点を10で割った余りがとなるような得点の取り方の最大値 としてDPを解いていきます。 これは、 で解くことができます。 最終的な答えは、 の、の部…

ABC060 D - Simple Knapsack

問題 提出コード 解法 ナップサックと書いてあるのでとりあえずDPを考えます。 をすべての重量から引いていくと、どれも0~3のいずれかの重量に置き換えることができます。 この重さを利用して、次のようなDPを考えていきます。 番目までの荷物の中で、個使用…

ABC056 D - No Need

問題 提出コード サンプル3についてなんとなく考えると、不必要なカードは2,3,4の3つであり、これはすべてのカードの中で小さい3つを選ぶ形になります。 ということで、なんとなく、昇順にソートすると前の方が不必要、後ろの方が必要なカードになりそうなこ…

ABC054 D - Mixing Experiment

問題 提出コード 解法 DPをします。 番目までの薬品で、がグラム、がグラムになるような選び方の最小値 とします。 初期値は、、それ以外はです。 あとは、 という遷移をしていけば大丈夫です。 最終的な答えは、 となります(ここで、は1以上です)。

ABC050 D - Xor Sum

問題 提出コード 方針がたってから遷移をバグなく求めるまでになんと半日かかりました! 解法 桁DPです。 というのも、2進数になおした2つの数字のペアについて、それぞれの桁についてありうる桁の組み合わせは、 の3種類のみです。 そして、これらの組み合…

ABC113 D - Number of Amidakuji

問題 提出コード DPをします。 まずは、下準備をします。 ある高さについて、幅がのとき(つまり、本の棒があるとき)に、横線の置き方がいくつあるかを計算します。 これをとします。 のとき、横線はおけないのでです。 のとき、横線を置くか置かないかの2通…

ABC044 C - 高橋君とカード / Tak and Cards

問題 提出コード CはDPのCですね! 解法 動的計画法を利用します。 数列のi番目までのうち、j個の要素を足した結果がkになるようなものの個数 とします。 すると、 右辺の左の項は、を使用しないパターン(1つ前の個数がそのまま引き継がれます)、右の項は、…

AOJ 2709 - 真っ暗な部屋

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

AOJ 2233 Carrot Tour

問題 提出コード 解法 これ自力で解ききれなかったの悔しいですね… dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値 とします。こうすることで、持っているにんじんの個数は自動的にkになります。 そして、 dis[i][j]…

SoundHound Programming Contest 2018 Masters Tournament 本戦 B - Neutralize

問題 提出コード ある区間を0にしつつ、うまいこと累積和を計算していきます。 今回は、DPを使って考えました。 i+1 ~ i+Kが0の区間だった場合、i+1~i+Kは無視してよく、i+Kに、iまでの累積和が存在することと同じになります。 ということで、今iについてみ…

CODE FESTIVAL 2018 qual A D - 通勤

問題 提出コード 解法 後ろの方から見ていくと見通しが良くなるのかな、と思いきやそうでもありませんでした。 番目のガソリンスタンドで燃料を補給する場合の、~番目のガソリンスタンドの建て替え方 とします。 仮に今燃料が満タンの状態で番目のガソリンス…

CODE FESTIVAL 2018 qual A C - 半分

問題 提出コード 解法 動的計画法で答えを求めていくことを考えていきます。 まずは特徴についてです。 この問題では、0がとても重要なものになっています。 数列に0が存在していた場合、0は何回2で割っても0になるので、この部分を利用して与えられたの調整…

AOJ 1167 - ポロック予想

問題 提出コード 解法 正四面体数を記録して、重複可能ナップサック問題を解いていきます。 dp[i][j] = i番目までを使用して、数がjになるような組み合わせの中の最小個数 = i番目の正四面体数 とすると、 dp[i][j] = min(dp[i-1][j],dp[i][j-]+1) となりま…

AOJ 1277 - Minimal Backgammon

問題 0~Nまでの盤面がある双六をします。 ダイスは1~6で、確率はすべて等しいです。 スタートは0で、ゴールがNです。 ゴールを通過すると、溢れた分だけ戻ります(ゴール扱いにはなりません)。 特殊マスが2種類あり、 L : 一回休み B: スタートへ戻る という…

AOJ 2892 - Aizu Competitive Programming Camp 2018 Day 3 D しりとり圧縮 (Shiritori Compressio

問題 解法 この解法はばたこ(@btk15049)さんから聞いたものになります。 dp[i] = i番目の単語までで、消去できる単語数の最大値 とします。 すると、i番目の単語を利用して、それより前の単語を消すかどうかの2パターンにまず分かれます。 i番目の単語を利用…

AOJ 1522 - Planarian Regeneration

問題 提出コード 数ヶ月放置してから考察しなおしたらすんなりいきました。 解説がなくてわからない問題は寝かせるのも大事だと思います。 解法 まず、サンプルケースなどを利用して手元で計算すると、 (縦における原点からの距離×縦の辺の長さ、の総和)×(横…

Benelux Algorithm Programming Contest 2016 D Bridge Automation

問題 橋の下をN隻の船がくぐります。船がくぐるには、橋を上げないといけません。 橋を上げる、もしくは下すのには60秒かかります。 船が橋をくぐるのには20秒かかります。 また、船は橋の前に到着してから1800秒(30分)待機することができます。 船が到着す…

ABC006 D - トランプ挿入ソート

問題 提出コード 解法 基本的に、1つのトランプは1回操作するだけで必ず正しい位置に戻せるので、最悪N回の操作が必要になります。 そして、操作の回数を最小にするには、そもそも操作しないトランプの枚数を最大化すればいいことになります。 これはつまり…

SnackDown 2016 - Jealous Numbers

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

AOJ 2199 - Differential Pulse Code Modulation

Differential Pulse Code Modulation 提出コード 差の二乗を最小化したいので、動的計画法を利用します。 とし、入力信号の番目を見るとき、複合化後の出力信号の値がになるような遷移の中で、求めたい値の最小値を記録します。dpの配列は大きな値で初期化し…

AOJ 2607 - Invest Master

Invest Master 提出コード 一見どっから手を付ければいいか悩みますが、わかるとすごくスッキリします。 手数料が何もないので、毎日株をすべて一度手放し換金するものとします。とくに2日以上同じ株を持ち続けるメリットはありません。 そこで、i日目でうま…

AOJ 2013 - Osaki

Osaki 提出コード 発車時刻と到着時刻のペアを入力しているわけではない上、入力時点ではソートされているわけではないことに注意します。 というわけで、入力を受け取るときは、発車時刻、到着時刻それぞれ別でまとめておき、入力後にそれぞれソートします…

ARC028 D - 注文の多い高橋商店

D - 注文の多い高橋商店 提出コード 満点を取るには、ほぼでクエリにこたえていかないといけません。 そこで、 ans[i][j] = i番目の品物を使わずにj個選ぶ方法 とすると、与えられたk、xを用いてans[k][m-x]を参照するだけで答えを出すことができます。 まず…

動的計画法における重複組み合わせの式変形について

蟻本に載っている重複組み合わせの式変形がピンとこなかったので、頭の整理をするためにメモを。 問題 種類の品物が存在し、番目の品物が個あるとき、これらの中から個選ぶ組み合わせの総数を求めよ、というものになります。 解法 まずはの解法からです。 番…

ARC083-E - Bichrome Tree

問題 提出コード ほとんど自力で解けたのでなかなかではないかなーと思ってます! 問題の制限より、頂点の番号が大きい方から順番に見ていくと、そのとき見ている頂点は必ず木の根になっています。 なので、番号が大きい方から順番に、そこを根とする部分木…

京都大学プログラミングコンテスト(KUPC)2013

競プロの練習会で、こちらのセットを使用したバチャコンをチームで行ったので解いた問題についてのメモをしていきます。 チームメイトはICPC出場時と同じくやまさん(@yamasangamasan)、べるくん(@dora_marutation)でした。加えて、相手チームがICPC本戦出場…

JOI 2012 予選 D 暑い日々

JOI 2012-2013 予選 問題4 提出コード 動的計画法を使うことを考えます。 まず、dp[i][j]として、j日目にi番目の服を着たときの、1~j日までの、「派手さの差の絶対値」の合計の最大値、とすると、 dp[i][j]=max(dp[k][j-1]+k番目の服とj番目の服の差の絶対…

AOJ 1603 - 500円玉貯金

500-yen Saving | Aizu Online Judge 提出コード 最終的な目標は、 ➀ 500円玉の枚数をできるだけ多くする ➁ ➀の中で、購入額を最小にする という二つなので、これを評価値として動的計画法を利用します。 動的計画法をする前に、少しだけ考察をします。 ある…