hogecoder

tsutaj 競技プログラミングの記録

AtCoder Regular Contest 038 B: マス目と駒

ちょっと迷ってしまったので。

問題概要

原文を参照してください → B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder

解説

rec[i][j] := (i, j) で手番が回ってきた人は勝つか負けるか? となるような配列を作ります。

あるマス  (i, j) について、この値は以下のように決定できます。

  • 1 ターンで行ける範囲に「負け」を表すマスが少なくとも 1 つある場合、勝ち
  • 上記に当てはまらない場合 (移動先の候補がない時も含む)、負け

少しわかりにくいと思うので解説すると、 (i, j) から 1 ターン動いた先で手番が回ってくる人、つまり「相手」が負け確定になるようなマスがある場合、そこに移動することで自分が勝ち確定になります。反対に、そのようなマスが 1 つもない場合は自分が負け確定になります。あとはこれを右下からメモ化再帰で求めていけば良いです。

ソースコード

int h, w;
char board[110][110];

// rec[i][j] := (i, j) から始めたら勝つか負けるか?
int rec[110][110];

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

int solve(int x, int y) {
    int &r = rec[x][y];
    if(r != -1) return r;
    r = 1;
    rep(i,0,3) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx == h || ny == w || board[nx][ny] == '#') continue;
        if(solve(nx, ny) == 1) r = 0;
    }
    return r;
}

signed main() {
    cin >> h >> w;
    rep(i,0,h) rep(j,0,w) cin >> board[i][j];
    memset(rec, -1, sizeof(rec));
    cout << (solve(0, 0) ? "Second" : "First") << endl;
    return 0;
}

先攻か後攻かの情報も保持したほうがいいのかな、とか色々考えていたらすんなり書けませんでした。ゲームの問題はもう少し慣れが必要そうです。

Google Code Jam Round 1B 2017 C: Pony Express

想定解法と違う方法で解いたので一応メモ。

問題概要

街が  N  (2 \le N \le 100) つあり、街  i j を結ぶ道路の長さは  D_{ij} (km) (-1 \le D_{ij} \le 10^{9}, ただし  -1 の時は道路がないことを表す) である。

それぞれの街には馬がおり、街  i にいる馬は時速  s_{i} (km/h)  (1 \le s_{i} \le 10^{3}) で移動することができ、最大で  e_{i} (km)  (1 \le e_{i} \le 10^{9}) 移動できる。街と街の移動には馬を利用する (必要ならば途中の街で馬を乗り継ぐこともできる)。このとき、以下のクエリを  Q (1 \le Q \le 100) 処理せよ。

  •  U から  V に向けて、上記の制約を満たした乗り継ぎをしながら馬に乗って行くことを考えたとき、かかる時間の最小値を求めよ。

解説

拡張ダイクストラで求めることができます。

rec[i][j][k] := 街 i を出発時点で、今乗っている馬 j が距離 k を走った時にかかる累計時間の最小値 となるような配列を作ります。この配列を真面目に取ろうとしても  10^{2} \times 10^{2} \times 10^{9} のサイズの配列を取らなければならないので無理ですが、実際はそのほとんどが使われることが無いため、使うところだけ利用できるように map を利用して作ることにします。

 x から  y に行く際には、馬の走れる距離が十分にあると仮定すると以下の  2 つの遷移が考えられます。

  •  y に着いた後も、今乗っている馬に乗り続ける
  •  y に着いたら、街  y にいる馬に乗り換える

別の馬に乗り換えた場合、走行距離の情報がリセットされることに注意して遷移すれば良いです。制約を満たさない動き (たとえば、馬の走行距離の限界を超えるなど) をしないようにすることも重要です。

ソースコード

struct Elem {
    int city, horse, dist;
    double cost;
    Elem(int a, int b, int c, double d) : city(a), horse(b), dist(c), cost(d) {}
};

bool operator<(const Elem &a, const Elem &b) {
    return a.cost > b.cost;
}

