😊

三井住友信託銀行プログラミングコンテスト2019 | D - Lucky PIN

2020/11/29に公開

競プロ

貪欲法

動的計画法

木

tech

問題

考えたこと

そのまま貪欲にやると $O(N^3)$ の時間がかかりTLEとなる。効率的な解法を考える必要がある。

入力された $S$ の中の数字がどの位置にあるか大事である。以下のようなTrie木のような木を作れば順序を保ちながら可能な暗証番号を記録できる。

暗証番号は3桁なので木の深さは3までと制限できる。よってノードの数は最大でも $10^3$ 程度であり間に合わせる事ができる。

コード

実装時のTips

木は構造体をコピーさせないためにポインタで作る

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

struct Node {
  map<char, Node *> children;
  int depth = 0;
};

void add(Node *node, char c) {
  if (node->depth == 3) {
    return;
  }
  for (auto m : node->children) {
    add(m.second, c);
  }
  if (node->children.find(c) == node->children.end()) {
    Node *child = new Node();
    child->depth = node->depth + 1;
    node->children[c] = child;
  }
}

unordered_set<string> s;

void search(Node *node, string cur) {
  if (node->depth == 3) {
    s.insert(cur);
    return;
  }
  for (auto m : node->children) {
    search(m.second, cur + m.first);
  }
}

// 木に順に入れていき最後に探索する
int main() {
  Node *root = new Node();
  ll n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    char c;
    cin >> c;
    add(root, c);
  }
  search(root, "");
  cout << s.size() << endl;
}

別解

ACしたあとに解説をみてみたらいろんな解法があったので紹介する。

暗証番号を全探索

暗証番号は $000$ から $999$ までの1000個なので暗証番号を $V$ とし、以下を1000回とけばいい。

$S$ から、 $N-3$ 桁を消して暗証番号 $V$ を作ることができるか

コードは以下となる。

#include <bits/stdc++.h>

#include <atcoder/all>
#include <boost/format.hpp>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  string s;
  cin >> n >> s;

  ll ans = 0;
  for (int i = 0; i < 1000; i++) {
    string t = (boost::format("%03d") % i).str();
    ll si = 0, ti = 0;
    while (si < n && ti < 3) {
      if (s[si] == t[ti]) {
        si++;
        ti++;
      } else {
        si++;
      }
    }
    if (ti == 3) {
      ans++;
    }
  }
  cout << ans << endl;
}

三井住友信託銀行プログラミングコンテスト2019 | D - Lucky PIN

問題

考えたこと

コード

別解

暗証番号を全探索

参考

Discussion