C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[7]: 過去問


(過去ログ 115 を表示中)

[トピック内 10 記事 (1 - 10 表示)]  << 0 >>

■67800 / inTopicNo.1)  過去問
  
□投稿者/ sun (5回)-(2013/09/03(Tue) 02:15:45)

分類:[.NET 全般] 

いま大会の過去問のソースを読み解いているのですがなぜさいごのfor文の条件のところに-2とついているのかが分かりません。なぜー2が必要なのか教えてください。


#include<stdio.h>
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int salary(int pipe2[],int joint2[],int n2);

int main(void)
{
	int n=0; //パイプの本数を格納する変数
	int pipe_length[100000]; //パイプの長さを格納する変数
	int joint_length[100000]; //ジョイントの長さを格納する変数

	for (int i=0;i<100000;i++)
	{
		pipe_length[i]=-1;
		joint_length[i]=-1;
	}

	while(scanf("%d",&n) && n>0)
	{
		for (int i=0;i<n;i++)
		{
			scanf("%d",&pipe_length[i]);

		}

		for (int i=0;i<n-1;i++)
		{
			scanf("%d",&joint_length[i]);
		}

		printf ("%d",salary(pipe_length,joint_length,n));

	}
}

int salary(int pipe2[],int joint2[],int n2)
{
	int number=0;
	int count_pipe=0;
	int count_joint=0;
	int length=0;
	int money=0;

	sort(pipe2,pipe2+n2);
	reverse(pipe2,pipe2+n2);

	sort(joint2,joint2+n2-1);
	reverse(joint2,joint2+n2-1);

	for (int i=0;i<n2;i++)
	{
		length+=pipe2[i];
		number++;
	}

	for (int i=0;i<n2-2;i++)
	{
		if (pipe2[i]<joint2[count_joint])
		{
			number--;
			length+=joint2[count_joint];
			count_joint++;
		}
	}

	money=number*length;

	return(money);

}

http://web-ext.u-aizu.ac.jp/pc-concours/2013/download/pastexam/2012pre.pdf
↑
問題文です

引用返信 編集キー/
■67801 / inTopicNo.2)  Re[1]: 過去問
□投稿者/ sun (6回)-(2013/09/03(Tue) 08:34:16)
補足です。考え方ですがもしパイプより長いジョイントが合った場合長さの総和にジョイントの長さ加え、本数から−1をします。このかんがえかたで正解でしょうか?

引用返信 編集キー/
■67804 / inTopicNo.3)  Re[1]: 過去問
□投稿者/ 魔界の仮面弁士 (323回)-(2013/09/03(Tue) 13:19:51)
No67800 (sun さん) に返信
> 分類:[.NET 全般]
うん?


> なぜー2が必要なのか
「ー2」→「-2」という突っ込みはさておき。


> 問題文です
どれですか?
「問題5 パイプつなぎ職人の給料」の事でしょうか?

そのコードがどこから出てきたものなのかも含め、状況説明が少なすぎるように思います。



とりあえず、問題5 のことだと仮定しておきます。


> さいごのfor文の条件のところに-2とついているのかが分かりません。

salary の最初のループが行っているのは、ジョイント 0 本の場合の 総延長 と本数みたいですね。

次のループは、ジョイントを繋げるかどうかの判定でしょう。
ジョイントに十分な長さが無いなら、繋がない方が給料が高くなりますので、
本数を減らしてでも総延長を伸ばした方が良いのかを判定条件にしているのだと思います。


でもコレ、本当に正しいコードになっていますか?

たとえば n=2、p={1 1}、j={3} を与えた場合、考えられるパターンとしては、
 ジョイント数 0 → p[0]およびp[1] → 2 本×長さ(1 + 1) → 賃金4
 ジョイント数 1 → p[0]+j[0]+p[1] → 1 本×長さ(1+3+1) → 賃金5
の 2 パターンであり、結果は 5 となるはずですが、結果は 4 と出力されました。

値を変えて、n=2、p={1 3}、j={3} を与えた場合は、
 ジョイント数 0 → p[0]およびp[1] → 2 本×長さ(1 + 3) → 賃金8
 ジョイント数 1 → p[0]+j[0]+p[1] → 1 本×長さ(1+3+3) → 賃金7
のパターンにおいて、結果は 8 と予想されます。こちらは結果も 8 でした。

引用返信 編集キー/
■67807 / inTopicNo.4)  Re[2]: 過去問
□投稿者/ kiku (19回)-(2013/09/03(Tue) 13:59:17)
> でもコレ、本当に正しいコードになっていますか?

こちらでも動作させて見たのですが、
おかしいなと思っていました。
プログラムの前にアルゴリズムの検討から始めないと
ならないと思います。

1.n=2の場合
 ジョイント数=1
 ・パターン1 パイプ2本(A,B)
 ・パターン2 パイプ1本(A+B)