int e[110], s[110];
int mat[110][110];
signed main() {
    int t; cin >> t;
    repq(cs,1,t) {
        int N, Q; cin >> N >> Q;
        rep(i,0,N) cin >> e[i] >> s[i];
        rep(i,0,N) rep(j,0,N) cin >> mat[i][j];
        printf("Case #%lld:", cs);
        rep(i,0,Q) {
            // city, horse, dist
            map<int, map<int, map<int, double> > > rec;
            int u, v; cin >> u >> v;
            double ans = DBL_MAX;
            u--; v--;
            priority_queue<Elem> q;
            q.push(Elem(u, u, 0, 0.0));
            while(!q.empty()) {
                Elem pick = q.top(); q.pop();
                int from = pick.city, d = pick.dist, usg = pick.horse;
                if(from == v) {
                    ans = min(ans, pick.cost);
                    break;
                }
                rep(to,0,N) {
                    if(mat[from][to] == -1) continue;
                    if(d + mat[from][to] > e[usg]) continue;
                    int nd = d + mat[from][to];
                    double c = (double)mat[from][to] / s[usg];
                    if(!rec[to][usg].count(nd) || rec[to][usg][nd] > rec[from][usg][d] + c) {
                        rec[to][usg][nd] = rec[from][usg][d] + c;
                        q.push(Elem(to, usg, nd, rec[to][usg][nd]));
                    }
                    if(!rec[to][to].count(0) || rec[to][to][0] > rec[from][usg][d] + c) {
                        rec[to][to][0] = rec[from][usg][d] + c;
                        q.push(Elem(to, to, 0.0, rec[to][to][0]));
                    }
                }
            }
            printf(" %.12lf", ans);
        }
        cout << endl;
    }
    return 0;
}

実はワーシャルフロイドを 2 回やる想定解法をまだ読んでいない・・・ (読もう)

TopCoder SRM 712 Div1 Easy: LR

オーバーフローで死ぬつらい問題。

問題概要

原文 → TopCoder Statistics - Problem Statement

環状になっているサイズ  n の数列  s, t がある (0-indexed)。 i 番目の要素に対して左隣は要素  i-1 であり、右隣は要素  i+1 である。 (ただし、 (n-1) 番目の要素の右隣は要素  0 である。)

数列に対して、以下の 2 種類の操作が可能である。

  • L: すべての要素に対して、その左隣の要素の値だけ加算する。
  • R: すべての要素に対して、その右隣の要素の値だけ加算する。

 s に対してこの 2 種類の操作を合計 100 回まで行って、数列  s を数列  t にすることができれば、その操作手順を出力せよ。できないならば、No solution を出力せよ。

解説

操作を見ればわかるように、各要素に対して加算の操作しかできないため s[i] > t[i] となるような要素が一つでもあればその時点で不可能です。また、最初から  s t が一致していれば操作する必要がありません。このチェックは最初にすべきでしょう。

今回の場合、総和を比較することによって操作回数を知ることができます。数列  s の総和を  S として、簡単に説明します。

どちらの操作においても、操作後には現時点での数列の総和ぶん増えます。これは各要素で隣にあるものを足しているので、各要素が 1 度ずつ加算されているということからわかりますね。ですので、操作をするごとに数列の総和は  S \rightarrow 2S \rightarrow 4S \rightarrow 8S \dots のように増えていくことになります。( t の総和  -  s の総和) に対してこの性質を利用して計算していけば、操作回数が特定できます。

また、L と R の並び順は関係ない こともわかります。これは L -> R と R -> L の結果が等しいことを利用すれば示せます。したがって、LL…L RR…R のような操作手順に帰着できるため、L と R の個数さえ分かれば良いことになります。

答えを導く方法の一つとして DP があります。 dp[i][j][k] := R を i 回、L を j 回行った時の k 番目の要素の値 となるような配列を作ります。この遷移は R を行うか L を行うかしかないので、その 2 つを書けば良いです。

ソースコード

ll dp[110][110][60];
class LR {
    public:
    string construct(vector<long long> s, vector<long long> t) {
        int n = (int)s.size();
        rep(i,0,n) if(s[i] > t[i]) return "No solution";
        if(s == t) return "";

        ll ssum = accumulate(s.begin(), s.end(), (ll)0);
        ll tsum = accumulate(t.begin(), t.end(), (ll)0);
        if(ssum == 0 || (tsum - ssum) % ssum) return "No solution";
        ll diff = (tsum - ssum) / ssum;
        ll turn = 1, d = 1;
        while(1) {
            if(diff - d < 0) return "No solution";
            if(diff - d == 0) break;
            diff -= d;
            d *= 2; turn++;
        }

        memset(dp, 0, sizeof(dp));
        rep(i,0,n) dp[0][0][i] = s[i];
        repq(x,1,turn) repq(i,0,x) {
            int j = x - i;
            bool ok = true;
            rep(k,0,n) {
                ll v = -1, w = -1;
                if(j != 0) v = dp[i][j-1][k] + dp[i][j-1][(k-1+n)%n];
                if(i != 0) w = dp[i-1][j][k] + dp[i-1][j][(k+1)  %n];
                dp[i][j][k] = max(v, w);
                if(dp[i][j][k] != t[k]) ok = false;
            }
            if(ok) return string(i, 'R') + string(j, 'L');
        }
        
        return "No solution";
    }
};

これ通せなかったのつらいなあ (本番は回数の決め打ちをしていなかったのでほげ)