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

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

ただいまの
回答率

90.48%

  • C

    3835questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3631questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    422questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C,C++の課題でわからないことがありました。

解決済

回答 2

投稿

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

http://abc002.contest.atcoder.jp/tasks/abc002_4
このサイトの問題のD問題でわからないものがありました。
http://www.slideshare.net/chokudai/abc002
↑がこの問題の解説なんですが、「全てのパターンを列挙して、その中で派閥を作れる中で一番大きい派閥の人数を出力する」とありました。これがいまいちよくわからなくて、全てのパターンを列挙したあとの処理がわかりません。他人のコードを見たりしましたが説明文がなくてよくわかりませんでした。下のコードが正解のコードみたいなんですけど、このコードの内容を詳しく解説していただけると幸いです。

include <stdio.h>

include <string.h>

include <iostream>

using namespace std;

int maxFaction(int N, int G[12][12], int f[12], int a)
{
    int ret = 0;
    int tmp = 0;
    int i;

    if (a == N) {
        for (i = 0; i < N; i++) {
            if (f[i] == 1) ret++;
        }
        return ret;
    }

    if (f[a] == 0) {
        for (i = 0; i < N; i++) {
            if (a == i) continue;
            if (f[i] == 1 && G[a][i] != 1) break;
        }
        if (i == N) {
            f[a] = 1;
            ret = maxFaction(N, G, f, a + 1);
            f[a] = 0;
        }
        tmp = maxFaction(N, G, f, a + 1);
        ret = (ret < tmp ? tmp : ret);
    }

    return ret;
}

int main()
{
    int N, M;
    int x, y;
    int G[12][12] = { 0 };
    int f[12];
    int i;

    cin >> N >> M;
    for (i = 0; i < M; i++) {
        cin >> x >> y;
        --x, --y;
        G[x][y] = G[y][x] = 1;
    }

    memset(f, 0, sizeof(f));
    printf("%d\n", maxFaction(N, G, f, 0));

    return 0;
}

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

checkベストアンサー

+1

※完全な解説にはなっていないと思いますが、自分が試して分かったところまでを
 書きます。

上記のコードよりも
http://www.slideshare.net/chokudai/abc002
P18 おたっくすさんの回答C++
の方がシンプルだったので、こちらを元に解説します。
こちらの回答も最大クリープ問題を再帰を使って解いています。

動作確認時のコードは以下になります。
(実際に動かす場合は矩形選択などで行頭の行数を削除ください)

1    #include <iostream>
2    #include <cstdio>
3    #include <vector>
4    #include <map>
5    #include <set>
6    #include <algorithm>
7    #include <string>
8    #include <cstdlib>
9    #include <stack>
10    #include <queue>
11    #include <cmath>
12    using namespace std;
13    
14    int N, M, f[12][12] = { 0 }, ans = 0;
15    
16    void dfs(vector<int> v, int k = 0) {
17        //--------確認コードここから--------//
18        printf("v=[");
19        for (int i = 0; i < v.size(); i++) {
20            printf("%d", v[i]);
21            if (i != v.size() - 1) {
22                printf(", ");
23            }
24        }
25        printf("]");
26        
27        printf(" k = %d\n", k);
28        //--------確認コードここまで--------//
29    
30        if (k == N) {
31            for (int i = 0; i < v.size(); i++) {
32                for (int j = i + 1; j < v.size(); j++) {
33                    if (f[v[i]][v[j]] == 0) {
34                        //--------確認コードここから--------//
35                        printf("  知り合いでない関係がある\n");
36                        //--------確認コードここまで--------//
37                        return;
38                    }
39                }
40            }
41            //--------確認コードここから--------//
42            printf("  ★全員知り合い (int)v.size() = %d\n", (int)v.size());
43            //--------確認コードここまで--------//
44            ans = max(ans, (int)v.size());
45        }
46        else {
47            dfs(v, k + 1);
48            v.push_back(k);
49            dfs(v, k + 1);
50            v.pop_back();
51        }
52    }
53    
54    int main() {
55        cin >> N >> M;
56        for (int i = 0; i < M; i++) {
57            int x, y;
58            cin >> x >> y;
59            x--; y--;
60            f[x][y] = f[y][x] = 1;
61        }
62        vector<int> v;
63        dfs(v);
64        cout << ans << endl;
65    }

関数がどのように再帰で呼ばれているのかが
よく分からなかったので、dfs()の冒頭に、呼ばれた時点の
v, k を表示するようにしました。(17~28行目)

また、dfs()が呼ばれて、kがNと等しい場合にvで指定する人たちが
知り合いなのかを確認するため、確認結果を表示するようにしました。
(34~36, 41~43行目)

入力は以下を使用しました。
[input.txt]
5 3
1 2
2 3
3 4

入力データが、56~61行目で隣接行列(f[][])に格納されます。

実行すると、

v=[] k = 0
v=[] k = 1
v=[] k = 2
v=[] k = 3
v=[] k = 4
v=[] k = 5
  ★全員知り合い (int)v.size() = 0
v=[4] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3] k = 4
v=[3] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3, 4] k = 5
  知り合いでない関係がある
v=[2] k = 3
v=[2] k = 4
v=[2] k = 5
  ★全員知り合い (int)v.size() = 1
v=[2, 4] k = 5
  知り合いでない関係がある
v=[2, 3] k = 4
v=[2, 3] k = 5
  ★全員知り合い (int)v.size() = 2
v=[2, 3, 4] k = 5
  知り合いでない関係がある
