Mister雑記

競プロやります。

ABC113 解説

A. Discount Fare (100)

問題リンク

概要

A駅からB駅を結ぶ運賃 X円の電車と、B駅からC駅を結ぶ運賃 Y円のバスがある。

バスの運賃が半額のとき、A駅からC駅まで移動するのにかかる運賃の総額を求めよ。

制約

  •  1 \leq X, Y \leq 100
  •  Yは偶数

解説

 X + Y / 2を出力すればいい。

 Yが偶数なので、切り捨て云々も気にする必要はない。

実装例

#include <iostream>

using namespace std;

int main() {
    int X, Y;
    cin >> X >> Y;
    cout << X + Y / 2 << endl;
    return 0;
}

B. Palace (200)

問題リンク

概要

 N個の地点が与えられ、 i番目の地点の標高が H_iである。

標高 xメートルの地点の平均気温が T - 0.006x度であるとき、平均気温が最も Aに近い地点の番号を出力せよ。

制約

  •  1 \leq N \leq 10^3
  •  0 \leq T \leq 50
  •  -60 \leq A \leq T
  •  0 \leq H_i \leq 10^5
  • 解は一意に定まる

解説

私がコンテスト中に採ったのが、各地点について先に平均気温を求め、それが最小となるindexを更新していくという方法。

他にもpairとして平均気温とindexをまとめて保持しておけば、ソートして答えを求めることもできる。

実装例

indexを更新していく場合

#include <cmath>
#include <iostream>

using namespace std;

int main() {
    int N;
    double T, A;
    cin >> N >> T >> A;

    // 各地点の平均気温
    double t[N];
    for (int i = 0; i < N; ++i) {
        double H;
        cin >> H;
        t[i] = T - H * 0.006;
    }

    // tがAに最も近いindex
    int ans = 0;
    for (int i = 1; i < N; ++i) {
        // 地点iの方が近ければ更新
        if (abs(A - t[i]) < abs(A - t[ans])) ans = i;
    }

    // 0-indexedで保持していたことに注意
    cout << ans + 1 << endl;
    return 0;
}

ソートする場合

#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

int main() {
    int N;
    double T, A;
    cin >> N >> T >> A;

    // (平均気温とTの差, index)の配列
    pair<double, int> t[N];
    for (int i = 0; i < N; ++i) {
        double H;
        cin >> H;
        double diff = abs(A - (T - H * 0.006));

        // indexは1-indexedで保持
        t[i] = make_pair(diff, i + 1);
    }

    // pairをソートすると、第一要素がkeyとなる
    // つまり「平均気温とTの差」について昇順にソートされる
    sort(t, t + N);

    cout << t[0].second << endl;
    return 0;
}

C. ID (300)

問題リンク

概要

 N個の県があり、そこに M個の市が属している。

 i番目の市が誕生したのは Y_i年で、 P_i県に属している。

各市に対して、以下のように定められるIDを出力せよ。

  • IDは12桁からなる。
  • 前半6桁は属している県の番号。
  • 後半6桁はその県の中で何番目に誕生したか。

制約

  •  1 \leq N, M \leq 10^5
  •  1 \leq P_i \leq N
  •  1 \leq Y_i \leq 10^9
  •  Y_iは全て異なる

解説

年についてソートして、早い方から各県に追加していく、というのが主な方針となる。 といってもこれがそこそこ実装が大変で、また人によって大きく実装方法が異なると思われる。 以下に載せる私の実装例もあくまで一例に過ぎない。

なおそれとは別に地味に面倒なのが出力のフォーマットで、coutで0埋めをする方法を知らないという人も多かったのではなかろうか。私も覚えていなかったので、本番中にググっていた。 フォーマットをまるごと暗記する必要はないが、「大体こんな感じだったはず」といった雰囲気程度は覚えておくと何かと便利である。

