SRM579Div1

結果:137.17 pt

実装にかかる時間が多すぎた。

UndoHistory

この問題は理解できたけど、実装に時間がかかりすぎた。しかし、実装が複雑になりそうな問題はしっかり考えてから実装しないと泥沼にはまるので、急ぐのも禁物。こればかりは、ひたすらコーディングして身に付けるしかない。

TravellingPurchasingMan

巡回セールスマン問題(TSP)と最短路問題を組み合わせたような問題。組み合わせたといっても、計算量は線形結合なのでそこまで、アルゴリズムを工夫する必要はない。
解き方は理解したがN-1がinterestingじゃない時にどのように処理をすればいいか、考えていたら時間がなくなってしまった。常に閉店している店を追加することでこの例外を処理する方法は、なかなかスマートだなと感じた。
bitDPのテンプレート問題であるTSPの解き方は、今まで蟻本の解答を参考にしてた。
しかし、今回の解答のbitDPはそれよりも実装しやすいと感じた。

蟻本のコードは洗練されすぎていて理解できないことが多い。自力で書けないと本番で使用しにくいので、背伸びせずにまずは実装しやすい形から徐々に洗練していった方が力がつきやすそう。

蟻本(TSP)

#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <algorithm>
#include <sstream>
#include <set>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define MAX_N 17
#define INF (1<<15)

int n;
int dp[1<<MAX_N][MAX_N];

void
solve(vector<vector<int> > &d)
{
	for (int S=0; S < 1<<n; ++S) {
		fill(dp[S], dp[S] + n, INF);
	}
	dp[(1<<n)-1][0] = 0;
	for (int S = (1<<n)-2; S >= 0; --S) {
		for (int v=0; v<n; ++v) {
			for (int u=0; u<n; ++u) {
				if (!(S>>u&1)) {
					dp[S][v] = min(dp[S][v], dp[S|(1<<u)][u] + d[v][u]);
				}
			}
		}
	}
	printf("%d\n",dp[0][0]);
}

int
main()
{
	n = 5;
	vector<vector<int> > d =
	{
		{0,3,INF,4,INF},
		{INF,0,5,INF,INF},
		{4,INF,0,5,INF},
		{INF,INF,INF,0,3},
		{7,6,INF,INF,0}
	};
	solve(d);
}

今回(TSP)

#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <algorithm>
#include <sstream>
#include <set>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <time.h>

using namespace std;

#define MAX_N 15
#define INF (1<<28)

int V;
int cost[MAX_N][MAX_N];

int
solve()
{
    vector<vector<int> > dp(1<<V,vector<int>(V,INF));
    int mask_limit = 1<<V;

    dp[0][0] = 0;

    for (int mask = 0; mask < mask_limit ; ++mask) {
        for (int u = 0; u<V; ++u) {
            if (dp[mask][u] < INF) {
                int t = dp[mask][u];
                for (int v = 0; v<V; ++v) {
                    int nt = t + cost[u][v];
                    if (dp[mask|(1<<v)][v] > nt) {
                        dp[mask|(1<<v)][v] = nt;
                    }
                }
            }
        }
    }

    return dp[(1<<V)-1][0];
}

int
main()
{
    vector<vector<int> > c =
    {
        {0  ,3  ,INF,4  ,INF},
        {INF,0  ,5  ,INF,INF},
        {4  ,INF,0  ,5  ,INF},
        {INF,INF,INF,0  ,3},
        {7  ,6  ,INF,INF,0}
    };
    V = static_cast<int>(c.size());
    for (int i=0; i<V; ++i) {
        for (int j=0; j<V; ++j) {
            cost[i][j] = c[i][j];
        }
    }
    cout << solve() << endl;
}