結果

問題 No.209 Longest Mountain Subsequence
コンテスト
ユーザー ゴリポン先生
提出日時 2026-03-03 21:12:10
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 1,767 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,512 ms
コンパイル使用メモリ 172,568 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2026-03-03 21:12:14
合計ジャッジ時間 3,484 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/05/15/1100 より
// 動的計画法
import std;

// 多次元配列をある値で埋める
void fill(A, T)(ref A a, T value) if (isArray!A)
{
	alias E = ElementType!A;
	static if (isArray!E) {
		foreach (ref e; a)
			fill(e, value);
	} else {
		a[] = value;
	}
}
// https://forum.dlang.org/post/k1js2b$1bef$1@digitalmars.com より
// 変数の参照
struct Ref(T) {
	private T* _payload;
	this(ref T i) { _payload = &i; }
	@property ref T deref() { return *_payload; }
	alias deref this;
}
auto ref_(T)(ref T arg) { return Ref!T(arg); }
// B[1 .. j]が狭義単調増加、B[j .. K]が狭義単調減少
// 1 <= j <= N にわたって左右の裾野の長さを調べる
int N;
int[] A;
int[][] L, R;
int left(int l, int r)
{
	auto ret = ref_(L[l][r]);
	if (ret < 0) {
		ret = 0;
		foreach (x; 0 .. l)
			if (A[x] < A[l] && A[l] - A[x] < A[r] - A[l])
				ret = max(ret, left(x, l) + 1);
	}
	return ret;
}
int right(int l, int r)
{
	auto ret = ref_(R[l][r]);
	if (ret < 0) {
		ret = 0;
		foreach (x; r + 1 .. N)
			if (A[x] < A[r] && A[r] - A[x] < A[l] - A[r])
				ret = max(ret, right(r, x) + 1);
	}
	return ret;
}

void main()
{
	foreach (_; 0 .. readln.chomp.to!int) {
		// 入力
		N = readln.chomp.to!int;
		A = readln.split.to!(int[]);
		// 答えの計算
		L = uninitializedArray!(int[][])(N, N);
		fill(L, -1);
		R = uninitializedArray!(int[][])(N, N);
		fill(R, -1);

		int ma = -1;
		foreach (i; 0 .. N) {
			int lm = 0, rm = 0;
			// 左側
			foreach (x; 0 .. i)
				if (A[x] < A[i])
					lm = max(lm, left(x, i) + 1);
			// 右側
			foreach (x; i + 1 .. N) {
				if (A[x] < A[i])
					rm = max(rm, right(i, x) + 1);
			}
			ma = max(ma, lm + rm + 1);
		}
		// 答えの出力
		writeln(ma);
	}
}
0