実装例

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <tuple>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    tuple<int, int, int> data[M];
    // (Y_i, P_i, i)の配列

    for (int i = 0; i < M; ++i) {
        int p, y;
        cin >> p >> y;
        data[i] = make_tuple(y, p, i);
    }

    // tupleをソートするときは第一要素がkeyとなる
    // つまりY_iによって昇順にソートされる
    sort(data, data + M);

    int cnt[N + 1];
    fill(cnt, cnt + N + 1, 0);
    // 各県に今属している市の数

    pair<int, int> id[M];
    // 各市の(属する県、県の中で誕生した順番)

    for (int i = 0; i < M; ++i) {
        int y, p, idx;
        tie(y, p, idx) = data[i];
        ++cnt[p];
        id[idx] = make_pair(p, cnt[p]);
    }

    for (int i = 0; i < M; ++i) {
        // setwで文字数、setfillで埋める文字を指定
        // iomanipをincludeする必要があるので注意
        cout << setw(6) << setfill('0') << id[i].first;
        cout << setw(6) << setfill('0') << id[i].second << endl;
    }
    return 0;
}

D. Number of Amidakuji

問題リンク

概要

鉛直な縦棒 W本からなるあみだくじについて考える。

各縦棒の長さは H+1であり、端点からの距離が正整数の場所にのみ水平な横棒を引くことができる(つまり各縦棒からは最大 H本の横棒を引くことができる)。

ただし各横棒は隣接していてはならず、また隣り合う2本の縦棒の間にしか引くことはできない(この辺の詳しいルールは公式ページを参照)。

このとき、一番左の縦棒から始めて最終的に左から K本目の縦棒に行き着くようなあみだくじの総数を、 10^9 + 7で割った余りを求めよ。

制約

  •  1 \leq H \leq 100
  •  1 \leq W \leq 8
  •  1 \leq K \leq W

解説

以降、上から距離 iの位置を「 i段目」と呼ぶことにする。このときあみだくじの始点は「0段目」であり、終点は「 H + 1段目」となる。

さて、全パターンを愚直に探索するとなると、各段に横棒を引くパターンがざっと 2^W通り(実際はもっと少ないが)、それが H段あるので (2^W)^Hという途方もないスケールになってしまう。

ここで知りたいのは「最終的に1がどこにいるか」だけであることから、 dp_{h, k} =  h段からなり、1が最終的に左から k本目にいるようなあみだくじの数」というDPを考える。すると答えは dp_{H, K}となる(この辺説明が下手で申し訳ない)。これを hについて更新していけばいい。

ではどうやって更新するかというと、 W \leq 8 Wの制約が緩いことから全ての横棒のパターンを試せば良い。これにはbit全探索が有効である。

f:id:misteer:20181104230050p:plain

ただし横線には条件があり、この中でも「各横棒は隣接していてはならない」についてはちゃんとチェックする必要がある。これはbitで言えば「1が隣接していること」と同値となる。

これで解けるには解けるのだが、AtCoderにしては実装が相当重い。まぁ頑張ろうとしか言えない。

実装例

#include <iostream>

using namespace std;

using ll = long long;

const ll MOD = 1e9 + 7;

int main() {
    int H, W, K;
    cin >> H >> W >> K;

    --K;
    // 以降縦棒の番号は0-indexedで扱う

    ll dp[H + 1][W];
    fill(dp[0], dp[H + 1], 0);
    dp[0][0] = 1;
    // dp[h][k] = 横線h段からなるあみだくじで、0がkに来るものの数

    for (int h = 0; h < H; ++h) {
        for (int b = 0; b < (1 << (W - 1)); ++b) {

            // 横線が隣り合っていないかチェック
            bool judge = true;
            for (int i = 0; i < W - 2; ++i) {
                // これで末尾が11のときに弾くことができる
                if ((b >> i) % 4 == 3) judge = false;
            }

            if (!judge) continue;

            // 各始点がどこへ移動するか求める
            int perm[W];
            for (int i = 0; i < W; ++i) perm[i] = i;

            for (int i = 0; i < W - 1; ++i) {
                // あみだくじのルールに従って位置をswap
                if ((b >> i) & 1) swap(perm[i], perm[i + 1]);
            }

            // 配る
            for (int i = 0; i < W; ++i) {
                dp[h + 1][perm[i]] += dp[h][i];
                dp[h + 1][perm[i]] %= MOD;
            }
        }
    }

    cout << dp[H][K] << endl;
    return 0;
}

DPとbit全探索を使う、ABC-Dにしては難しめな問題。 とはいえこの辺の実装は慣れるしかない。

感想

  • 実装も接続も重いコンテストだった。
    • Dの画像とサーバーが半分だったのが原因だとかなんとか
  • 個人的には18位が獲れたので満足。