2.n=3の場合
 ジョイント数=2
 ・パターン1 パイプ3本(A,B,C)
 ・パターン2 パイプ2本(A+B,C)
 ・パターン3 パイプ2本(A,B+C)
 ・パターン4 パイプ1本(A+B+C)

3.n=Nの場合
 ジョイント数=(N-1)
 パターン数=2^(N-1)

単純に上記のパターンをすべて計算して、
最大のものを探す必要があるのではないかと思います。
最大のものが複数パターンある可能性もありますが
このときの仕様はどうするのかも考えないとですね。

後は何か条件を付加して計算量を減らす方法を検討するかですね。

引用返信 編集キー/
■67843 / inTopicNo.5)  Re[3]: 過去問
□投稿者/ sun (7回)-(2013/09/04(Wed) 23:33:46)
なるほど。とりあえず全探索をするしかないと思い解いてみたのですがなぜか答えが間違っているとかえってくるのですがなにがまちがっているのでしょうか?
サンプルの値は正しく出力されるので何が間違っているのかわかりません。

#include<stdio.h>
#include<algorithm>

using namespace std;

int salary(int pipe2[],int joint2[],int n2);

int main(void)
{
	int n=0; //パイプの本数を格納する変数
	int pipe_length[65000]; //パイプの長さを格納する変数
	int joint_length[65000]; //ジョイントの長さを格納する変数

	while(scanf("%d",&n) && n>0)
	{
		for (int i=0;i<n;i++)
		{
			scanf("%d",&pipe_length[i]);
		}

		for (int i=0;i<n-1;i++)
		{
			scanf("%d",&joint_length[i]);
		}

		printf ("%d\n",salary(pipe_length,joint_length,n));

	}
}

int salary(int pipe2[],int joint2[],int n2)
{
	int number=0;
	int count_pipe=0;
	int count_joint=0;
	int length=0;
	int ver1=0;
	int ver2=0;
	int money=0;
	int syou[65000];

	sort(joint2,joint2+n2-1);
	reverse(joint2,joint2+n2-1);

	//ジョイントをつなげない場合の長さの合計を求める
	for (int i=0;i<n2;i++)
	{
		length+=pipe2[i];
		number++;
	}

	ver1=number*length;

	//全探索
	for (int i=0;i<n2;i++)
	{
		length+=joint2[i];
		number--;
		syou[i]=length*number;
	}

	//全探索の最適解を取り出す
	for (int i=0;i<n2;i++)
	{
		ver2=syou[0];

		if (ver2<syou[i])
		{
			ver2=syou[i];
		}
	}

	money=max(ver1,ver2);//最大値を求める

	if (ver1==ver2)
	{
		money=ver1;
	}

	return(money);

}

引用返信 編集キー/
■67845 / inTopicNo.6)  Re[4]: 過去問
□投稿者/ shu (380回)-(2013/09/05(Thu) 09:33:13)
2013/09/05(Thu) 17:39:33 編集(投稿者)
No67843 (sun さん) に返信

ジョイント未使用時のパイプの長さの総和 : S
パイプの本数:n
一番長いジョイントの長さ:J1
次に長いジョイントの長さ:J2 => J2 < J1ということ

としたとき

ジョイント未使用時:P1 = S * n
一番長いジョイントのみ使用時:P2 = (S + J1) * (n - 1)
二番目に長いジョイントのみ使用時:P3 = (S + J2) * (n - 1)
次に長いジョイントまで使用時:P4 = (S + J1 + J2) * (n - 2)


P2 - P3 = (S + J1) * (n - 1) - (S + J2) * (n - 1)
        = (J1 - J2) * (n - 1)
        > 0    (J1 > J2なので)
つまりジョイントを1本追加するときは一番長い物を考えればよい
のでP3は無視してよい。


P1 - P2 = S * n - (S + J1) * (n - 1)
        = S - J1 * (n-1)

P1 > P2のときを考えると
     S - J1 * (n-1)>0


P2 - P4 = (S + J1) * (n - 1) - (S + J1 + J2) * (n - 2)
        = (S + J1) * (n - 1) - (S + J1) * (n - 2) - J2 * (n -2)
        = S + J1 - J2 * (n - 2)
    > S + J1 - J1 * (n - 2)         (J1>J2なので
        = S - J1 * (n - 1)                    J1 * (n-2) >  J2 * (n -2)
        > 0                                 - J1 * (n-2) < -J2 * (n-2))

つまり P1>P2 なら P2>P4となるのでP1が答えとなり継続する必要がない
※このロジックはm個のジョイントとm+1個のジョイントで考えるとさらに確実

P1<P2ならP1をP2で置き換え同様に計算していく。

こんな感じでいけると思いますがどうでしょう。


ただ実際こんな仕事があったら毎日、全然つながないのが一番いいですね。

