ABC 246

Table of Contents

A - Four Points

問題

辺が $x$ 軸に平行または $y$ 軸に平行であるから, 長方形を構成する4点に関して $x$ 座標が同じ点が2つずつ, $y$ 座標が同じ点が2つずつある.

この問題では3点が与えられるので残る1点の座標は

となる.

提出コード

B - Get Closer

問題

$(A, B)$ 方向への単位ベクトルを求めれば良いので $\displaystyle \left(\frac{A}{\sqrt{A^2 + B^2}}, \frac{B}{\sqrt{A^2 + B^2}} \right)$ が答え.

提出コード

C - Coupon

問題

まず各商品に対して $\frac{A_i}{X}$ 枚のクーポンを使う. クーポンが足りなくなったらそのまま.

クーポンが余った場合, 各商品に払わないといけない金額は $X$ 未満になっているので, 残高が高い順にクーポンを適用させていけばよい.

提出コード

D - 2-variable Function

問題

$f(a,b) = a^3 + a^2b + ab^2 + b^3$ とする. $f(a,b) \geq N$ を満たす最小の $f(a, b)$ を求める.

$N \leq 10^{18}$ より $0 \leq a, b \leq 10^6$ である. $a$, $b$ は非負整数であるから $f(a,b)$ は $a$, $b$ に関して増加関数である. よって $a$ を固定したときの $f(a, b) \geq N$ を満たす最小の $f(a, b)$ を $f_a(b_{\mathrm{min}})$ とすると $f_a(b_{\mathrm{min}})$ は $b$ を二部探索することでもとめることができる. すべての $a$ に関して $f_a(b_{\mathrm{min}})$ を求めたときその最小値が答えとなる.

計算量は $N^{1/3} \log N^{1/3}$.

提出コード

E - Bishop 2

問題

一つ前の移動と同じ方向へ進む場合はコスト 0 で移動し, 違う方向に進む場合はコスト 1 で移動する. これをダイクストラ風にして解く.

int di[] = {-1, -1, 1, 1};
int dj[] = {-1, 1, -1, 1};

struct Point {
    int i, j, dir, cost;
};

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

void solve() {
    int n;
    cin >> n;
    int ax, ay, bx, by;
    cin >> ax >> ay >> bx >> by;
    ax--, ay--, bx--;
    by--;

    vector<string> board(n);
    rep(i, n) cin >> board[i];

    vvint dist(n, vint(n, INF));
    dist[ax][ay] = 0;

    priority_queue<Point, vector<Point>, greater<Point>> pq;
    pq.push({ax, ay, 4, 0});
    vector<vvint> done(n, vvint(n, vint(5)));

    while (pq.size()) {
        auto [x, y, dir, cost] = pq.top();
        pq.pop();

        if (done[x][y][dir])
            continue;  // これを入れないと TLE する.
                       // 入れなかった場合, 確定したところをもう一度探索してしまうため.
        done[x][y][dir] = 1;

        rep(d, 4) {
            int nx = x + di[d], ny = y + dj[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
            if (board[nx][ny] == '#')
                continue;
            int inc = (dir == d) ? 0 : 1;
            if (dist[nx][ny] >= cost + inc) {  // 距離は同じでも違う方向からくるパターンもあるので = を加える
                dist[nx][ny] = cost + inc;
                pq.push({nx, ny, d, cost + inc});
            }
        }
    }

    if (dist[bx][by] == INF)
        cout << -1 << endl;
    else
        cout << dist[bx][by] << endl;
}

提出コード