naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉AtCoder Typical Contest 002

典型コンその2
(2016/4/10開催のもの)

A - 幅優先探索

やるだけ、というか
キューに (distance, (y, x)) を追加していって、先頭から取って四方に広げていくだけ。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
#define rep(var,n)  for(int var=0;var<(n);++var)

int main() {
    int R,C; cin >> R >> C;
    int sy,sx; cin >> sy >> sx; --sy; --sx;
    int gy,gx; cin >> gy >> gx; --gy; --gx;
    vector<string> mp(R);
    rep(r,R) cin >> mp[r];
    //
    int distance = -1;
    queue<pair<int,ii>> q;
    q.push(make_pair(0,ii(sy,sx)));
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int d = p.first;
        int y = p.second.first, x = p.second.second;
        if (y == gy && x == gx) {
            distance = d; break;
        }
        if (mp[y][x] == '.') {
            if (0 <= y-1 && mp[y-1][x] == '.') {
                q.push(make_pair(d+1, ii(y-1, x)));
            }
            if (y+1 < R && mp[y+1][x] == '.') {
                q.push(make_pair(d+1, ii(y+1, x)));
            }
            if (0 <= x-1 && mp[y][x-1] == '.') {
                q.push(make_pair(d+1, ii(y, x-1)));
            }
            if (x+1 < C && mp[y][x+1] == '.') {
                q.push(make_pair(d+1, ii(y, x+1)));
            }
        } else {
            ;
        }
        mp[y][x] = 'v';
    }
    cout << distance << endl;

    return 0;
}

→AC
https://beta.atcoder.jp/contests/atc002/submissions/2589145

四方 (y-1,x), (y+1, x), (y, x-1), (y, x+1) について(行き先をチェックしながら)キューに乗せて行くんだけど、1つ1つ手書きしてるのってバグりやすいからrep(i,4)で書ける4要素ベクトル(8方向なら8要素)を用意しておいてそれを足すべきかも。

こういうの書くときっていつも、行き先が行ける場所なのかどうか、visitedかどうかをキューに追加する前にチェックしてるんだけど、それをキューから拾うときにやったとしても、こういう感じのマップだとキューへの追加量は高々2倍程度にしかならない、ということを(計測の結果)知ってしまった。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

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

int main() {
    int R,C; cin >> R >> C;
    int sy,sx; cin >> sy >> sx; --sy; --sx;
    int gy,gx; cin >> gy >> gx; --gy; --gx;
    vector<string> mp(R);
    rep(r,R) cin >> mp[r];
    //
    int distance = -1;
    queue<pair<int,ii>> q;
    q.push(make_pair(0,ii(sy,sx)));

    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int d = p.first;
        int y = p.second.first, x = p.second.second;
#ifdef CHECK_AFTER
        if (!IN(y,0,R-1) || !IN(x,0,C-1) || mp[y][x] != '.') continue;
#endif
        if (y == gy && x == gx) {
            distance = d; break;
        }
        if (mp[y][x] == '.') {
            rep(i, 4) {
                int yi = y + dy[i], xi = x + dx[i];
#ifdef CHECK_AFTER
                q.push(make_pair(d+1, ii(yi,xi)));
#else
                if (IN(yi,0,R-1) && IN(xi,0,C-1) && mp[yi][xi] == '.') {
                    q.push(make_pair(d+1, ii(yi,xi)));
                }
#endif
            }
        } else {
            ;
        }
        mp[y][x] = 'v';
    }
    cout << distance << endl;

    return 0;
}

B - n^p mod m

やるだけ、というか貼るだけ
(Mが可変なので、Mがconstになってるsnippetコードは修正する必要がある)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//const ll M=1000000007LL;
ll M;

ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { assert(y%M!=0); return MUL(x, POW(y, M-2)); }
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

ll solve(ll n, ll m, ll p) {
    M = m;
    return POW(n, p);
}

int main() {
    ll n,m,p; cin >> n >> m >> p; // 1e9 1e9 1e14
    cout << solve(n,m,p) << endl;
    return 0;
}

→AC
https://beta.atcoder.jp/contests/atc002/submissions/2589200

C - 最適二分探索木

ソートして端から取ってく or 一段落とす、とやって行って、みたいな事*1してたらサンプルケースで53を下回って、問題を捉え違えていることに気づく。この問題はソートしちゃいけない(与えられた配列そのままの順番で二分木を構築しないといけない)

