情画プロコン #2 略解

(2015/8/10 改訂)

リソース制限

	C / C++	Java	Python2 / Python3
時間制限	1秒	1秒	5秒
メモリ制限	256MB	256MB	256MB

※参考コードは全てC++

Lv1. だいがくぐらし！

制約から、日をまたぐことは無いと分かるので、
家を出る時刻と講義開始時刻を0時0分からの「分」単位に変換した上で比較すれば良い。

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char const *argv[]) {
    int A;
    cin >> A;

    for (int i = 0; i < 7; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (a * 60 + b + A > c * 60 + d) {
            cout << "DEAD" << endl;
        } else {
            cout << "SAFE" << endl;
        }
    }

    return 0;
}

Lv2. ディジタル信号処理

定義をそのままプログラムに翻訳する。
$k$を$1$から$N-1$までカウントし、順番に調べていけば良い。
$f[i] = f[(i + k) \bmod N]$となる$k$がない場合、最終的な$k$の値が自動的に$N$になる。

また、元の信号をコピーして後ろに貼り付けることで、$\bmod$を取り払う事ができる。

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char const *argv[]) {

    int N, k;
    cin >> N;
    vector<int> v;
    for (int i = 0; i < N; ++i) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    for (k = 1; k < N; ++k) {
        bool flag = true;
        for (int i = 0; i < N; ++i) {
            if (v[i] != v[(i + k) % N]) {
                flag = false;
                break;
            }
        }
        if (flag) break;
    }
    cout << k << endl;

    return 0;
}

Lv3. 巡回レポートマン問題

地図のマスを頂点、各頂点について移動できる方向に重み1の辺を貼ったグラフを考える。
「重み」を「距離」と読み替えたときの、任意の2点間の最短距離が分かれば良い。
方法はいろいろ(幅優先探索、ダイクストラ、ベルマンフォード等)あるが、
ワーシャルフロイド法を使うと、「任意の2点間の最短距離」が1度に分かるので楽である。
($HW$が100以内なので、間に合う。)

#include <iostream>
#include <vector>

using namespace std;

int N, H, W;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int dist[100][100];
const int INF = 1 << 29;

inline int get(int y, int x) {
    return y * W + x;
}

int main(int argc, char const *argv[]) {
    cin >> N >> H >> W;
    vector<string> m;
    vector<int> R;
    vector<int> C;

    for (int i = 0; i < H; ++i) {
        string temp;
        cin >> temp;
        m.push_back(temp);  
    }

    for (int i = 0; i <= N; ++i) {
        int r, c;
        cin >> r >> c;
        r--, c--;
        R.push_back(r);
        C.push_back(c);
    }

    //初期化(隣接行列)
    for (int i = 0; i < H * W; ++i) {
        for (int j = 0; j < H * W; ++j) {
            if (i == j) continue;
            dist[i][j] = INF;
        }
    }

    //グラフ構築
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            for (int k = 0; k < 4; ++k) {
                int tx = j + dx[k];
                int ty = i + dy[k];
                if (tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
                if (m[ty][tx] == '.') {
                    dist[get(i, j)][get(ty, tx)] = 1;
                }
            }
        }
    }

    //ワーシャルフロイド法    
    for (int k = 0; k < H * W; ++k) {
        for (int i = 0; i < H * W; ++i) {
            for (int j = 0; j < H * W; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        int temp = dist[get(R[i], C[i])][get(R[i + 1], C[i + 1])];
        if (temp == INF) {
            ans = -1;
            break;
        }
        ans += temp;
    }

    cout << ans << endl;

    return 0;
}

Lv4. 物理実験

部分点解法

(部分点1解法) : $M$が0なので、各$i$について、$A_i$と$B_i$のうち小さい方を取れば良い。
(部分点2解法) : $M$が0または1である。
$M=0$のときは(部分点1解法)を使う。
$M=1$のときは、その条件で対象となっている2つの物質K以外については(部分点1解法)を使う。
その条件で対象となっている2つの物質Kについては、それぞれを空間A, 空間Bに入れた場合($4$通り)についてシミュレーションを行い、minをとる。
(部分点3解法) : $1≦N≦16$である。
全ての物質Kについて、空間A、空間Bに入れた場合($2^N$通り)をシミュレートすれば良い。
(部分点4解法) : $17≦N≦100$ かつ全ての$1≦j≦N$について、$D_j - C_j = 1$である。
$i + 1$番目の物質Kをおいた場合の全体エネルギーは、$i$番目の物質Kをおいた空間のみによって決まる。(マルコフ性)
よって、以下の様な状態をとって動的計画法(DP)を行えば良い。

dp[i][j] := 物質をi番目まで調べたとき、i番目の物質を空間j(j=0ならA, j=1ならB)においた場合の最小全体エネルギー
(部分点5解法) : 全ての$1≦j≦N$について、$1≦D_j - C_j≦16$を満たす。
(部分点4解法)について、保存する状態を「$i$番目」から「$i-15$番目〜$i$番目」に変更してbitDPを行えば良い。

満点解法

$i (i = 1, 2, … , N)$番目の物質Kを表す頂点を作る。
別に始点s、終点tの頂点を作り、始点から$i$番目の物質Kの頂点に対して重み$A_i$、
$i$番目の物質Kの頂点から終点の頂点に対して重み$B_i$、
互いに関係がある二つの物質Kの頂点間に双方向に重み$E_j$の辺を貼ったグラフを作る。

求める答えは、このグラフの最小s-tカットとなるので、「最大フロー・最小カット定理」より、s-t間最大フローを求めれば良い。
最大フローを求めるアルゴリズムにはいろいろあるが、今回は「Ford-Fulkerson」が速度・実装難易度的にちょうど良いだろう。

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;


const int MAX_V = 102;
const int INF = 1 << 29;

// Ford-Fulkerson; refference : プログラミングコンテストチャレンジブック
struct edge {int to, cap, rev; };
vector<edge> G[MAX_V];
bool used[MAX_V];

// fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(int from, int to, int cap) {
    const int s1 = G[to].size();
    const int s2 = G[from].size() - 1;
    G[from].push_back((edge){to, cap, s1});
    G[to].push_back((edge){from, 0, s2});
}

// 増加パスをDFSで探す
int dfs(int v, int t, int f) {
    if (v == t) return f;
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (!used[e.to] && e.cap > 0) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

//sからtへの最大流を求める
int max_flow(int s, int t) {
    int flow = 0;
    for(;;) {
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, INF);
        if (f == 0) return flow;
        flow += f;
    }
}

int main(int argc, char const *argv[]) {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        add_edge(0, i + 1, a);
        add_edge(i + 1, N + 1, b);
    }
    for (int j = 0; j < M; ++j) {
        int c, d, e;
        cin >> c >> d >> e;
        add_edge(c, d, e);
        add_edge(d, c, e);
    }
    cout << max_flow(0, N + 1) << endl;

    return 0;
}