質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.53%

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

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 372

Taka787

score 16

長文失礼いたします。

【要件】
二つの正整数昇順列 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以上になると実行時間が3秒を超えましたと出て、エラーになります。
自分なりに考えたのですが、ループの数が多くなるのが原因なのかと思うのですが、コードをどう修正すればよいかがいまいちよくわからない状態です。
対処法を教えていただければ幸いです。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

+3

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/04 21:02

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

    キャンセル

checkベストアンサー

+1

最後の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;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/04 21:00

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

    キャンセル

+1

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

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]なら
  同じ数が含まれていた数を+1して、
  次はf[n+1]とg[m+1]を比較する

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/04 20:58

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

    キャンセル

+1

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

#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;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/04 20:57

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.53%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る