スクリーンショット_2020-02-10_12

ABC154:問題Eで桁DPの反省をしたら、前々から理解できていなかったABC007:問題DもACできて満足している

2月9日に、競技プログラミングサイトAtCoderで開催された競技プログラミングコンテスト「AtCoder Beginner Contest 154」に参加した。

【今回の結果】
順位:約6145人中3126位(上位51%くらい)
レート:651(前回:651 前回比:+1)
パフォーマンス:662

全 6 問出題され、問題 A、B、C、D は AC できた。WA を出さなかった点はよかったが、問題 D の問題文を飛ばし読みしてしまい、80分くらい使ってしまった。毎回しょうもないミスをしてしまうよなぁ。

昨年末くらいから AtCoder の過去問である ABC001 から順番に問題 C と問題 D を埋めている。難易度を調べて難易度が低いものからやってもよかったが「もう問題 C も D も全部さらっとできないといけないな」と感じているので、難易度で並び替える作業を省いた。空き時間でやっていて、さらにCodeforces と平行して埋めているため、ペースは早くない。例えば、ABC003 の問題 D については 2、3 日使ったりしている。数日前からやっていたのは ABC007 の問題 D。偶然にも今回の問題 E 同様、桁 DP を使うと解けるという問題だった。しかし、桁 DP を理解できず、 ABC007 の問題 D もAC をとれていなかったので、今回の問題 E も手も足もでなかった。「やっぱり、あのときちゃんとやればよかったな」とよくある後悔しながら、今回は問題 E について復習する。

問題 E について

問題文は以下のリンクをご確認ください。

桁 DP については、以下の記事とその記事内のリンク先の記事がすごく参考になりました。

「 0 以上 N 以下の整数で、条件を満たすものの個数を求めよ」
「 0 以上 N 以下の整数で、条件を満たすものの最大値を求めよ」
のような問題でよく用いられる技法として桁 DP がある。

これを覚えておくと、今回の問題文を読んだだけで「お、桁 DP だな」と反応できるようになる。

AtCoderで提出されているいろいろな方のコードを見ていますと、桁DPは、

dp[i][j][k]
i:確定している桁数
j:N未満(1)か否(0)か
k:条件

としている方をよくみたのですが、AtCoderの解説動画の方のマネをして真ん中に条件を持ってきた。すなわち、

dp[i][j][k]
i:確定している桁数
j:条件
k:N未満(1)か否(0)か

で考えようという結論になった。解説動画などをみて実装して AC したコードは以下の通り。

問題 E で AC したコード

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

// dp[i][j][k]
// i:確定している桁数(最大100桁だが少し多めに)
// j:Kより、0から3まで
// k:N未満(1)か否(0)か
int dp[105][4][2];

int main() {

 string N;
 cin >> N;

 int K;
 cin >> K;

 // 桁数
 int n = N.size();

 // 初期化
 dp[0][0][0] = 1;

 for (int i = 0; i < n; i++) {
   for (int j = 0; j < 4; j++) {
     for (int k = 0; k < 2; k++) {

       // 1桁ずつ見ていく
       int c_ = N[i] - '0';

       for (int c = 0; c < 10; c++) {

         // 値を入れる場所を決める
         int i_ = i + 1;
         int j_ = j;
         int k_ = k;

         // 条件 -----
         // j が 0 じゃない場合は次(j_++)を見るが
         // K を超えていたら条件を満たさないので、このループは終わり
         if (c != 0) {
           j_++;
         }
         if (j_ > K) {
           continue;
         }

         // N未満(1)か否(0)かのチェック -----
         // k が N 未満か確定していないときは
         // 見ている桁の値(c_)が c 未満のときは条件を満たさないので、このループ終わり
         // 見ている桁の値(c_)が c を超えると N 未満が確定する
         if (k_ == 0) {
           if (c_ < c) {
             continue;
           } else if (c < c_) {
             k_ = 1;
           }
         }

         // 決めた場所に値を入れる
         dp[i_][j_][k_] += dp[i][j][k];

       }
     }
   }
 }

 // n 桁の値で 0 じゃない数字が K 個あって、
 // N 未満が確定している場合と確定していない場合の値を足したものが答え
 int answer = dp[n][K][0] + dp[n][K][1];
 cout << answer << endl;

 return 0;

}

そして、ABC007 問題 D もできるようになった

桁 DP がそこそこ理解できたので、ABC007 問題 D を考える。

問題文は以下のリンクをご確認ください。

ABC154 問題 E は「0 じゃない数が K 個」という条件だったが、ABC007 問題 D は「4 と 9 が使われている数字の個数」という条件になる。したがって、桁DP部分の実装については、上記の問題 E のAC したコードの「// 条件 -----」や「// N未満(1)か否(0)かのチェック -----」の部分などを少し調整したら、なんとか AC とることができた。ABC154 問題 E では 2 回桁 DP する必要があるから、ABC154 問題 E と全く同じというわけにはいかないが、両方ともいい勉強になった。

ちなみに、ABC007 問題 D で AC したコードは以下の通りです。

ABC007 問題 D で AC したコード

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

long long count(long long n) {

 string s = to_string(n);  

 // dp[i][j][k]
 // i:確定している桁数(ちょっと多めに)
 // j:条件を満たすか(1)か否(0)か
 // k:N未満(1)か否(0)か
 long long dp[25][2][2];

 // 配列の全部に 0 を入れる
 for (int i = 0; i < 25; i++) {
   for (int j = 0; j < 2; j++) {
     for (int k = 0; k < 2; k++) {
       dp[i][j][k] = 0;
     }
   }
 }

 // 初期化
 dp[0][0][0] = 1;

 for (int i = 0; i < s.size(); i++) {
   for (int j = 0; j < 2; j++) {
     for (int k = 0; k < 2; k++) {

       // 1 桁ずつ見ていく
       int c_ = s[i] - '0';

       // N未満の場合は、9 まで調べる
       if (k == 1) {
         c_ = 9;
       }

       for (int c = 0; c < c_ + 1; c++) {
         
         // 値を入れる場所を決める
         int i_ = i + 1;
         int j_ = j;
         int k_ = k;

         // 条件 -----
         // j が 4 か 9 の場合は条件を満たす
         // j が 4 か 9 以外の場合は条件を満たさない
         if (c == 4 || c == 9) {
           j_ = 1;
         }

         // N未満(1)か否(0)かのチェック -----
         // k が N 未満か確定していないときは
         // 見ている桁の値(c_)が c 未満だと確定できない
         // 見ている桁の値(c_)が c を超えると N 未満が確定する
         if (c_ < c) {
           k_ = 0;
         } else if (c < c_) {
           k_ = 1;
         }

         // 決めた場所に値を入れる
         dp[i_][j_][k_] += dp[i][j][k];
       
       }
     }
   }
 }

 long long ans = 0;
 ans = dp[s.size()][1][0] + dp[s.size()][1][1];
 return ans;
}

int main() {

 long long A, B;
 cin >> A >> B;
 
 cout << count(B) - count(A - 1) << endl;

 return 0;

}

昨年末くらいから AtCoder の過去問である ABC001 から順番に問題 C と問題 D を埋めていると書きましたが、2月10日現在でABC001からABC007が終わりました。約6週間で14問。残りはざっと数えて150くらいあるから、このペースだと全部終わるのに60週間以上かかるから、1年以上かかる計算だな。長期間楽しめる趣味になってきた感じだ。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

スキありがとうございます!
2
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。

この記事が入っているマガジン

コメントを投稿するには、 ログイン または 会員登録 をする必要があります。