v=[1] k = 2
v=[1] k = 3
v=[1] k = 4
v=[1] k = 5
  ★全員知り合い (int)v.size() = 1
v=[1, 4] k = 5
  知り合いでない関係がある
v=[1, 3] k = 4
v=[1, 3] k = 5
  知り合いでない関係がある
v=[1, 3, 4] k = 5
  知り合いでない関係がある
v=[1, 2] k = 3
v=[1, 2] k = 4
v=[1, 2] k = 5
  ★全員知り合い (int)v.size() = 2
v=[1, 2, 4] k = 5
  知り合いでない関係がある
v=[1, 2, 3] k = 4
v=[1, 2, 3] k = 5
  知り合いでない関係がある
v=[1, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0] k = 1
v=[0] k = 2
v=[0] k = 3
v=[0] k = 4
v=[0] k = 5
  ★全員知り合い (int)v.size() = 1
v=[0, 4] k = 5
  知り合いでない関係がある
v=[0, 3] k = 4
v=[0, 3] k = 5
  知り合いでない関係がある
v=[0, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 2] k = 3
v=[0, 2] k = 4
v=[0, 2] k = 5
  知り合いでない関係がある
v=[0, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 2, 3] k = 4
v=[0, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1] k = 2
v=[0, 1] k = 3
v=[0, 1] k = 4
v=[0, 1] k = 5
  ★全員知り合い (int)v.size() = 2
v=[0, 1, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 3] k = 4
v=[0, 1, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2] k = 3
v=[0, 1, 2] k = 4
v=[0, 1, 2] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3] k = 4
v=[0, 1, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3, 4] k = 5
  知り合いでない関係がある
2

と出ます。

k = 5時の出力を抜粋すると、

v=[] k = 5
  ★全員知り合い (int)v.size() = 0
v=[4] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3, 4] k = 5
  知り合いでない関係がある
v=[2] k = 5
  ★全員知り合い (int)v.size() = 1
v=[2, 4] k = 5
  知り合いでない関係がある
v=[2, 3] k = 5
  ★全員知り合い (int)v.size() = 2
v=[2, 3, 4] k = 5
  知り合いでない関係がある
v=[1] k = 5
  ★全員知り合い (int)v.size() = 1
v=[1, 4] k = 5
  知り合いでない関係がある
v=[1, 3] k = 5
  知り合いでない関係がある
v=[1, 3, 4] k = 5
  知り合いでない関係がある
v=[1, 2] k = 5
  ★全員知り合い (int)v.size() = 2
v=[1, 2, 4] k = 5
  知り合いでない関係がある
v=[1, 2, 3] k = 5
  知り合いでない関係がある
v=[1, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0] k = 5
  ★全員知り合い (int)v.size() = 1
v=[0, 4] k = 5
  知り合いでない関係がある
v=[0, 3] k = 5
  知り合いでない関係がある
v=[0, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 2] k = 5
  知り合いでない関係がある
v=[0, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1] k = 5
  ★全員知り合い (int)v.size() = 2
v=[0, 1, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3, 4] k = 5
  知り合いでない関係がある

となります。
ここでvの値に注目すると、0,1,2,3,4の全ての組み合わせパターンが
現れています。
k = 5の時、それぞれの組み合わせパターンに対して
vの人たちが互いに知り合いかを、確認しています。(31~40行目)

また全員が知り合いの場合、その時点で調べているグループの人数(v.size())が
ansよりも大きければ、ansを更新します。(44行目)
★がついているところが全員知り合いの時ですが、
その時のグループ人数は0,1,2なので、最大値2が最終回答となります。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

関数の再帰呼び出しについて調べると良いと思いますよ

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

  • 解決済

    二次元配列の入出力

    度々すいません。二次元配列入出力についての質問です。 n(任意)人の身長と体重をキーボードから読み込み、2次元配列に蓄えたうえで、その内容を入力順に出力するプログラムを作りたいので

  • 受付中

    C言語 動的メモリ確保とリスト(構造体)を利用したプログラム

    現在このような結果で表示されるプログラムの作成を試みています。 >0p↲ >p >1d↲ >pd >0i↲ >ipd >2a↲ >ipad というように、格納位置

  • 解決済

    【C言語】スタックをリストで実現するプログラム

    毎度お世話になっております。 高橋麻奈さんの「やさしいC アルゴリズム」をみて勉強しているのですが、リストを使ったスタックのコードで、がコンパイルエラーになってしまいました。 コ

  • 解決済

    コードを見てダメ出しや指摘などお願いします。

    #include <stdio.h> int main(void){     double a;     double b;        char o;  //演算子    

  • 解決済

    標準入力からの入力方法について

    以下のような行数の決まっていない数値を1つずつ標準入力から取得し(取得した数値はあとで利用したいので 全部まとめて配列などに入れて保持したい)ですが分かりませんでした。 1

  • 解決済

    C++でのオセロゲームについて

    色々手を尽くしましたが、自力で解決できないため教えていただければと思い質問いたします。 学習のためhttps://gist.github.com/mia-0032/5325961

  • 受付中

    Javaを使った性格診断プログラムを作りたいです。

    簡単な性格診断プログラムを作りたいです。 Java初心者です。 Javaを使って、簡単な性格診断プログラムを作ろうと思っています。 1~4の数字で入力して回答してもらう質

  • 解決済

    vector参照方法

    大学の課題で、0~9のうちの1つを入力するとそのローマ字(0ならばzero)が表示され、またその逆も可能なプログラム(zeroならば0)をvectorを用いて作るようにと出たので、

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

  • C

    3835questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3631questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    422questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。