問題 提出コード 解法 全方位木dpをします。 初めに頂点1が根である際の値を求めます。 を根とする部分木について、を黒で塗った際の部分木の塗り方 とすると、頂点の子の集合をとして、 となります。 を根とした際の求めるべき答え とすると、 となります。…

問題 提出コード 解法 はじめに、2次元累積和を用いて、ある長方形の範囲の需要の合計をで求めることができるようにしておきます。 ここから、DPを行います。 長方形の左上が,右下がとなるような範囲のグループの分け方の最適解 とします。最適解、なのでグ…

問題 提出コード 解法 が間に合うので、に設置した際に照らすことができるマスの個数がで求まれば、全探索をしつつ最大値を求めることでこの問題に答えることができます。 ということで、前計算をします。 まず、縦に伸びる光と横に伸びる光は無関係のため、…

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

問題 提出コード 解法 簡単のため、にも送風機があるとしてよいです。 矢の長さがのときの損失回数がわかっていれば、各クエリに対して二分探索をして答えを求めることができます。 ということで、長さがのときの損失回数を頑張って求めます。 送風機と送風…

問題 提出コード 解法 配置方法は9!通りなので、全てに対して探索を行いたいです。 ので、ある配置のときにかかる操作回数の最小値の求め方を探ります。 すると、次のようなことをすればよいことになります。 あらかじめ、文字列について、どの数字からどの…

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

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

問題 提出コード 解法 1つのマス目が、他のマス目に影響を及ぼすことも、影響されることもないので、それぞれのマスについて、-1でない場合に1へと変化させる魔力の最小値を求めればよいです。 ということで、マス目の現在の数字(0~9)を頂点、をからへ向かう…

問題 提出コード まずは、レベルバーガーをすべて食べたときの、食べる全体の枚数および食べるパティの枚数を求めます。 食べる全体の枚数をとすると、 となります。 食べるパティの枚数をとすると、 となります。 初期値は、です。 答えは、再帰によって求…

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

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

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

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

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

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

月曜土曜素因数 提出コード まずは、nの最大値である300000までの月曜土曜数を抽出し、動的配列に保存します。 愚直に1つずつ、7で割ったときの余りが1or6になっているかどうか調べて問題ありません。 そうしたら、次に月曜土曜素数を求めます。先ほど求めた…

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

D - おいしいたこ焼きの焼き方 提出コード mp[i][j] = からまでの、長方形の部分の美味しさの総和 (ただし、添え字が0以下のときは0) として、入力と同時に累積和をとっていきます。 すると、ある長方形をl,r,u,d(それぞれ長方形の左、右、上、下の辺の番号)…

なんだかんだまだARC出たことないので出てみたいですね A - Garden 提出コード (a-1)*(b-1)をすればよいです。 道の部分を無視して畑をくっつけると、実際に上の式のように、a-1とb-1の辺の長方形になります。 B - 105 提出コード 1からnまでの数字について…

バチャコン5回目です(4回目は復習回でした)。 A - New Year 提出コード 12月30日のn時から年が明けるまでにどれくらい時間がかかるか、という問題です。 12/31の一日分まるまる24時間+今日の残り時間(24-n)を出力します。 12/31の分は、問題を読み間違えてい…

目標は200位でした。レート順400位ぐらいだったので運次第、と思ってました A - コンテスト名 提出コード 頭が真っ白になったので素直に全部書き出しました。与えられる文字の長さがそもそも5に満たない場合の条件を途中まですっかり書き忘れていたので危な…