[C++] AIZU ONLINE JUDGE <0584>

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
mahiknock
記事: 8
登録日時: 1年前
連絡を取る:

[C++] AIZU ONLINE JUDGE <0584>

#1

投稿記事 by mahiknock » 1年前

AIZU ONLINE JUDGE <0584> の問題に関してです。

************************************************************
https://onlinejudge.u-aizu.ac.jp/#/chal ... Trial/0584

※以下引用
入力ファイルの1行目に正整数 n (n≧3)が書いてあり、
つづく n 行に異なる正整数 a1, ..., an が 1つずつ書いてある。
a1, ..., an から異なる2個を選んで作られる順列を
(数として見て)小さい順に並べたとき、3番目に来るものを出力せよ。
ただし、例えば、a1 = 1, a4 = 11 のような場合も、a1a4 と a4a1 は異なる順列とみなす。
また、1 ≦ ai ≦ 10000 (i = 1, ..., n) かつ 3 ≦ n ≦ 10000 である。
出力ファイルにおいては, 出力の最後にも改行コードを入れること。

// Sample Input 1
3
2
7
5
// Sample Output 1
52

// Sample Input 2
4
17
888
1
71
// Sample Output 2
171
************************************************************

コードを Ideone.com (C++14) で
入力例を用いチェックしたところ、出力された数字は
サイトに記載されていた出力例と同じだったのですが、
自動審判に使われるデータではおかしな値が出力されました。
(autojudge.txt 参照)
自身で調べて改良を加えているものの一向に改善する気配がありません。
環境は C++ gcc 5.1.1 20150422 (Red Hat 5.1.1-1) です。
些細なミスだと思いますが自身では気づけていないので、改良点を教えて下さい。
(C++ に慣れてきている段階なので可読性などの些細な点には目をつぶって頂けると幸いです)

コード:

#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct calc {
	int x, y;
	int digit(int x);
	int permutation(int y);
};

int calc::digit(int n) {
	int num = 0;
	while (n / 10 > 1) {
		n /= 10;
		num++;
	}
	return num;
}

int calc::permutation(int o) {
	int data_num[o];
	int temp = 0;
	vector<int> data_all(o * (o - 1));
	for (int i = 0; i < o; i++) {
		cin >> data_num[i];
	}
	for (int i = 0; i < o; i++) {
		for (int j = 0; j < o; j++) {
			if (i != j) {
				int digit_num = calc::digit(data_num[i]) + calc::digit(data_num[j]) + 1;
				data_all[temp] = data_num[i] * pow(10, digit_num) + data_num[j];
				temp++;
			}
		}
	}
	sort(data_all.begin(), data_all.end());
	int answer = data_all[2];
	return answer;
}

int main() {
	int a;
	cin >> a;
	calc obj_calc;
	cout << obj_calc.permutation(a) << endl;
	return 0;
}
autojudge.txt
(273 バイト) ダウンロード数: 12 回

かずま

Re: [C++] AIZU ONLINE JUDGE <0584>

#2

投稿記事 by かずま » 1年前

a と b を並べて一つの数 c を作ると
 c = a * pow(10, b の桁数) + b
ではないのですか?

 c = a * pow(10, a の桁数 + b の桁数 + 1) + b
としているのはなぜですか?

n の桁数の求め方も間違っていませんか?
その calc::digit では、17 は 0桁。888 は 2桁。
1 は 0桁。71 は 1桁になってしまいます。

class の x と y は何のためにあるのですか?
まあ、これは動作には無関係なので些細なこととも言えますが。

アバター
mahiknock
記事: 8
登録日時: 1年前
連絡を取る:

Re: [C++] AIZU ONLINE JUDGE <0584>

#3

投稿記事 by mahiknock » 1年前

返信ありがとうございます。
かずま さんが書きました:
1年前
a と b を並べて一つの数 c を作ると
 c = a * pow(10, b の桁数) + b
ではないのですか?

 c = a * pow(10, a の桁数 + b の桁数 + 1) + b
としているのはなぜですか?

n の桁数の求め方も間違っていませんか?
その calc::digit では、17 は 0桁。888 は 2桁。
1 は 0桁。71 は 1桁になってしまいます。
可読性に欠けていた場合は申し訳ありません。
calc::digit では n の桁数 - 1 の値が返り値となっています。
よって、17 と 888 から 17888(answer) を作る場合、
calc::digit(17) = 1, calc::digit(888) = 2
となりますので、answer = 17 * pow(10, 1 + 2 + 1) + 888
これで 17888 が返り値として出力されるという考えです。
少し回りくどくなっちゃってますね。(笑)
かずま さんが書きました:
1年前
class の x と y は何のためにあるのですか?
まあ、これは動作には無関係なので些細なこととも言えますが。
これはこちら側のミスですね。

今回のご指摘にあった部分を改変してみました。

コード:

