結果

問題 No.319 happy b1rthday 2 me
コンテスト
ユーザー ゴリポン先生
提出日時 2026-10-18 21:39:39
言語 D
(dmd 2.113.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
結果
WJ  
(最新)
AC  
(最初)
実行時間 -
コード長 1,913 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
最終ジャッジ日時 2026-10-18 21:39:46
ジャッジサーバーID
（参考情報） 		judge5_0 / judge2_0
このコードへのチャレンジ
（要ログイン）

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/12/13/0900 より
// claude ai より
// 数え上げ、桁DP
import std;

long strToLong(char[] s)
{
	if (s.empty)
		return 0;
	else
		return s.to!long;
}
// 文字列で表された数を1減らす
char[] dec(char[] A)
{
	char[] ret = A.dup;
	ret.reverse;
	foreach (ref r; ret) {
		if (r != '0') {
			r--;
			break;
		}
		r = '9';
	}
	if (ret.length > 1 && ret.back == '0') ret.length -= 1;
	ret.reverse;
	return ret;
}
long[] p10;
long[][][] memo;

long inc(int d, char[] s, int lead, int one)
{
	if (d >= s.length) return 0;
	if (memo[d][lead][one] >= 0) return memo[d][lead][one];
	long ret = 0;
	int ma = lead ? s[d] - '0' : 10;

	foreach (i; 0 .. ma) {
		if (i == 2 && one) ret += p10[s.length.to!int - 1 - d];
		ret += inc(d + 1, s, 0, i == 1);
	}
	if (lead) {
		if (s[d] == '2' && one) ret += strToLong(s[d + 1 .. $]) + 1;
		ret += inc(d + 1, s, 1, s[d] == '1');
	}
	return memo[d][lead][one] = ret;
}
long con(char[] a)
{
	if (a.length < 2) return a[0] >= '2';

	int low = a[$ - 1] - '0';
	a.popBack;
	if (low < 2) a = dec(a);

	long ret = 1;
	foreach (i; 0 .. a.length) {
		if (i || a[0] > '2') ret += p10[a.length.to!int - 1 - i];
		else if (a[i] == '2') ret += strToLong(a[1 .. $]) + 1;
	}
	return ret;
}
// 多次元配列をある値で埋める
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;
	}
}

void main()
{
	// 入力
	char[] A, B;
	readln.chomp.formattedRead("%s %s", A, B);
	// 答えの計算
	p10 = 1L.recurrence!((a,n) => a[n-1] * 10).take(18).array;
	int c = A[$ - 1] == '2' && A[0] == '2';
	memo = uninitializedArray!(long[][][])(B.length + 1, 2, 2);
	fill(memo, -1);
	long ans = con(B) + inc(0, B, 1, 0);
	fill(memo, -1);
	A = dec(A);
	ans -= con(A) + inc(0, A, 1, 0);
	// 答えの出力
	writeln(ans - c);
}
0