POJ 3273 Monthly Expense

解法

月の出費の上限で二分探索

ソースコード

int n, m;
int money[ten(5) + 100];
bool ok(int month_spend)
{
    int months = 1, spend = 0;
    rep(i, n)
    {
	if (spend + money[i] > month_spend)
	{
	    ++months;
	    spend = 0;
	}
	spend += money[i];
    }
    return months <= m;
}
int main()
{
    scanf("%d%d", &n, &m);
    rep(i, n)
	scanf("%d", money + i);

    int low = *max_element(money, money + n) - 1;
    int high = ten(9) + 100;
    while (high - low > 1)
    {
	int mid = (high + low) / 2;
	if (ok(mid))
	    high = mid;
	else
	    low = mid;
    }
    printf("%d\n", high);
}

POJ 3272 Cow Traffic

問題の意味がなかなかわからなかった

問題概要

ノード数nのDAGが与えられる。入力次数が0のノードからnへのパスを全て列挙する。各辺ごとにいくつのパスに含まれているかを数えたとき、最大のパス数はいくつか。

解法

辺i -> jを含むパス数は、(入力次数0のノード -> iのパス数) * (j -> nのパス数)で求められる
前者は元のグラフを逆辺にしたグラフ上でdp, 後者は元のグラフ上でdpして求める

ソースコード

int dfs(int v, const vector<vector<int> >& g, int* dp)
{
    if (dp[v] != -1)
	return dp[v];

    int res = 0;
    rep(i, g[v].size())
	res += dfs(g[v][i], g, dp);
    return dp[v] = res;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<int> > g(n), rg(n);
    while (m--)
    {
	int a, b;
	scanf("%d%d", &a, &b);
	--a, --b;
	g[a].pb(b);
	rg[b].pb(a);
    }

    int dp[5252], rdp[5252];
    CL(dp, -1);
    CL(rdp, -1);

    dp[n - 1] = 1;
    rep(i, n - 1)
	if (rg[i].empty())
	    rdp[i] = 1;    // 0 indegree in original graph

    int res = -1;
    rep(i, n) rep(j, g[i].size())
    {
	int u = i, v = g[i][j];
	int paths = dfs(u, rg, rdp) * dfs(v, g, dp);
	chmax(res, paths);
    }
    printf("%d\n", res);
}

POJ 3280 Cheapest Palindrome

解法

区間dp
dp[i][j] = [i, j)をpalindromeにする最小コスト

ソースコード

int main()
{
    int m, n;
    string s;
    cin >> n >> m >> s;

    const int inf = ten(8);
    int cost[256];
    fill(cost, cost + 256, inf);
    while (n--)
    {
	char c;
	int add, del;
	cin >> c >> add >> del;
	cost[c] = min(add, del);
    }

    static int dp[2048][2048]; // [i, j)
    erep(i, m) erep(j, m)
	dp[i][j] = inf;

    rep(i, m)
    	dp[i][i] = dp[i][i + 1] = 0;

    rep(len, m)
    {
	for (int i = 0, j = len; j <= m; ++i, ++j)
	{
	    if (i > 0)
		chmin(dp[i - 1][j], dp[i][j] + cost[s[i - 1]]);
	    if (j < m)
		chmin(dp[i][j + 1], dp[i][j] + cost[s[j]]);
	    if (i > 0 && j < m && s[i - 1] == s[j])
		chmin(dp[i - 1][j + 1], dp[i][j]);		
	}
    }
    printf("%d\n", dp[0][m]);
}

POJ 3279 Fliptile

解法

一番上の行のflipの仕方を決めると、flipの仕方は一意に決まるので、一番上の行のflipパターンを全て試す。
蟻本に載ってる問題です

ソースコード

