結果

問題 No.335 門松宝くじ
コンテスト
ユーザー asugen0402
提出日時 2019-03-27 15:26:39
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 5,873 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 32,768 KB
実行使用メモリ 8,416 KB
最終ジャッジ日時 2024-10-11 02:21:08
合計ジャッジ時間 3,428 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_VAL_MAX		805										// 最大値
#define D_SEGT_CNT		1024									// セグメントツリーデータ数(2の累乗)

// 内部変数
static FILE *szpFpI;											// 入力
static int si1No[D_VAL_MAX];									// 番号
static int siNCnt;												// 番号数
static int si2SegT[D_VAL_MAX][D_SEGT_CNT * 2];					// セグメントツリー[最大値]

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// セグメントツリー - 親データセット
int
fSegTSetP(
	int piMax					// <I> 最大値
)
{
	int i;

	// 最初の親番号範囲
	int liPNo1 = D_SEGT_CNT / 2;
	int liPNo2 = D_SEGT_CNT - 1;

	// 作成
	while (liPNo1 > 0) {
		for (i = liPNo1; i <= liPNo2; i++) {

			// 子番号
			int liCNo1 = i * 2;
			int liCNo2 = liCNo1 + 1;

			// セット
			if (si2SegT[piMax][liCNo1] > si2SegT[piMax][liCNo2]) {
				si2SegT[piMax][i] = si2SegT[piMax][liCNo1];
			}
			else {
				si2SegT[piMax][i] = si2SegT[piMax][liCNo2];
			}
		}

		// 次の親番号範囲
		liPNo2 = liPNo1 - 1;
		liPNo1 /= 2;
	}

	return 0;
}

// セグメントツリー - 取得
int
fSegTGet(
	int piMax					// <I> 最大値
	, int piNNo					// <I> 現在番号 1～
	, int piNowS				// <I> 現在範囲 - 開始 0～D_SEGT_CNT-1
	, int piNowE				// <I> 現在範囲 - 終了 0～D_SEGT_CNT-1
	, int piGetS				// <I> 取得範囲 - 開始 0～D_SEGT_CNT-1
	, int piGetE				// <I> 取得範囲 - 終了 0～D_SEGT_CNT-1
)
{
	// 内包チェック
	if (piGetS <= piNowS && piNowE <= piGetE) {
		return si2SegT[piMax][piNNo];
	}

	// 中間位置
	int liCenter = (piNowS + piNowE) / 2;

	int liRet = 0;

	// 左側
	if (piGetS <= liCenter) {
		liRet = fSegTGet(piMax, piNNo * 2, piNowS, liCenter, piGetS, piGetE);
	}

	// 右側
	if (piGetE >= liCenter + 1) {
		int liVal = fSegTGet(piMax, piNNo * 2 + 1, liCenter + 1, piNowE, piGetS, piGetE);
		if (liRet < liVal) {
			liRet = liVal;
		}
	}

	return liRet;
}

// 期待値 - 取得
int
fGetVal(
)
{
	int i, j;
	char lc1Buf[1024];

	// セグメントツリー - 初期化
	memset(si2SegT, 0, sizeof(si2SegT));

	// 番号 - 取得
	for (i = 0; i < siNCnt; i++) {
		fscanf(szpFpI, "%d", &si1No[i]);
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	// セグメントツリー - セット
	for (i = 1; i <= siNCnt; i++) {

		// 子データセット
		for (j = 0; j < siNCnt; j++) {
			if (si1No[j] <= i) {
				si2SegT[i][D_SEGT_CNT + j] = si1No[j];
			}
		}

		// 親データセット
		fSegTSetP(i);
	}

	// ２つの数字の選択
	int liSum = 0;
	for (i = 0; i < siNCnt - 1; i++) {
		for (j = i + 1; j < siNCnt; j++) {
			int liMax = 0;

			// ２つの数字の左側
			if (i > 0) {
				int liVal = fSegTGet(siNCnt, 1, 0, D_SEGT_CNT - 1, 0, i - 1);

				if (si1No[i] > si1No[j]) {
					if (liVal > si1No[i]) {
						liVal = fSegTGet(si1No[i] - 1, 1, 0, D_SEGT_CNT - 1, 0, i - 1);
					}
				}
				else {
					if (liVal < si1No[i]) {
						liVal = 0;
					}
				}

				// 最大値
				liMax = liVal;
			}

			// ２つの数字の間
			if (j - i > 1) {
				int liVal = fSegTGet(siNCnt, 1, 0, D_SEGT_CNT - 1, i + 1, j - 1);

				if (si1No[i] > si1No[j]) {
					if (si1No[i] > liVal && liVal > si1No[j]) {
						liVal = fSegTGet(si1No[j] - 1, 1, 0, D_SEGT_CNT - 1, i + 1, j - 1);
					}
				}
				else {
					if (si1No[i] < liVal && liVal < si1No[j]) {
						liVal = fSegTGet(si1No[i] - 1, 1, 0, D_SEGT_CNT - 1, i + 1, j - 1);
					}
				}

				// 最大値 - 更新
				if (liMax < liVal) {
					liMax = liVal;
				}
			}

			// ２つの数字の右側
			if (j < siNCnt - 1) {
				int liVal = fSegTGet(siNCnt, 1, 0, D_SEGT_CNT - 1, j + 1, siNCnt - 1);

				if (si1No[i] > si1No[j]) {
					if (liVal < si1No[j]) {
						liVal = 0;
					}
				}
				else {
					if (liVal > si1No[j]) {
						liVal = fSegTGet(si1No[j] - 1, 1, 0, D_SEGT_CNT - 1, j + 1, siNCnt - 1);
					}
				}

				// 最大値 - 更新
				if (liMax < liVal) {
					liMax = liVal;
				}
			}

			// 期待値 - 加算
			liSum += si1No[i] * si1No[j] * liMax;
		}
	}

	return liSum;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 数の個数・くじ数 - 取得
	int liTCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siNCnt, &liTCnt);

	// １つ目のくじ - 取得
	int liMax = fGetVal();
	int liNo = 0;

	// ２つ目以降のくじ - 取得
	for (i = 1; i < liTCnt; i++) {
		int liVal = fGetVal();
		if (liMax < liVal) {
			liMax = liVal;
			liNo = i;
		}
	}

	return liNo;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 結果 - セット
	sprintf(lc1Buf, "%d\n", liRet);

	// 結果 - 出力
	fOut(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}
0