arrows blog

解いた問題などを適当に書いていきます。

SRM 699 div2

SRM シミュレーション 二分探索 最短経路問題

Easy

問題概要

最初、整数値x = 0である。
N回、以下のいずれかの操作を繰り返す。

  1. xに0からAまでのいずれかの整数値を加算する。
  2. xに0からBまでのいずれかの整数値を減算する。

N回の操作の後、xの値が0でなければならない。
上記の操作を最適に行ったとき、途中のxの値の最大値を求めよ。

制約

  • 2 ≤ N ≤ 50
  • 1 ≤ A, B ≤ 50

解法

シミュレーションする。

1ずつ進めていき、xにAを加算していく。
もし、i回目の操作でxの値がB × (N - i - 1) (残りの操作で可能な限り減算できる値)より小さい場合、最大値をxに更新する。以上のとき、最大値をB × (N - i - 1)に更新して終了する。

コード

class UpDownHiking {
  public:
    int maxHeight(int N, int A, int B)
    {
        int res = 0, h = 0;
        for (int i = 0; i < N; i++) {
            h += A;
            if (B * (N - i - 1) > h) {
                res = max(res, h);
            } else {
                res = max(res, B * (N - i - 1));
                break;
            }
        }
        return res;
    }
};

Med

問題概要

値Sが与えられる。
以下の操作したときに値がSになる整数Xを求めよ(存在しない場合は、-1を出力する)。

  1. 値Xを決める。
  2. sum = 0とする。
  3. もし、値Xが0なら終了する。
  4. sumにXを加算し、Xを10で割った整数値を新たなXとし、3に戻る。

制約

  • 1 ≤ S ≤ 1018

解法

二分探索。

答えとなるXを二分探索して決める。
答えは、[1, S]の間になるので、下限と上限はそれぞれ、1とSなどとする。

コード

class LastDigit {
  public:
    long long c(long long x)
    {
        long long sum = 0;
        while (x > 0LL) {
            sum += x;
            x /= 10LL;
        }
        return sum;
    }
    
    long long findX(long long S)
    {
        long long l = 0, r = S;
        while (r - l > 1) {
            long long mid = (l + r) / 2;
            if (c(mid) > S) {
                r = mid;
            } else {
                l = mid;
            }
        }
        if (c(l) == S) return l;
        if (c(r) == S) return r;
        return -1;
    }
};

Hard

問題概要

1からNで番号付けられた、N個のノードがある。
M個のエッジがある(実際にはM個ではない)。
各エッジiは、kaiからlbiへ進める(単方向)ことを表す。ただし、k, lは1以上の任意の整数であり、k × ai ≤ Nかつl × bi ≤ Nである必要がある。

すべてのエッジのコストは1である。
ノードSからノードTへ行くときの最小コストを求めよ(行けない場合は-1を出力する)。

制約

  • 2 ≤ N ≤ 105
  • 1 ≤ S, T ≤ N
  • 1 ≤ M ≤ 500
  • 1 ≤ ai, bi ≤ N
  • (ai, bi)のペアは全て異なる。

解法

算数 + ダイクストラ(コストが均一なのでBFSでも大丈夫だと思う)。

d[v] := 頂点vにいるときの最小コストとする。

まず、スタートSから行けるノードbiをチェックする。
これは、Sがaiで割り切れるなら行けるので、その場合、d[bi] = 1として、priority_queue(以下、pqとする)にpushする。pqには、コストとノードのペアを持たせる。

次に、ダイクストラの内部に入る。
もし、Tが現在のノードvで割り切れるならば終了する(d[v]が答えとなる)。
遷移では、ノードvとaiとの最小公倍数を取り、その値がN以下であり、biが未訪問の場合、d[bi] = d[v] + 1としてpqにpushする。
この操作を繰り返せば良い。

ノードvとaiとの最小公倍数を取るのは、ノードvに到達できるならば、ノードk × v (kは1以上の任意の整数)にも到達でき、aiも、l × ai (lは1以上の任意の整数)となるようにlをかけられるためである。

コード

#define INF (1<<29)
typedef pair<int, int> pii;
typedef long long ll;

class FromToDivisibleDiv2 {
  public:
    ll lcm(ll a, ll b)
    {
        return a / __gcd(a, b) * b;
    }
    
