ツバサの備忘録

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

桁DP

AOJ 0570 - ジグザグ数 (Zig-Zag Numbers)

問題 提出コード 解法 以下のジグザグ数の個数から、以下のジグザグ数の個数を引くと答えになるので、あとは以下のジグザグ数の個数を求める方法がわかればよいです。 桁が明らかに大きいので桁DPをしていきます。 について、 : 今見ている桁の番号 : 以下が…

ABC129 E - Sum Equals Xor

問題 提出コード 解法 制約を見ると明らかに桁DPのような匂いがするので桁DPをしました。 の上から桁目をとします。 となるが存在した場合、をすると繰り上がりが発生するので、となります。逆に、それ以外のはどれを使用してても問題の条件を満たします。 …

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

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

ABC117 D - XXOR

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

Typical DP Contest E - 数

問題 提出コード 解法 制約をみてもわかるように桁DPです。 とします。は、上から桁目を決める段階、という意味です。は、今作成している数字の桁和をで割った余りがであるという意味です。は、今作成している数字が未満であることが確定しているかどうか、…

ABC050 D - Xor Sum

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

ABC007 D - 禁止された数字

D - 禁止された数字 提出コード 問題をぱっと見て桁DPっぽいなーと思ったので桁DPをやります。 A-1、もしくはB以下の、4または9が含まれている数の個数をそれぞれ桁DPで調べて、最後にB以下の個数からA-1以下の個数をひいてあげれば答えになります。 dp[i][j…