昇順列の共通要素数を出力

Question

長文失礼いたします。

【要件】
二つの正整数昇順列 f: f0,f1,...（ 0＜f0＜f1＜...）と g: g0,g1,...（ 0＜g0＜g1＜...） とが与えられたとき、その両方に現れている数値の個数を数えたいです。

二つの正整数昇順列の組は、正整数 n を与えると定まる。具体的には、関数呼出し sfg(n); を行なうと、その後、関数呼出し f() は正整数昇順列 f の数値を順に返してくるし、関数呼出し g() は正整数昇順列 g の数値を順に返してくる。それぞれの正整数昇順列が尽きてしまうと、これらの関数呼出しは -1 を返してくる。 正整数 n を与えて定まる正整数昇順列 f, g は、いずれもその長さが n 未満である。

※関数sfg、f、gの定義は別ファイルにあり、同時にコンパイルすることによって実行します。

入力：　

二つの昇順列を指定する正整数 n が標準入力に与えられる。

出力：

n で定まる二つの正整数昇順列 f, g の両方に現れている数値の個数を必要最小限の桁数で1行として標準出力に書き出す。

#include <stdio.h>

void setfg(int n);
int f();
int g();

int main(int argc, char *argv[]){
    long long int n;
    int i, x, y, z, fff, ggg, ans;
    ans = 0;
    
    
    
    scanf("%llu", &n);
    
    int F[10000000] = {0};
    int G[10000000] = {0};
    
    setfg(n);


        for(i=0; i < n; i++) {

            F[i] = f();

            if(F[i] > 0) {
                fff++;
            }
        }
        
        for(y=0; y < n; y++) {

            G[y] = g();
         
            
            if(G[y] > 0) {
                ggg++;
            }
        }

        for(x =0; x < fff; x++) {
            for(z= 0; z < ggg; z++) {
                if(F[x] == G[z]){
                    ans++;
                }    
            }
        }

    printf("%d\n", ans);
    
    return 0;
}

【うまくいかない点】
入力値が501以上になると実行時間が３秒を超えましたと出て、エラーになります。
自分なりに考えたのですが、ループの数が多くなるのが原因なのかと思うのですが、コードをどう修正すればよいかがいまいちよくわからない状態です。
対処法を教えていただければ幸いです。

Answer 1

対処法を教えていただければ幸いです。

fもgも昇順である、という条件を活かせば、配列への保存すら不要になると思います（記憶するのは「fの最後に出た値」と「gの最後に出た値」、そして「今までのカウント」だけで大丈夫です）。

Comments

[Taka787]

昇順に並んでいることに気づきませんでしたので、難しく考えていました。
アドバイス有難うございました。

Answer 2

...こんだけ↓のことちゃうん?

#include <stdio.h>
#include <stdlib.h>

int inxf;
int inxg;

void reset() {
  inxf = 0;
  inxg = 0;
}

int f() {
  static int data[] = { 1, 2, 3, 3, 4, 4, 5, 7, -1 };
  int v = data[inxf];
  if ( v >= 0 ) ++inxf;
  return v;
}

int g() {
  static int data[] = { 3, 4, 4, 5, 6, 7, -1 };
  int v = data[inxg];
  if ( v >= 0 ) ++inxg;
  return v;
}

int set_intersection(void (*fn)(int)) {
  int count = 0;
  int vf = f();
  int vg = g();
  while ( vf > 0 && vg > 0 ) {
    /* 小さいほうをひとつ進める。同じなら両方進める。 */
    if      ( vf < vg ) { vf = f(); }
    else if ( vf > vg ) { vg = g(); }
    else                { fn(vf); vf = f(); vg = g(); ++count; }
  }
  return count;
}

void print(int n) {
  printf("%d\n", n);
}

int main() {
  int count;
  reset();
  count = set_intersection(&print);
  printf("--- %d elements found.\n", count);
  return 0;
}

Comments

[Taka787]

わかりやすいコードありがとうございます。
よく考えてみれば、そんな難しいことではないことに気づきましたww

Answer 3

両方とも昇順で並んでいるのですから、

f[n]とg[m]を比較して、f[n]>g[m]なら、
　  次はf[n]とg[m+1]を比較する。
f[n]<g[m]なら
    次はf[n+1]とg[m]を比較する
f[n]=g[m]なら
　　同じ数が含まれていた数を＋１して、
　　次はf[n+1]とg[m+1]を比較する

という演算を繰り返せば足ります。nかmの少なくとも一方が+1されますから、繰り返しが n 回を超えることはありません。　　

Comments

[Taka787]

昇順に並んでいることを忘れていました。的確なアドバイス有難うございました。

Answer 4

最後の2重forループでは,
・内側ループは, 一致もしくは大きくなったら break 出来るはず.
・外側ループが回るとき, 内側ループの開始は前回の内側ループの break 時の値からで良いはず.
と想像します.

これであってますでしょうか.

int main(int argc, char *argv[]){
    int fv, gv, ans=0;
    long long int n;

    scanf("%llu", &n);
    setfg(n);

    while(1) {
        fv = f();
        gv = g();
        while(fv != -1 && gv != -1 && fv != gv) {
            if(fv < gv) fv = f();
            if(fv > gv) gv = g();
        }
        if(fv == -1 || gv == -1) break;
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}

Comments

[Taka787]

とても分かりやすい説明、コードありがとうございました。
おかげさまで解決することが出来ました。