結果

問題 No.150 "良問"(良問とは言っていない
コンテスト
ユーザー bal4u
提出日時 2019-05-20 20:59:13
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,219 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 31,232 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-17 06:42:25
合計ジャッジ時間 935 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:15:24: note: in expansion of macro 'gc'
   15 |         int n = 0, c = gc();
      |                        ^~
main.c: In function 'out':
main.c:9:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
    9 | #define pc(c) putchar_unlocked(c)
      |               ^~~~~~~~~~~~~~~~
main.c:32:17: note: in expansion of macro 'pc'
   32 |         if (!n) pc('0');
      |                 ^~

ソースコード

diff # 

// yukicoder: 150 "良問"(良問とは言っていない
// 2019.5.19 bal4u

#include <stdio.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

int ins(char *s) { // 文字列の入力　スペース以下の文字で入力終了
	char *p = s;
	do *s = gc();
	while (*s++ > ' ');
	*--s = 0;
	return s - p;
}

void out(int n) { // 非負整数の表示（出力）
	int i;
	char b[20];

	if (!n) pc('0');
	else {
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

//// セグメント木
#define INF 0x7fffffff
int seg[256]; int sz;

void init(int n) {
	sz = 1; while (sz < n) sz <<= 1;
	memset(seg, INF, sizeof(seg));
}

// k番目（0-index）の値を v に変更
void update(int k, int v) {
	int a, b;
	k += sz - 1;
	seg[k] = v;
	while (k > 0) {
		k = (k - 1) >> 1;
		a = seg[(k << 1) + 1];
		b = seg[(k << 1) + 2];
		seg[k] = (a <= b)? a: b;
	}
}

// 空間 [a, b) 内の最小値
int getMin(int a, int b, int k, int l, int r)
{
	int left, right;
	if (r <= a || b <= l) return INF;
	if (a <= l && r <= b) return seg[k];
	left = getMin(a, b, (k << 1) + 1, l, (l + r) >> 1);
	right = getMin(a, b, (k << 1) + 2, (l + r) >> 1, r);
	return left <= right ? left : right;
}

char S[105], g[105];

void good(int l, int r) {
	int i, j, k;
	static char *str = "good";
	for (i = l; i <= r; i++) {
		k = 4;
		for (j = 0; j < 4; j++) if (S[i+j] == str[j]) k--;
		g[i] = k;
	}
}

void problem(int l, int r) {
	int i, j, k; int ma = 0;
	static char *str = "problem";
	for (i = l; i <= r; i++) {
		k = 7;
		for (j = 0; j < 7; j++) if (S[i+j] == str[j]) k--;
		update(i, k);
		if (i > ma) ma = i;
	}
}
int main()
{
	int i, T, w, a, ans;
	
	T = in(); while (T--) {
		w = ins(S);
		init(w);            // セグメント木の初期化
		good(0, w-11);
		problem(4, w-7);
		ans = 20;
		for (i = 0; i <= w-11; i++) {
			a = g[i] + getMin(i+4, w-6, 0, 0, sz);
			if (a < ans) {
				ans = a;
				if (!ans) break;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}
0