競プロ日記

問題
ACコード
WAコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 28;
constexpr lint   INFL = 1LL << 60;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  string n;
  cin >> n;
  const int len = n.length();
  // dp[桁][3出た][5出た][7出た][nと一致][上位桁が全て0]
  int dp[11][2][2][2][2][2] = {0};
  dp[len][0][0][0][1][1] = 1;
  vector<int> num{3, 5, 7, 0};
  rrep (i, len) {
    int digit = n[len - i - 1] - '0';
    rep (j, 4) {
      vector<bool> next(4);
      next[j] = true;
      const int x = num[j];
      bool big = x > digit, same = x == digit;
      rep (a, 2) {
        rep (b, 2) {
          rep (c, 2) {
            rep (d, 2) {
              if (d && big) continue;
              rep (e, 2) {
                if (next[3] && !e) continue;
                int na = a | next[0];
                int nb = b | next[1];
                int nc = c | next[2];
                int nd = d & same;
                int ne = next[3];
                dp[i][na][nb][nc][nd][ne] += dp[i + 1][a][b][c][d][e];
              }
            }
          }
        }
      }
    }
  }
  int sum = 0;
  rep (i, 2) sum += dp[0][1][1][1][i][0];
  cout << sum << endl;
  return 0;
}

上から順番にやっているだけなのに桁DP強化月間みたいになってる。
そもそも想定解が桁DPではないが、いかにも桁DPできそうだったので・・・。
全探索の方はすぐに思いつかなかったが、桁DPを縛ったとしたら思いつけたかなぁ、微妙だ。

桁DPでやることを考えたら青くらいはあるんじゃないか？
そもそも桁DP自体が結構難易度高めで、桁DPというだけで水色以上レベルなのだと最近理解した。


今回の桁DPは最近得た知見を総動員しようと頑張ってみた。
前回の記事ABC117 D XXORの「桁DPは上の桁が全て0の場合、DPが初期値かどうかで遷移を変える」という知見も使おうと試行錯誤したのだが、全然うまくいかなかった。
やってみれば理由は明白で、0という数字が出てこないことを前提とした遷移をしているのに、上位桁が全て0の場合のみ0が出てくることが許されるためだ。
いわゆるLeading zero。
「このLeading zero内での遷移をLeading zero以外で0が出てきた場合の遷移と同様に扱えるか」、これが重要なのだと気付いた。
前回の初期値かどうかで遷移を変えるという部分も、初期値である=Leading zero内であるということなので、初期値を考えることの真髄はLeading zeroを考えることだったのだ。
これに気付けたので、DPの状態に「0以外の値が出てきたか」というのを持つことでACできた。

DPの遷移はABC138 F Coincidenceの経験を多いに生かした。
全ての遷移前を、ありえる可能性の回数(今回は0,3,5,7の4回)見て、条件によってcontinueしたり遷移先を変えたりする。
初見ではこんなDPできるか！と思ったものの、2回目の今回、問題のランクはかなり下がったとは言え、この書き方はかなり理にかなってるなと感じられた。
コード中の遷移ではあまり良くない部分でna~neを宣言しているが、今回やABC138Fのように遷移や条件が多い場合、速度や効率重視するより見やすさ大事にした方が良さそう。
dpの全ての状態と遷移は以下の通り。

dp[i][a][b][c][d][e] = dp[桁数][3を1度以上使った][5を1度以上使った][7を1度以上使った][今の所Nと一致][今の所0しか使っていない(Leading zero内かどうか)] = 何通りか
digit = Nのi桁目の数字
x = 遷移しようとしている数(0,3,5,7)

dp[i][na][nb][nc][nd][ne] += dp[i+1][a][b][c][d][e]の遷移を桁数×(0,3,5,7)の4回ループする。
1. x=0かつe=0なら、Leading zero外で0を選択することになるのでcontinue。
2. d=1かつdigit<xなら、Nを超えた遷移になってしまうのでcontinue。
3. x=3,5,7のとき、a,b,cのxに対応する部分を立ててそれ以外はそのまま(na, nb, nc)。
4. d=1かつdigit==xのときのみ、今の所Nと一致を継続できるのでnd=1、それ以外はnd=0。
5. Leading zero内を継続できるのは、今の所Leading zero内で遷移先が0のときのみである。
x=0の遷移が許されるのは1.の条件よりLeading zero内のみなので、x=0のときのみne=1。


ここから苦労話。

まず1番軽いところから。
さすがにDPの配列がここまで深くなるとvectorで書きたくないなぁとなって通常の配列を使ったのだが、普通の配列は0で初期化されないのである・・・。
ずっとvectorばかり使っていたらつい忘れてしまう。
値が明らかにおかしいと遷移を見てみると、オーバーフローのような値が出ていたので、配列外参照がないことを確かめた後、配列は0じゃないじゃんとすぐにたどり着けた。
学生時代に、「{}でも{0}でも初期化できるんだへー」と思ったのを思い出しながら{0]にしておいた。

i桁目の値をどう取り出すかがかなり大事だった。
最初文字列でやろうと思ったのだが、もともと数値なものを文字列に直してまた数値に直して計算するのはいかがなものかと。
10進数だから10で割って色々したらできるだろうとこの方針でやってみたらできたのだが、いかんせんややこしい。
初心に戻って文字列にしたらとても分かりやすい・・・。
さらに最上位の桁が既に分かっているので、NがLeading zeroということがなくなって遷移条件もすっきりできた。
Leading zero内かどうかを判断するために変な条件つけてミスったり、そこだけ抽出して遷移したがために肝心のDPの遷移が間違っていることに全然気付けなかったりと散々だった。
WAコードはこの方針でやっており、桁を取り出す部分やLeading zeroの判定部分は正しく行えているのだが、ACコードのほうが100倍分かりやすい。

もう1つ苦労したのが、テストケースを間違えて見ていたこと(?)。
この問題はテストケースが公開されているので、4つだけWAというところでテストケースを確かめに行ったのだが、間違えてDのテストケース(b16)を見ていた。
最近C問題で詰まるなんてことがなかったのでつい・・・。
他の人の解説のACコードもコードテストに貼り付けて確かめながらやっていたのだが、なんでこの遷移でだめなんだ・・・と、半ばやけくそでACコードにテストコードを貼り付けてみたところ、自分のコードと同じ結果を出したところでおや？となり気付いた。
試しにジャッジしてみたらあっさりAC。
何時間悩んだか。
運悪いことに、Dの入力も出力も同じような値だったのでぱっと見では気付けなかった。
解説も見たのに全然ACできなくて、理解が浅いのか実装をミスっているのか分からなくて何時間も悩み続けるこの感じ、最近は知識も実装力もついてきてほとんどなかったのだが久々に味わった。
もうちょっとで誰かこの桁DPを完成させてくれーーーと未解決問題として記事を書くところだった。


新ABC解き始めた頃、ほとんどテストケース公開されていないのがかなり辛い気持ちだったが、最近は公開されていてもテストケースはあまり見ないようにしている。
というのも、解説記事を見れば8割くらい正解のコードは書けるはずなので、そこからテストケースを見て答えが合うようにコードを弄るのは、意味も分からずパズルをかちゃかちゃして合わせているようであまり身になる気がしないからである。
見ないことに拘って時間を溶かすのも頭悪いが、見てさらに時間を溶かしたのは頭悪すぎる・・・。