int h, w, tile[22][22];
int work[22][22],  pos[22][22];
int f;
void flip(int x, int y)
{
    work[y][x] ^= 1;
    pos[y][x] = 1;
    rep(i, 4)
    {
	int tx = x + dx[i], ty = y + dy[i];
	if (valid(tx, ty, w, h))
	    work[ty][tx] ^= 1;
    }
}
int main()
{
    scanf("%d%d", &h, &w);
    rep(i, h) rep(j, w)
	scanf("%d", &tile[i][j]);

    int min_flip = 33333, res_pos[22][22];
    rep(s, bin(w))
    {
	CL(pos, 0);
	COPY(work, tile);
	f = 0;

	rep(x, w)
	    if (s >> x & 1)
		flip(x, 0);

	for (int y = 1; y < h; ++y)
	    rep(x, w)
		if (work[y - 1][x])
		    flip(x, y);

	bool ok = true;
	rep(y, h) rep(x, w)
	    ok &= !work[y][x];


	if (ok && f < min_flip)
	{
	    min_flip = f;
	    COPY(res_pos, pos);
	}
    }
    if (min_flip == 33333)
	puts("IMPOSSIBLE");
    else
    {
	rep(y, h) rep(x, w)
	    printf("%d%c", res_pos[y][x], x + 1 == w ? '\n' : ' ');
    }
}

POJ 3277 City Horizon

解法

まずは、座標圧縮する
ビルの開始点、終了点に高さをメモする
座標の小さい点から走査していき、ビルの開始点ではそのビルの高さを集合に加え、終了点では集合から削除する
高さの集合の管理には追加、削除が高速にできるものを使うと良い
追加、削除がO(logn)のデータ構造を使うと、計算量はO(nlogn)

multisetを使うと実装が楽になるが、TLEしたのでpriority_queue + カウンタ(num)で書き直した

ソースコード

int main()
{
    const int M = 4 * ten(4);
    int n;
    int a[M], b[M], h[M]; // [a, b)
    scanf("%d", &n);
    rep(i, n)
	scanf("%d%d%d", a + i, b + i, h + i);

    vector<int> pos;
    rep(i, n)
	pos.pb(a[i]), pos.pb(b[i]);
    uniq(pos);

    vector<int> uh(h, h + n);
    uniq(uh);

    static vector<int> start[2 * M], end[2 * M];
    rep(i, n)
    {
	int s = lower_bound(all(pos), a[i]) - pos.begin();
	int e = lower_bound(all(pos), b[i]) - pos.begin();
	int hi = lower_bound(all(uh), h[i]) - uh.begin();
	start[s].pb(hi);
	end[e].pb(hi);
    }

    int num[M] = {};
    priority_queue<pint> h_set;	// (height, hi)
    ll area = 0;
    rep(pi, pos.size())
    {
	rep(i, start[pi].size())
	    if (num[start[pi][i]]++ == 0)
		h_set.push(pint(uh[start[pi][i]], start[pi][i]));
	rep(i, end[pi].size())
	    --num[end[pi][i]];

	while (!h_set.empty() && num[h_set.top().second] == 0)
	    h_set.pop();

	if (!h_set.empty())
	{
	    ll max_h = h_set.top().first;
	    ll len = pos[pi + 1] - pos[pi];
	    area += len * max_h;
	}
    }
    printf("%lld\n", area);
}

POJ 3278 Catch That Cow

解法

bfs

ソースコード

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

    const int inf = ten(7);
    int d[2 * ten(5) + 100];
    fill(d, d + 2 * ten(5), inf);
    queue<int> q;
    d[n] = 0;
    q.push(n);
    while (!q.empty())
    {
	int p = q.front();
	q.pop();
	int nd = d[p] + 1;
	int to[] = { p - 1, p + 1, 2 * p };
	rep(i, 3)
	{
	    if (to[i] >= 0 && to[i] < ten(5) + 10)
	    {
		if (nd < d[to[i]])
		{
		    d[to[i]] = nd;
		    q.push(to[i]);
		}
	    }
	}
    }
    printf("%d\n", d[k]);
}

POJ 3629 Card Stacking

ソースコード

int main()
{
    int n, k, p;
    scanf("%d%d%d", &n, &k, &p);
    int m = k / n;
    vector<int> res;
    queue<int> deck;
    rep(i, k)
	deck.push(i + 1);

    for (int i = 0; !deck.empty(); ++i %= n)
    {
	if (i == n - 1)
	    res.pb(deck.front());
	deck.pop();
	rep(j, p)
	{
	    deck.push(deck.front());
	    deck.pop();
	}
    }
    sort(all(res));
    rep(i, m)
	printf("%d\n", res[i]);
}