    int shortest(int N, int S, int T, vector <int> a, vector <int> b)
    {
        int M = a.size();
        vector<int> d(N + 1, INF);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for (int i = 0; i < M; i++) {
            if (S % a[i] == 0) {
                d[b[i]] = 1;
                pq.push(pii(1, b[i]));
            }
        }

        while (!pq.empty()) {
            pii p = pq.top(); pq.pop();
            int c = p.first, v = p.second;
            if (T % v == 0) return d[v];
            if (d[v] < c) continue;

            for (int i = 0; i < M; i++) {
                ll nv = lcm(v, a[i]);
                if (nv > N) continue;
                if (d[v] + 1 < d[b[i]]) {
                    d[b[i]] = d[v] + 1;
                    pq.push(pii(d[b[i]], b[i]));
                }
            }            
        }
        return -1;
    }        
};

感想

簡単な回だったが、本番では、medは超単純なミスをして落とし、hardは答えが合わなく(lcmが間違えていたため)未提出だった。
上のミスがなければおそらく1位だったので本当に惜しい。

AOJ 0542 Authentication Level

AOJ グラフ

問題概要、制約

説明が難しいので省略。サンプルの説明のところ読むと概要を理解しやすい。
Authentication Level | Aizu Online Judge

解法

ダイクストラ。

それぞれの事務所について、部屋をx個訪問したときの最小コストを求める。
これはダイクストラにより求めることができる。

後は、事務所1において何個の部屋を訪れるか決めうちする。この個数をrとすると、事務所2には、R - r 個の部屋を訪れることになる。ただし、その個数がそれぞれの事務所の部屋の個数を超えてはならない。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define INF (1<<29)
 
struct State {
    int c, x, y;
     
    State (int c, int x, int y) : c(c), x(x), y(y) {}
 
    bool operator < (const State &s) const {
        return c > s.c;
    }
};
 
int main()
{
    int R;
    while (cin >> R, R) {
        int W, H, sy, sx;
        vector<int> level[2];
        for (int i = 0; i < 2; i++) {
            cin >> W >> H >> sx >> sy;
            sy--; sx--;
            vector<vector<int>> a(H, vector<int>(W));
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    cin >> a[i][j];
                }
            }
 
            vector<vector<bool>> visited(H, vector<bool>(W, 0));
            visited[sy][sx] = 1;
             
            priority_queue<State> pq;
            pq.push(State(a[sy][sx], sx, sy));
 
            level[i].push_back(0);
 
            const int dx[] = {-1, +0, +1, +0};
            const int dy[] = {+0, -1, +0, +1};
            int maxi = 0;
             
            while (!pq.empty()) {
                State st = pq.top(); pq.pop();
                level[i].push_back(max(maxi, st.c));
                maxi = max(maxi, st.c);
                for (int j = 0; j < 4; j++) {
                    int nx = st.x + dx[j];
                    int ny = st.y + dy[j];
                    if (0 <= nx && nx < W && 0 <= ny && ny < H &&
                        !visited[ny][nx]) {
                        visited[ny][nx] = 1;
                        pq.push(State(a[ny][nx], nx, ny));
                    }
                }
            }
        }
         
        int res = INF;
        for (int i = 0; i <= R; i++) {
            int j = R - i;
            if ((int)level[0].size() <= i) continue;
            if ((int)level[1].size() <= j) continue;
            res = min(res, level[0][i] + level[1][j]);
        }
        cout << res << endl;
    }
    return 0;
}

AOJ 1020 Cleaning Robot

AOJ 数学 DP

問題概要、制約

省略。
Cleaning Robot | Aizu Online Judge

解法

確率DPをする。

dp[i][j] := バッテリーをi使って位置jにいるときの確率。
位置は二次元座標だが、(x, y)をy * 3 + xのようにすると次元を1つ落とすことができる。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
pii get_pos(int x)
{
    return pii(x / 3, x % 3);
}
 
bool inField(int x, int y)
{
    return (0 <= x && x < 3 && 0 <= y && y < 3);
}
 
int main()
{
    int N;
    while (cin >> N, N) {
        string S = "ABCDEFGHI";
        char a[3];
        for (int i = 0; i < 3; i++) {
            cin >> a[i];
        }
        int s = S.find(a[0]);
        int t = S.find(a[1]);
        int b = S.find(a[2]);
 
        double dp[25][9] = {{}};
        pii p = get_pos(b);
 
        dp[0][s] = 1;
         
        const int di[] = {-1, +0, +1, +0};
        const int dj[] = {+0, -1, +0, +1};
         
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 9; j++) {
                if (dp[i][j] == 0) continue;
                pii n = get_pos(j);
                for (int k = 0; k < 4; k++) {
                    int ni = n.first + di[k];
                    int nj = n.second + dj[k];
                    if (!inField(nj, ni) || (pii(ni, nj) == p)) {
                        dp[i+1][j] += dp[i][j] / 4;
                    } else {
                        dp[i+1][ni*3+nj] += dp[i][j] / 4;
                    }
                }
            }
        }
        printf("%.10f\n", dp[N][t]);            
    }    
    return 0;
}

