ＡＢＣ１１４ D - 756

初めに思いついたこと：

・１００！を愚直に扱うのはまずい。（１５０桁くらいある）

・約数の個数なので、素因数分解した値を考えれば良さそう。

（この時、１００！を素因数分解しても、素因数の個数は（２＾１０）＾５０≒１０＾１５０よりせいぜい５００くらい。（余裕で扱える））

・N!=2^p2*3^p3*5^p5....の時、約数の個数は(p2+1)*(p3+1)*(p5+1)....となるのでこれを使えば約数７５個の条件もチェックできる。

mathtrain.jp

具体的には：

約数の個数が７５＝３＊５＊５=１５＊５＝３＊２５のとき、条件を満たす数はa^74またはa^2*b^4*c^4またはa^14*b4またはa^2*b^24のいずれかで表される。

よって、Ｎ！の素因数の個数をカウントしておけば、~乗になりうるかどうかがそれぞれ判定でき、素因数全体について全探索をすれば答えが求まる。

（素因数の種類はたかだか１００、なぜなら１０１以上の素数は１００！と互いに素である）

素因数の個数のカウントの仕方は、２～Ｎをそれぞれ素因数分解して、足し合わせていくだけ。

注意点：

a^4*b^4*c^2のとき、a<bなどの条件をつけてあげないと重複して数え上げてしまう。

私は条件の付け方を、for(i=2~){for(j=i+1~)}}のようにjについて、j=i+1スタートにした。

また、a,b,c（あるいはa,b）について、a==b||b==c||c==a == true　にならないように気を付けたい。明らかに条件が成立しなくなる。

例）２＾４＊３＾４＊２＾２＝２＾８＊３＾４　－＞　９＊５＝４５個　Ｘ

実装：

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

map<int, int> res; // map[i]:=N!を素因数分解したときiは何乗か。

//Ｏ(√n)
//素因数分解
void prime_factor(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        res[i]++;
        n /= i;
      }
    }
  }
  if (n != 1) {
    res[n]++;
  }
}

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

  //Ｎ！の各要素を素因数分解し、足し合わせる。
  for (int i = 2; i <= N; i++) {
    prime_factor(i);
  }

  int ans = 0;

  //a^4*b^4*c^2
  for (int i = 2; i <= N; i++) {
    for (int j = i + 1; j <= N; j++) {
      for (int k = 2; k <= N; k++) {
        if (i == j || j == k || k == i) continue;
        if (res[i] >= 4 && res[j] >= 4 && res[k] >= 2) ans++;
      }
    }
  }

  //a^14*b^4 または a^24*b^2
  for (int i = 2; i <= N; i++) {
    for (int j = 2; j <= N; j++) {
      if (i == j) continue;
      if (res[i] >= 14 && res[j] >= 4) ans++;
      if (res[i] >= 24 && res[j] >= 2) ans++;
    }
  }

  //a^74
  for (int i = 2; i <= N; i++) {
    if (res[i] >= 74) ans++;
  }

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

本番ではa^4*b^4*c^2の場合しか考えていなかった。

全体的に悔しいコンテストでした。

精進します。

ＡＢＣ１１４ 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;
}

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

ブログをはじめました。

競技プログラミングの解説ブログを書いてみることにしました。

私はプログラミングを知らない状態で競プロを始めた人間です。

なので、プログラミング未経験者の方々が競プロを始めたときに、私の軌跡を参考にできるようなブログが書けたらなと思います。

あまり気構えると飽きてしまう性分なので、徒然なるままに書いていきたい。