配列をどこで切るかを総当たりして、左右に分割して同じ問題を解く(その際に1つ深くなるからその区間に含まれる数の合計を足す必要がある。最初は深さを含めた関数を書いていたのだけれど、深さが+1になることで関数の値はΣ(その区間に含まれる数) だけ変わることを利用すれば深さは引数に入れる必要がない)、みたいなのを書いた。

区間は全部でn(n+1)/2個あって、それぞれの分割位置総当たり、ということはO(n^3)か。
n≦100 のデータセットならこれで行ける。(部分点50点)
n≦3000 まで行けると+50点だけど、O(n^3)では無理。O(n^2)ないしO(n^2logn)を示唆。
n≦100000 まで行けると+1点、というのは多分O(nlogn)で解けることを示唆している。(続く)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define ALL(c)  (c).begin(),(c).end()
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

int N;
vector<int> w;
vector<ll> acc;

#define INFTY 1e18

map<ll,ll> memo;

ll sub(int from, int to) {
    int width = to - from;
    if (width == 1) {
        return 0;
    }

    ll k = ((ll)from << 17LL) | to;
    if (memo[k]) {
        return memo[k];
    }

    ll best = INFTY;
    for (int i=from+1; i<to; ++i) {
        ll score = sub(from, i) + sub(i, to) + (acc[to] - acc[from]);
        best = min(best, score);
    }

    memo[k] = best;
    return best;
}

ll solve() {
    acc.assign(N+1, 0);
    rep(i,N) acc[i+1] = acc[i] + w[i];
    return sub(0, N);
}

int main() {
    N = loadint();
    w.resize(N);
    loadvec(w, N);
    cout << solve() << endl;
    return 0;
}

→部分AC (50点)
https://beta.atcoder.jp/contests/atc002/submissions/2589644

〜〜

(続き)
問題文の解説スライドを見ながら進める。
www.slideshare.net

O(n^2) 解法

  • 長さ1の区間から順にDP
  • 長さ2の区間=1つずつに分割。分割位置は記録。
  • 長さkの区間まで計算済みのとき。長さk+1の区間の分割位置を全て調べていたら前述のO(n^3)解法と同じ。調べるべき分割位置を減らせないか?
    • 長さkの区間(L:左を1つ縮めたもの、R:右を1つ縮めたもの)は計算済みで、かつL,Rそれぞれの場合の分割位置も分かっている。長さk+1の区間の分割位置はL,Rの分割位置の間のどこかにあるに違いないのでそこだけ調べればよい。*2
int N;
vector<int> w;
vector<ll> acc;

#define INFTY 1e18

ll solve() {
    acc.assign(N+1, 0);
    rep(i,N) acc[i+1] = acc[i] + w[i];

    if (N > 3000) return INFTY;

    vector<vector<ll>> dp(N+1, vector<ll>(N+1, INFTY));
    vector<vector<int>> cut(N+1, vector<int>(N+1, -1));

    rep(from, N) {
        dp[from][from+1] = 0; // w[i];
        cut[from][from+1] = -1;
    }
    rep(from, N-1) {
        dp[from][from+2] = w[from] + w[from+1];
        cut[from][from+2] = from+1;
    }
    for (int len=3; len<=N; ++len) {
        for (int from=0; from<=N-len; ++from) {
            int cut0 = cut[from][from+len-1],
                cut1 = cut[from+1][from+len];
            ll best = INFTY;
            int the_cut = -1;
            for (int c=cut0; c<=cut1; ++c) {
                ll score = dp[from][c] + dp[c][from+len];
                if (score < best) {
                    best = score;
                    the_cut = c;
                }
            }
            dp[from][from+len] = (acc[from+len] - acc[from]) + best;
            cut[from][from+len] = the_cut;
        }
    }

    return dp[0][N];
}

int main() {
    N = loadint();
    w.resize(N);
    loadvec(w, N);
    cout << solve() << endl;
    return 0;
}

→部分AC (100点)
https://beta.atcoder.jp/contests/atc002/submissions/2589883

O(nlogn) 解法

(続く)

*1:これは、小さい順に組んでいくハフマン符号化の手順と同じものが出来るのだろうか?

*2:Monge性、というらしい。スライド13ページ参照、なんだけどこれ意味分からん