AOJ 2665 Hopping Hearts

AOJ DP

問題概要

長さL-1の平均台の上にN羽のうさぎがいる。i番目のうさぎの初期位置はxiであり、0 ≤ xi ≤ xi+1 ≤ L-1を満たす。

それぞれのうさぎは、1回ジャンプすると右にaiだけ移動できる。任意の回数ジャンプすることできるが、別のうさぎを飛び越えたり、L以上の位置に移動することはできない。同時にジャンプしていられるのは高々 1 羽であり、ある位置に存在できるうさぎの数も高々 1 羽である。

初期状態から始めてジャンプを任意の回数繰り返したあとの状態として、あり得るものは何通りあるか。1 000 000 007 で割った余りで求めよ。

制約

  • 1 ≤ N ≤ 5000
  • 1 ≤ L ≤ 5000
  • 0 ≤ xi ≤ xi+1 ≤ L-1
  • 0 ≤ ai ≤ L-1

解法

ごちうさを見ると解ける。


DPをする。
dp[i][j] := i番目のうさぎまで見て、区切り板がjにあるときの場合の数。
区切り板は越えることのできない壁を表す。

上記のdpだと5000 × 5000のメモリを消費するが、1つ前のうさぎの状態がわかれば良いので2 × 5000のメモリ量で済む。

注意点は、うさぎはその場でぴょんぴょんすることがあるということである。

コード

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
const ll MOD = ((1e9) + 7);
  
int dp[2][5050];
  
int main()
{
    int N, L;
    scanf("%d %d", &N, &L);
    vector<int> x(N), a(N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &x[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
  
    fill(dp[0], dp[0] + L, 1);    
    for (int i = 0; i < N; i++) {
        int curr = i & 1, next = !curr;
        for (int j = x[i]; j < L; j += a[i]) {
            if (j > 0) {
                dp[next][j] += dp[curr][j-1];
            } else {
                dp[next][j] = dp[curr][j];
            }
            dp[next][j] %= MOD;
            if (a[i] == 0) break;
        }
          
        for (int j = x[i]; j < L; j++) {
            dp[next][j+1] += dp[next][j];
            dp[next][j+1] %= MOD;
        }
        fill(dp[curr], dp[curr] + L, 0);
    }
    printf("%d\n", dp[N&1][L-1]);
    return 0;
}

AOJ 0307 Nisshinkan Marathon Club

AOJ シミュレーション

問題概要, 制約

長いので省略。
ニッシン館マラソン部 | Aizu Online Judge

解法

シミュレーションをする。


シミュレーションする際には、それぞれの人のいる給水所、各給水所の空の容器の数、中身の入った容器の数を状態に持つと良い。

まず、時間を1ずつ進めていくことを考える。
それぞれの時間で、N人の人の位置を進めていく。
人iが現在いる位置をposiとすると、その人の次の位置は、(posi + pi) % Rとなる。(piは人iのペースであり、Rは周回コースの長さを表す)

それぞれの人について、
時間が0でなければ、次の位置で空の容器の数を1増やす。
また、次の位置の中身の入った容器の数をチェックし、それが、1以上であれば1減らし、0であれば、新たに給水容器が必要になるので答えに1加算する。

上記が全て終了したら、その時間で溜まった空の容器の数を中身の入った容器の数に加算する。

以上を繰り返すと答えが出る。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int N, R, T;
    cin >> N >> R >> T;
    vector<int> p(N), cur(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];        
    }
     
    int res = 0;
    vector<int> e(R), f(R); 
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < N; j++) {
            cur[j] = (cur[j] + p[j]) % R;
            if (i != 0) e[cur[j]]++;
            if (f[cur[j]] > 0) {
                f[cur[j]]--;
            } else {
                res++;
            }
        }
        for (int j = 0; j < R; j++) {
            f[j] += e[j];
            e[j] = 0;
        }
    }
    cout << res << endl;
    return 0;
}