POJ 3048 Max Factor

ソースコード

int main()
{
    int pf[22222];
    CL(pf, -1);

    for (int i = 2; i <= 20000; ++i)
	if (pf[i] == -1)
	    for (int j = i; j <= 20000; j += i)
		pf[j] = i;

    int res = 1;
    int n;
    scanf("%d", &n);
    while (n--)
    {
	int a;
	scanf("%d", &a);
	if (pf[a] > pf[res])
	    res = a;
    }
    printf("%d\n", res);
}

POJ 3173 Parkside's Triangle

ソースコード

int main()
{
    int n, s;
    scanf("%d%d", &n, &s);

    int a[33][33];
    rep(j, n) erep(i, j)
    {
	a[i][j] = s;
	if (++s == 10)
	    s = 1;
    }

    rep(i, n)
    {
	rep(j, i)
	    printf("  ");
	for (int j = i; j < n; ++j)
	    printf("%d%c", a[i][j], j + 1 == n ? '\n' : ' ');
    }
}

POJ 3051 Satellite Photographs

ソースコード

int w, h;
char c[1024][100];
int dfs(int x, int y)
{
    if (!in_rect(x, y, w, h) || c[y][x] != '*')
	return 0;

    c[y][x] = '.';
    int s = 1;
    rep(i, 4)
	s += dfs(x + dx[i], y + dy[i]);
    return s;
}
int main()
{
    cin >> w >> h;
    rep(i, h)
	cin >> c[i];

    int res = 0;
    rep(y, h) rep(x, w)
	chmax(res, dfs(x, y));
    cout << res << endl;
}

POJ 3191 The Moronic Cowmpouter

大きい桁からその桁が必要かを上限下限から判断する方法でやろうとした
が、n進数(n > 1)とほとんど同じやり方でできるみたいなのでそうした
参考: wikipedia:en:Negative_base

ソースコード

vector<int> to_negabase(ll n, int base)
{
    vector<int> res;
    if (n == 0)
    {
	res.push_back(0);
	return res;
    }

    while (n != 0)
    {
	int rem = n % base;
	n /= base;
	if (rem < 0)
	{
	    rem += -base;
	    ++n;
	}
	res.push_back(rem);
    }
    return res;
}
string to_negabase_s(ll n, int base)
{
    vector<int> digits = to_negabase(n, base);
    string res;
    for (int i = digits.size() - 1; i >= 0; --i)
	res += to_s(digits[i]);
    return res;
}
int main()
{
    int n;
    cin >> n;
    cout << to_negabase_s(n, -2) << endl;
}

POJ 3184 Finicky Grazers

解法

Dはスペースの個数 / 牛の間隔の個数で求められる
Dの計算時の余りはD + 1にできる回数。問題に明記されてない気がするが、この回数分D + 1を使う必要がある

最小コストの計算はdpをする
dp[i][j] = 牛iを位置(i + D * i + j)に置いたときの最小コスト

そのままn * nの二重ループするとTLEするので、解になり得ない範囲は無視する

ソースコード

int main()
{
    int n, l;
    int x[ten(4)];
    scanf("%d%d", &n, &l);
    rep(i, n)
	scanf("%d", x + i);

    const int d = (l + 1 - n) / (n - 1);
    const int rem = (l + 1 - n) % (n - 1);

    const int inf = ten(8);
    int cur[ten(4) + 100], next[ten(4) + 100];
    fill_n(cur, rem + 1, inf);
    fill_n(next, rem + 1, inf);
    cur[0] = x[0];
    for (int i = 1; i < n; ++i)
    {
	const int lower = max(0, rem - (n - i));
	const int upper = min(i, rem);

	for (int j = lower; j <= upper + 1; ++j)
	    next[j] = inf;

	const int offset = (d + 1) * i;
	for (int j = lower; j <= upper; ++j)
	{
	    const int to = offset + j;
	    chmin(next[j], cur[j] + abs(x[i] - to));
	    chmin(next[j + 1], cur[j] + abs(x[i] - (to + 1)));
	}

	swap(cur, next);
    }
    printf("%d\n", cur[rem]);
}

POJ 3183 Stump Removal

解法

凸 or 平になっている箇所を爆破する

ソースコード

int main()
{
    const int M = 5 * ten(5) + 10;
    int n, h[M];
    scanf("%d", &n);
    rep(i, n)
	scanf("%d", h + i + 1);
    h[0] = h[n + 1] = 0;
    for (int i = 1; i <= n; ++i)
	if (h[i - 1] <= h[i] && h[i] >= h[i + 1])
	    printf("%d\n", i);
}

POJ 3185 The Water Bowls

解法

greedy
左端をflipするかの2通りを試す
位置iが1である場合、iをひっくり返すにはi, i + 1, i + 2をひっくり返す必要があるのでgreedyにやる

別解
反転パターンを全探索。bit + 無駄な探索しない高速化をしないとTLEする

ソースコード

greedy

int main()
{
    int b[25] = {};
    rep(i, 20)
	cin >> b[i + 1];

    int res = 3333;
    rep(_, 2)
    {
	int a[25];
	COPY(a, b);
	if (_)
	    a[0] = 1;

	int f = 0;
	rep(i, 20)
	{
	    if (a[i])
	    {
		++f;
		rep(j, 3)
		    a[i + j] ^= 1;
	    }
	}
	if (count(a, a + 21, 1) == 0)
	    chmin(res, f);
    }
    cout << res << endl;
}

全探索

int main()
{
    int b = 0;
    rep(i, 20)
    {
	int f;
	scanf("%d", &f);
	b |= f << i;
    }
    b <<= 1;

    const int rev = (1 << 3) - 1;
    const int filter = ((1 << 20) - 1) << 1;
    int res = 3333;
    rep(s, 1 << 20)
    {
	int flips = __builtin_popcount(s);
	if (flips < res) // 刈る
	{
	    int a = b;
	    rep(i, 20)
		if (s >> i & 1)
		    a ^= rev << i;

	    a &= filter;
	    if (a == 0)
		res = flips;
	}
    }
    printf("%d\n", res);
}