// 改変前
/*33*/ int digit_num = calc::digit(data_num[i]) + calc::digit(data_num[j]) + 1;
/*34*/ data_all[temp] = data_num[i] * pow(10, digit_num) + data_num[j];
// 改変後
/*33*/ data_all[temp] = data_num[i] * pow(10, digit(data_num[j])) + data_num[j];
この場合は出力が上手くいきました。
それはそれでまた不思議なのですが、
calc::digit(int n) の処理が上手くいってなかったのでしょうか。
まだまだ自分の勉強不足に痛感させられますね。
かずまさん、ありがとうございました。

かずま

Re: [C++] AIZU ONLINE JUDGE <0584>

#4

投稿記事 by かずま » 1年前

mahiknock さんが書きました:
1年前
calc::digit(int n) の処理が上手くいってなかったのでしょうか。
digit(17) が 0 で、digit(71) が 1 だから、
明らかに上手くいっていません。

元のプログラムの 34行目のあとに
 cout << data_all[temp] << endl;
を追加して、入力 4 17 888 1 71 を与えると

コード:

17888
171
1771
888017
888001
8880071
27
1888
171
7117
710888
7101
171
となります。
88817 となるべきところが 888017 になっています。
117 となるべきところが 27 になっています。
sort すると、117 171 171 ... となるので、3番目の
171 は正しく表示されるので気づかないかもしれませんが。

アバター
mahiknock
記事: 8
登録日時: 1年前
連絡を取る:

Re: [C++] AIZU ONLINE JUDGE <0584>

#5

投稿記事 by mahiknock » 1年前

今、こちらでも確認させていただきました。
しょうもない部分でのミスでなんだか申し訳ありません。
ご丁寧にありがとうございます。

追記という形にはなりますが、
改変後のコードだと時間制限を超過してしまいましたので、
以下のようにさらに改変しました。
無理矢理な感じはしますが、一応載せておきますね。

コード:

#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

struct calc {
	unsigned digit(unsigned x);
	unsigned permutation(unsigned y);
};

unsigned calc::digit(unsigned n) {
	return log10(n) + 1;
}

unsigned calc::permutation(unsigned o) {
	unsigned data_num[o];
	unsigned data_dig[o];
	unsigned data_ser[3];
	data_ser[0] = UINT_MAX;
	data_ser[1] = UINT_MAX;
	data_ser[2] = UINT_MAX;
	unsigned data_all;
	for (int i = 0; i < o; i++) {
		cin >> data_num[i];
		data_dig[i] = digit(data_num[i]);
	}
	for (int i = 0; i < o; i++) {
		for (int j = 0; j < o; j++) {
			if (i != j) {
				data_all = data_num[i] * pow(10, data_dig[j]) + data_num[j];
				if (data_ser[2] > data_all) {
					if (data_ser[1] > data_all) {
						if (data_ser[0] > data_all) {
							data_ser[2] = data_ser[1];
							data_ser[1] = data_ser[0];
							data_ser[0] = data_all;
						}
						else {
							data_ser[2] = data_ser[1];
							data_ser[1] = data_all;
						}
					}
					else {
						data_ser[2] = data_all;
					}
				}
			}
		}
	}
	unsigned answer = data_ser[2];
	return answer;
}

int main() {
	unsigned a;
	cin >> a;
	calc obj_calc;
	cout << obj_calc.permutation(a) << endl;
	return 0;
}

かずま

Re: [C++] AIZU ONLINE JUDGE <0584>

#6

投稿記事 by かずま » 1年前

なぜ、class を使うのかわかりませんが、
<cmath> の log10 や pow を使わないやり方なら、こんなものでしょうか?

コード:

#include <iostream>  // cin, cout, endl
#include <climits>   // UINT_MAX

int main()
{
	unsigned n, c, a[10000], d[10000], b[3] = { UINT_MAX, UINT_MAX, UINT_MAX };
	std::cin >> n;
	for (unsigned i = 0; i < n; i++)
		for (std::cin >> c; a[i] = c, d[i] = 10; c /= 10; ) d[i] *= 10;
	for (unsigned i = 0; i < n; i++)
		for (unsigned j = 0; j < n; j++)
			if (i != j && (c = a[i] * d[j] + a[j]) < b[2])
				if (c >= b[1]) b[2] = c;
				else if (b[2] = b[1], c >= b[0]) b[1] = c;
				else b[1] = b[0], b[0] = c;
	std::cout << b[2] << std::endl;
}

かずま

Re: [C++] AIZU ONLINE JUDGE <0584>

#7

投稿記事 by かずま » 1年前

すみません。コンパイルエラーになります。
std::cin >> c; の「;」を「,」に修正してください。

アバター
mahiknock
記事: 8
登録日時: 1年前
連絡を取る:

Re: [C++] AIZU ONLINE JUDGE <0584>

#8

投稿記事 by mahiknock » 1年前

クラス構造を取っているのは、
プログラミング初心者の自分がクラスという概念に
慣れたかっただけなので、特に意味は無いです。(笑)
コードの修正の件は了解しました。

作っていただいたコードを精読(?)させて頂いて、
自身の技能の向上に努めたいと思います。
何から何まで至れり尽くせりですみません。
また何かありましたら質問させて頂きます。
本当にありがとうございました。

返信

“C言語何でも質問掲示板” へ戻る