AtCoder Grand Contest 043 AGC043 A - Range Flip Find Route

AtCoder Grand Contest 043 A - Range Flip Find Route

コンテスト中に色々あったのでメモ。

問題へのリンク

問題概要
コンテスト中の方針（ダイクストラ）
- 解説
- 実装
別解　DP（こっちの方が簡単）
- 実装
類題

※最後に類題を載せていますが、ヒントにもなりかねないので見たくない方はそこまで読まないようご注意ください！

問題概要

全部白だけを通って端から端へいくために、あらかじめ長方形領域を指定して色を反転させておきたい。長方形領域を選ぶ回数の最小値を求めよ。

コンテスト中の方針（ダイクストラ）

Rangeのところを読まずに実装し始め（？！）、一点ずつ切り替えだと思い込み黒に移動するときに重み1を持った辺を張って、ただのダイクストラ。サンプルが合い提出するもWA。
問題文を読み直すと「右か下」が太字になってることに気づき上下左右の辺をやめる。結果変わらず。2WA。
よくよく読むと最後に区間と書いてある。頭を抱える。
色々考えてみると、どうやらパスが大事らしい。ダイクストラ法は経路復元ができるので復元して、その中で白から黒に何回移り変わったかを数え、その値を出力する。WA。
冷静に考え直すと、ダイクストラの最短パスは一意に定まらないのでそれがたまたま選ばれた可能性があり網羅性に欠ける。パスに依存しない実装にしたいので経路を考えている最中に何か計算したい気持ちになる。
ここで先ほどパスに注目したのが役に立つ。経路を考えてる最中に白から黒に移動したときだけコストがかかるようにすればやりたいことが実現できそうだという気持ちになる。辺の張り方を変えて無事AC。

解説

解説放送にもありましたが、一次元で考え、二次元に拡張するのが自然かもしれません。DPでやるのが最も見通しがよさそうです（まあダイクストラも実質DP (?)なので）。両方で実装できるようにしておくといいかもしれません。ダイクストラは辺に情報を持たせますが、DPは走査しながらなので直感的かもしれません。

公式解説放送のリンク
実装
提出のリンク

ポイントは、グリッドの最短経路問題をダイクストラに落とす実装です。i, jという二次元座標を一次元に変換して頂点のindexとして管理すると見通しが良いです。これなら普段使っている一般のグラフのライブラリが転用できてハッピーです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INFLL = (ll)1e18+1;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int H,W;
template<class T> class Dijkstra {
public:
    int N;
    T inf;
    vector<T> cost;
    vector<vector<pair<T, int>>> edge;
    Dijkstra(const int _N, T _inf) : N(_N), inf(_inf),cost(_N), edge(_N) {
    }
 
    void make_edge(int from, int to, T w) {
        edge[from].push_back({ w,to });
    }
 
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf;
 
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
 
        while (!pq.empty()) {
            T v = pq.top().first;
            int from = pq.top().second;
            pq.pop();
            for (auto u : edge[from]) {
                T w = v + u.first;
                int to = u.second;
                if (w < cost[to]) {
                    cost[to] = w;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
};


vector<string> A;
bool IsIn(int x,int y){
    return 0<=x&&x<H&&0<=y&&y<W;
}
int f(int i, int j){
    return i * W + j;
}

int main() {

    cin >> H >> W;
    A.resize(H);
    rep(i,H){
        cin >> A[i];
    }
    Dijkstra<ll> d(H*W, INFLL);
    rep(i,H)rep(j,W){
        rep(k,2){
            int e = f(i, j);
            int nx = i + dx[k];
            int ny = j + dy[k];
            int ne = f(nx, ny);
            int cost = 0;
            if(!IsIn(nx, ny))continue;
            if(A[i][j] == '.' && A[nx][ny] == '#')cost = 1;
            d.make_edge(e, ne, cost);
        }
    }
    d.solve(f(0, 0));

    ll ans = d.cost[f(H-1, W-1)];
    if(A[0][0] ==  '#')ans++;
    cout << ans <<  endl;
}

別解　DP（こっちの方が簡単）

実装

提出へのリンク

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
typedef long long ll;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INFLL = (ll)1e18+1;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int H, W;
bool IsIn(int x,int y){
    return 0<=x&&x<H&&0<=y&&y<W;
}
ll dp[110][110];
int main() {

    cin >> H >> W;
    vector<string> A(H);
    rep(i,H)cin >> A[i];
    rep(i,H)rep(j,W)dp[i][j] = INFLL;
    dp[0][0] = (A[0][0] == '#' ? 1:0);
    rep(i,H)rep(j,W){
        rep(k,2){
            int ni = i + dx[k];
            int nj = j + dy[k];
            if(!IsIn(ni, nj))continue;
            int cost = 0;
            if(A[i][j] == '.' && A[ni][nj] == '#')cost++;
            chmin(dp[ni][nj], dp[i][j] + cost);
        }
    }
    cout << dp[H-1][W-1] << endl;
}