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位だったので本当に惜しい。