結果

問題 No.335 門松宝くじ
コンテスト
ユーザー asugen0402
提出日時 2019-03-27 16:10:41
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 312 ms / 2,000 ms
コード長 6,731 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 520 ms
コンパイル使用メモリ 33,152 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 02:22:53
合計ジャッジ時間 3,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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[2][D_SEGT_CNT * 2];							// セグメントツリー [0]:最大 or [1]:最小

// 内部変数 - テスト用
#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 piType					// <I> [0]:最大 or [1]:最小
)
{
	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 (piType == 0) {
				if (si2SegT[0][liCNo1] > si2SegT[0][liCNo2]) {
					si2SegT[0][i] = si2SegT[0][liCNo1];
				}
				else {
					si2SegT[0][i] = si2SegT[0][liCNo2];
				}
			}
			else {
				if (si2SegT[1][liCNo1] < si2SegT[1][liCNo2]) {
					si2SegT[1][i] = si2SegT[1][liCNo1];
				}
				else {
					si2SegT[1][i] = si2SegT[1][liCNo2];
				}
			}
		}

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

	return 0;
}

// セグメントツリー - 取得
int
fSegTGet(
	int piType					// <I> [0]:最大 or [1]:最小
	, 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[piType][piNNo];
	}

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

	int liRet = 0;

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

	// 右側
	if (piGetE >= liCenter + 1) {
		int liVal = fSegTGet(piType, piNNo * 2 + 1, liCenter + 1, piNowE, piGetS, piGetE);
		if (piType == 0) {
			if (liRet < liVal) {
				liRet = liVal;
			}
		}
		else {
			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]);
		si2SegT[0][D_SEGT_CNT + i] = si1No[i];
		si2SegT[1][D_SEGT_CNT + i] = si1No[i];
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	// セグメントツリー - 親データセット
	fSegTSetP(0);
	fSegTSetP(1);

	// ２つの数字の選択
	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(0, 1, 0, D_SEGT_CNT - 1, 0, i - 1);			// 左側の最大値

				if (si1No[i] > si1No[j]) {
					if (liVal > si1No[i]) {
						liVal = fSegTGet(1, 1, 0, D_SEGT_CNT - 1, 0, i - 1);				// 左側の最小値
						if (liVal > si1No[i]) {
							liVal = 0;
						}
						else {
							liVal = si1No[i];
						}
					}
				}
				else {
					if (liVal < si1No[i]) {
						liVal = 0;
					}
					else if (liVal < si1No[j]) {
						liVal = si1No[j];
					}
				}

				// 最大値 - 更新
				liMax = liVal;
			}

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

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

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

			// ２つの数字の右側
			if (j < siNCnt - 1) {
				int liVal = fSegTGet(0, 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[i]) {
						liVal = si1No[i];
					}
				}
				else {
					if (liVal > si1No[j]) {
						liVal = fSegTGet(1, 1, 0, D_SEGT_CNT - 1, j + 1, siNCnt - 1);		// 右側の最小値
						if (liVal > si1No[j]) {
							liVal = 0;
						}
						else {
							liVal = si1No[j];
						}
					}
				}

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

			// 期待値 - 加算
			liSum += 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