読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

yukicoder No.319 happy b1rthday 2 me

この記事は読者が桁DPを知っているという前提で書かれています。桁DPがわからないという方はこちらの記事へ。

問題文

http://yukicoder.me/problems/850

解法

  • A~Bの中にある12の個数
  • 繋げるときに生まれる12の個数

の和が求めたい値になる。それぞれの求め方を順に説明する。

A~Bの中にある12の個数

  • f(N) := 0~Nにある12の個数

という関数を作れば、f(B)-f(A-1)で計算できる。f(N)の計算は次のような桁DPをすればいい。

dp[ 決定した桁数 ][ N未満確定か ][ 末尾が1か ][ 12の個数 ] := この条件を満たす数の総数

遷移方法は「末尾が1である数に2を付加すれば12がひとつできる」ということを考えると分かる。

繋げるときに生まれる12の個数

****1に2****を繋ぐと12が生まれる。 2つの数の差が1なので最上位桁の数字は一致しており、実は2***1と2***2の組になっている。 そのため2***1の形の数の総数を数え上げればいい。

  • g(N) := 0~Nにある2***1の形の数の総数

という関数を作れば、g(B-1)-g(A-1)で計算できる。 g(B)ではなくg(B-1)を計算するのはなぜかというと、Bが2***1の形だったとしても次の数がなく12が生まれないからである。

g(N)の計算も桁DPでできる。 最上位桁が2であるという条件を考えるのにleading zeroの情報が必要なため、次のようなDPになる。

dp[ 決定した桁数 ][ N未満確定か ][ leading zeroを抜けたか ] := この条件を満たす数の総数

遷移方法は次の2つを考えると分かる。

  • leading zeroを抜けるタイミングで2を使うようにする
  • 最下位桁には1を使う

なお、例外的に1,2は12を生むので微調整が必要。


似たようなDPを2回書くのは面倒だったので、共通部分を使いまわした。

yukicoder No.319 happy b1rthday 2 me

ひとこと

ABC029 Dみたいに解けるのは分かるんだけど、結局思考停止して桁DPしてしまった。