雑記

競技プログラミングについての話題(?)

桁DPのこと - 備忘録的な何か

 PCKダメでした。5完しかできなかったので精進します、といった感じですかね。

 

とりあえずJOI予選を通過できるよう頑張りたいと思います

 

 

前置きはここまでにして、なんか最近やった桁DPについて振り返りを兼ねて

 

abc029.contest.atcoder.jp

 

一年生向けにslackで1day3problemをしていたんですけど、(僕を含む)2年生以上も何かできるようにと問題を15問出しました。1day15problemの誕生です。

 

まあ挑戦してみるかくらいの気持ちで15問目に上の問題をいれたんですけど普通に解けたのでうれしかったです

 

小学生の感想文レベルの備忘録ですが許してください

 

〜問題の概要〜

入力として 1 以上 10^9 以下の N が与えます

1から N までの数字に何回1が出てきたか数えてね

 

みたいな問題です

 

もしかしたら数学的に解けるかもしれないけど桁DPで解きました

 

 

入力は int 型ではなく string に

#include <bits/stdc++.h>
using namespace std;

string S;

int main()
{
  cin >> S;

  return 0;
}

 

 最初は for を振り回して解くつもりだったけど桁DPさの先輩に再帰で書いた方がわかりやすいよって言われたので適当な dfs とかで再帰します

#include <bits/stdc++.h>
using namespace std;

string S;

int dfs(int i = 0)
{

}

int main()
{
  cin >> S;

  cout << dfs() << endl;
  return 0;
}

 

桁DPは頭から何桁目を見ているか、を使うのでまずはそのための変数 i を用意します

そして、今見ている数が N 以下かどうか判定するための変数を用意します。 tightさの先輩には tight をオススメされたので変数名には tight を使用します

#include <bits/stdc++.h>
using namespace std;

string S;

int dfs(int i = 0, bool tight = true)
{

}

int main()
{
  cin >> S;

  cout << dfs() << endl;
  return 0;
}

これは5桁の整数があって、4????と3????であれば4????の方が大きいよね、といった話です。

124?? と 124?? みたいな状態が tight is true な状態です。感じ取ってください。

最後に 1 がいくつ使われているかどうかを保持するための変数を用意します。僕は one を使用しましたのでそれでいきます

#include <bits/stdc++.h>
using namespace std;

string S;

int dfs(int i = 0, bool tight = true, int one = 0)
{

}

int main()
{
  cin >> S;

  cout << dfs() << endl;
  return 0;
}

今回の問題では遷移に必要な変数はこれだけでしたが、問題によってはもっと多くの変数が必要になるので適宜変更しながらどうぞ

あとは終了条件を書いて再帰します

#include <bits/stdc++.h>
using namespace std;

string S;

int dfs(int i = 0, bool tight = true, int one = 0)
{
  if (i == S.size()){
    return one;
  }

  int x = S[i] - '0';
  int ret = 0;
  int r = (tight ? x : 9);

  for (int j = 0; j <= r; j++){
    ret += dfs(i + 1, tight && x == j, one + (j == 1));
    //dfs(次の桁, 今まで tight かつ次も tight か, 使われた 1 の数)
  }

  return ret;
}

int main()
{
  cin >> S;

  cout << dfs() << endl;
  return 0;
}

今見ている数字は何かを変数 x に入れておきます

retを初期化します(return 用の変数)

r に、tight が true であれば x を(x より大きな数に遷移しないように)、false であれば 9 を入れておきます

あとは for 文で r 以下のとき dfs()を呼び出します

dfs() の引数はコメントを参照してください(わかりにくかったらごめんなさい)

ここまで書くと N が小さな値なら動きます(多分部分点は取れる)

ただ、このままだと全探索になってしまうのでメモ化して高速化しましょう

#include <bits/stdc++.h>
using namespace std;

string S;
int dp[10][2][10];        //桁数、tightかどうか、使われている1の数

int dfs(int i = 0, bool tight = true, int one = 0)
{
  if (i == S.size()){
    return one;
  }

  int &ret = dp[i][tight][one];

  if (ret != -1) return ret;


  int x = S[i] - '0';
  //int ret = 0;
  ret = 0;
  int r = (tight ? x : 9);

  for (int j = 0; j <= r; j++){
    ret += dfs(i + 1, tight && x == j, one + (j == 1));
  }

  return ret;
}

int main()
{
  cin >> S;

  memset(dp, -1, sizeof(dp));   //-1で初期化

  cout << dfs() << endl;
  return 0;
}

用意するテーブルは dfs の引数と全く同じなので特に考える必要はありません

入力される値はたかだか10桁なので i , one ともに 10 程度で十分です

あとは dp の値が取り得ない値で(ここでは -1)初期化しておわり

参照渡しとか tight , r を考えた人すごいなと思いました(小並感)

あとは同じ日にzig-zag numberやら禁止された数字やらをといて桁DPを解く人みたいになっていましたが少しは慣れることができたかなと思います

説明が下手なの申し訳ないといった感じですが、誰かの何かのヒントになればなと思います。

誤字脱字とかあったら言ってください><