ＡＢＣ１１４ C - 755

初めに思ったこと：

・全探索は難しそう。Ｏ（Ｎ）＝１０＾９

・桁ＤＰかな？

・ずるずると桁ＤＰの沼にハマる

コンテスト後：

bit全探索を思いつく。

具体的には、3,5,7を0,1,2に対応させてbit全探索。

計算量はＯ（１０＊１０＊３＾１０）≒１０＾６で、間に合う。

注意点：

・桁それぞれについてbit全探索する必要がある。

実装例：

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

signed main() {
  int N;
  cin >> N;

  //Ｎの桁数を求める。
  int tmp = N;
  int cont = 0;
  while (tmp > 0) {
    tmp /= 10;
    cont++;
  }

  int ans = 0;
  //i桁の整数を全探索。
  for (int i = 3; i <= cont; i++) {
    //３bit全探索
    for (int bit = 0; bit < pow(3, i); bit++) {
      //３、５、７の個数をカウント。0->3,1->5,2->7に対応する。
      int mp[3];
      mp[0] = mp[1] = mp[2] = 0;

      int tmp = 0, now = bit;
      for (int j = 0; j < i; j++) {
        int x = now % 3;
        mp[x]++;

        if (x == 0) tmp += 3;
        if (x == 1) tmp += 5;
        if (x == 2) tmp += 7;

        now /= 3;
        tmp *= 10;
      }

      tmp /= 10;

      //条件を満たすかチェック
      if (tmp <= N && mp[0] != 0 && mp[1] != 0 && mp[2] != 0) ans++;
    }
  }

  cout << ans << endl;
  return 0;
}

悔しいです。

補足

再帰関数でもできるそうなので、そちらのコードも載せておきます。

なお、引数のｘ３～ｘ７は必要ありませんが（ｎから判別できるため）、書いた方が楽です。

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

int N;

//n:=今見ている数
//x3,x5,x7:=順に3,5,7が使われたかどうか。使われている場合true
int rec(int n, bool x3, bool x5, bool x7) {
  if (n > N) return 0;
  int res = 0;
  //今見ている数ｎが条件を満たすかどうか。満たすならばres++;
  if (n <= N && n != 0 && x3 && x5 && x7) res++;

  //nの語尾に３を付ける操作は、ｎを１０倍して3足せば良い。以下同様。
  //また３を足した場合、３は少なくとも使われているのでtrueにして再帰呼び出しする。
  res += rec(n * 10 + 3, true, x5, x7);
  res += rec(n * 10 + 5, x3, true, x7);
  res += rec(n * 10 + 7, x3, x5, true);
  return res;
}

signed main() {
  cin >> N;
  cout << rec(0, false, false, false) << endl;
  return 0;
}

こっちの方が簡潔で美しいですね。