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

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

ただいまの
回答率

90.99%

  • C++

    2940questions

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

任意の入力に対して長方形の面積の最大値を求めるプログラム

解決済

回答 1

投稿

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

l_h_l_h

score 3

Atcoder Beginner Contest071 C問題より、問題文は以下の通りです

問題文

太さが無視できる棒が N 本あります. i 番目の棒の長さは Ai です.

すぬけ君は,これらの棒から 4 本の異なる棒を選び,それらの棒を辺として長方形(正方形を含む)を作りたいです. 作ることができる最大の長方形の面積を求めてください.
制約
4≤N≤10^5
1≤Ai≤10^9
Ai は整数
http://abc071.contest.atcoder.jp/tasks/arc081_a

此方の問題を以下のプログラムで解いたところ、半分以上不正解となりましたが、理由が分かりません

   #include<iostream>
    #include<stdlib.h>
    using namespace std;

    int compar(const int *val1, const int *val2);

    int main(){
        int N,i,x=0,y=0;
        cin>>N;
        int A[N];
        for(i=0;i<N;i++){
            cin>>A[i];
        }
        qsort(A,N,sizeof(int),(int (*)(const void *, const void *))compar);

        for(i=0;i<N-1;i++){
            if(A[i]==A[i+1]){
                x=A[i];i+=2;break;
            }
             }
        for(;i<N-1;i++){
            if(A[i]==A[i+1]){
                y=A[i];break;
            }
        }
        cout<<x*y<<endl;
            return 0;

    }





    int compar(const int *val1, const int *val2) {
        if ( *val1 > *val2 ) {
            return -1;
        } else if ( *val1 == * val2 ) {
            return 0;
        } else {
            return 1;
        }
    }
コード

この問題文は、入力された数のうち、2回以上出現する数字を大きい順に2つ選び出し、その積を求めることと言い換えられます
入力された数字を配列Aに格納し、それをまず降順にソートします
ループ文により、A[i]とA[i+1]が同じであればその値をxに代入し、iに2プラスします
次に、iの値はそのままでyについても同じことをすることで、yに2番目に大きい2回以上出現した数字が代入されます
最後にそれらを掛けて出力して終了です
用意されている入力例で試したところ合ってそうなのですが、全然違うみたいです
どなたか、どこがおかしいか分かる方がいましたらご助力願います
よろしくお願いいたします

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

+2

例えば入力値が下記の場合はどうなるでしょうか。

4
1000000000 1000000000 1000000000 1000000000

追記:

質問に記載のコードについて変数の型を変えただけですが、手元のgcc環境では動作するようでした。

$ g++ -v
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4)
$ cat input
4
1000000000 1000000000 1000000000 1000000000
$ cat input | ./a.out
1000000000000000000
#include <iostream>
#include <stdlib.h>
using namespace std;

int compar(const long long *val1, const long long *val2);

int main(void)
{
    long long N, i, x = 0, y = 0;
    cin >> N;
    long long A[N];

    for (i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    qsort(A, N, sizeof(long long), (int (*)(const void *, const void *))compar);

    for (i = 0; i < N-1; i++)
    {
        if (A[i] == A[i+1])
        {
            x = A[i];
            i += 2;
            break;
        }
    }

    for (; i < N-1; i++)
    {
        if (A[i] == A[i+1])
        {
            y = A[i];
            break;
        }
    }

    cout << x * y << endl;

    return 0;
}

int compar(const long long *val1, const long long *val2)
{
    if (*val1 > *val2)
    {
        return -1;
    }
    else if (*val1 == *val2)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/10/18 01:11

    回答ありがとうございます
    試したところ、25と出力されました

    キャンセル

  • 2017/10/18 01:13

    すみません、コードを読み違えていたので条件を変更しました。

    キャンセル

  • 2017/10/18 01:38

    ありがとうございます
    謎の大きな負の数が出力されてしまいました
    long型で試してみてもダメだったのですが、どこがおかしいでしょうか?(それどころか、long型にしたら出力結果が全部0になってしまいました……)

    キャンセル

  • 2017/10/18 01:43

    xとyの積がintの範囲を超えるため、算術オーバーフローが発生しています。
    これをどのように回避するのか、というのがこの設問での課題です。

    キャンセル

  • 2017/10/18 08:00 編集

    きちんと正攻法で解かれるようであれば、困難は分割せよ、というところでしょうか。
    具体的な話まですると、多倍長整数で調べられるとよいでしょう。

    とにかく解ければ、ということであれば、使えるものは使え、ということになるかと思います。
    long intがダメだったというのは処理系にもよるので一概には理由は言えませんが、言語仕様上long long intというものもあります。

    キャンセル

  • 2017/10/18 12:11

    ありがとうございます
    long long int、mp::cpp_intの両方を試してみましたが、出力はいずれも0となってしまいました
    大きい数の分割にはどのような手法があるでしょうか?

    キャンセル

  • 2017/10/18 19:20

    > 大きい数の分割にはどのような手法があるでしょうか?
    一番イメージしやすい形は、筆算での計算方法です。
    筆算では、1桁同士の計算と繰り上がりを用いて、複数桁同士の和や積を求めることを可能としています。
    これを変数が扱える範囲で同様に行うことで、任意精度の計算が可能となります。

    キャンセル

  • 2017/10/19 14:31

    変数の型を変えても出力が0になる件ですが、恥ずかしながらクイックソートの引数を変えるのを忘れていました……
    無事正解になりました!
    筆算の考え方は盲点でした こちらも試してみようと思います
    長々とありがとうございました!

    キャンセル

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

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

関連した質問

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

  • C++

    2940questions

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