引用返信 編集キー/
■67857 / inTopicNo.7)  Re[5]: 過去問
□投稿者/ sun (9回)-(2013/09/06(Fri) 00:02:41)
その方法をとってやってみましたがそれでもAOJで3/6しか通りません。何度も入力して自分でも解を確かめてみたんですが全てあっているように思われます。何かほかに問題があるのでしょうか?それともコードのどこかにミスがあるのでしょうか?
引用返信 編集キー/
■67858 / inTopicNo.8)  Re[6]: 過去問
□投稿者/ shu (383回)-(2013/09/06(Fri) 07:40:59)
No67857 (sun さん) に返信
> その方法をとってやってみましたがそれでもAOJで3/6しか通りません。何度も入力して自分でも解を確かめてみたんですが全てあっているように思われます。何かほかに問題があるのでしょうか?それともコードのどこかにミスがあるのでしょうか?

AOJで3/6というのがどういう基準なのか分かりませんがプログラムが間違っているということなのでしょうか?

引用返信 編集キー/
■67874 / inTopicNo.9)  Re[6]: 過去問
□投稿者/ Jitta (70回)-(2013/09/06(Fri) 22:06:08)
Jitta さんの Web サイト
No67857 (sun さん) に返信
> その方法をとってやってみましたがそれでもAOJで3/6しか通りません。何度も入力して自分でも解を確かめてみたんですが全てあっているように思われます。何かほかに問題があるのでしょうか?それともコードのどこかにミスがあるのでしょうか?

 なぜソートするのでしょうか。問題文には、
「i番目のジョイントは、i番目とi+1番目のパイプだけをつなげることができる。」
とあるので、ソートする必要はないでしょう。
また、パイプやジョイントの配置を入れ替える必要もないでしょう。


> 過去問のソースを読み解いている

 質問の中でこの言葉がどのような意味を持っているのか、よくわかりません。
ここからは、過去問に対して解答があり、その解答のコードを読み解いていると理解できます。
が、ここに提示されているコードは、上に指摘した誤りからも、解答ではないようです。


P…パイプ
□, ■…ジョイント(□…つながない、■…つなぐ)
Pの数=n

とすると、全パターンはこのようになります。

 1:P1□1P2□2P3□3P4□4P5
 2:P1■1P2□2P3□3P4□4P5
 3:P1□1P2■2P3□3P4□4P5
 4:P1■1P2■2P3□3P4□4P5
 5:P1□1P2□2P3■3P4□4P5
 6:P1■1P2□2P3■3P4□4P5
 7:P1□1P2■2P3■3P4□4P5
 8:P1■1P2■2P3■3P4□4P5
 9:P1□1P2□2P3□3P4■4P5
10:P1■1P2□2P3□3P4■4P5
11:P1□1P2■2P3□3P4■4P5
12:P1■1P2■2P3□3P4■4P5
13:P1□1P2□2P3■3P4■4P5
14:P1■1P2□2P3■3P4■4P5
15:P1□1P2■2P3■3P4■4P5
16:P1■1P2■2P3■3P4■4P5

ここから、ジョイントをつなぐ位置について、n−1ビットの2進数と考えることができます。
つまり、2^(n-1) 通りのつなぎ型があるので、これら全部を調べます。
インデックスを 0〜2^(n-1)-1 変化させ、得られた数を2進数にして、
ビットが立っている位置のジョイントをつないだ結果を得ます。
パイプの数は、「つながなかったジョイントの数+1」で求められます。
ところが、パイプの数の最大は65000ということなので、
工夫しないと桁あふれを起こします。
というより、全検索による回答をはじくための仕様だと思います。

 パイプの長さを 5, 4, 2、ジョイントの長さを 2, 3 として、全パターンを計算すると

(5+4+2)*3=33
(11+2)*2=26
(5+9)*2=28
16*1=16

つなぐと、掛ける数が減るので、ジョイントの長さが十分に長くないと、
つなぐことで給与が減ってしまいます。
ということは、長いジョイントから調べて、全くつながないときよりも、
多くなったか、少なくなったかを見るようにするという、shuさんの方法がいいでしょう。
で、単に「長いものをつなげばよい」のではなく、
「i番目のジョイントは、i番目とi+1番目のパイプだけをつなげることができる。」
なので、長いジョイントが何番目かを覚えておかなければなりません。

ジョイントの長さを、長さだけでなく、「何番目のジョイントか」も記録できる様にすればいいでしょう。

引用返信 編集キー/
■67876 / inTopicNo.10)  Re[7]: 過去問
□投稿者/ sun (10回)-(2013/09/06(Fri) 22:54:40)
何とか問題を解くことができました。指摘されたことを含め整数型が間違っているなどいろいろ問題があったようですね。とても参考になりましたみなさん解答ありがとうございました。
解決済み
引用返信 編集キー/


トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

管理者用

- Child Tree -