読者です 読者をやめる 読者になる 読者になる

CODE FESTIVAL 2015 予選A

結果は3完の447位でした(もうダメすぎる).
問題文は日本語なので省略します.
Welcome to CODE FESTIVAL 2015 予選A - CODE FESTIVAL 2015 予選A | AtCoder

[A: CODE FESTIVAL 2015 ]

方針

与えられた文字列の末尾には必ず"2014"という文字列があるので最後の文字を'4'から'5'に変更.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

int main()
{
    string s;
    cin >> s;
    cout << s.substr(0, s.size() - 1) << "5\n";

    return 0;
}

[B: とても長い数列 ]

方針

観察するとi番目の数列A_iはpow(2, n - i - 1)回足される.
int型で計算結果は収まるけど念の為にlong long 型で計算.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll ans = 0, a;
    int n;
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        ans += pow(2, n - i - 1) * a;
    }

    cout << ans << endl;

    return 0;
}

[C: 8月31日 ]

方針

A_iの和をsum_aと置くと求める問題は次のように書ける.

minimize      x_1 + x_2 + \ldots + x_N
subjecto to     sum_a - (A_1 - B_1) \times x_1 - \cdots - (A_N - B_N) \times x_N \le T
          x_1, x_2, \ldots , x_N \in \{0, 1\}

変数x_iが1のときB_iを選択,0のときA_iを選択するとする.
最適解を求めるためには,初め初期解を(x_1, ..., x_N)=(0, ..., 0)として,条件式を満たすまで 係数 A_i - B_i > 0 の大きいものから変数X_iを1にしていく.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

ll Solve()
{
    int n;
    ll t, sum_b = 0, sum_a = 0, a, b;

    cin >> n >> t;
    vector<int> d(n);

    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        sum_b += b;
        sum_a += a;
        d[i] = -(a - b);
    }

    if (t < sum_b)
        return -1;
    if (sum_a <= t)
        return 0;

    sort(d.begin(), d.end());

    int num = 0;
    for (int i = 0; i < n; ++i) {
        sum_a += d[i];
        ++num;
        if (sum_a <= t)
            return num;
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cout << Solve() << endl;

    return 0;
}

[D: 壊れた電車 ]

方針

点検作業時間kに関して二分探索をする.
点検作業時間がkのときすべての車両を点検できるかを判定する.

一番左端の車両は一番左の整備士が点検をする方が良い.
i番目の整備士が点検をしないといけない一番左端の車両をlとする.

・点検作業時間k内にlを点検できないならどのようにしてもk以内には点検できない.
・lを点検できるときは残りの時間でできるだけ右端の車両rを点検する.
 □ x_i <= l なら r = x_i + k
 □ l < x_i なら点検方法は次の2つの内rが最大となるものを選ぶ.
f:id:tatanaideyo:20150927031136p:plain

次のi+1番目の整備士はr+1をlとして同様に点検をする.
最後の整備士が点検を終えた時にrがN以上なら点検可能.それ以外は点検不可能となる.

ソースコード
// 反省点1:nとmをlong long型にしたら通った(オーバーフロー)
// 反省点2: 下のmaxで右辺しか考慮してなかった(よく考えるとkが大きければ左辺の方が得)
//                                         (kが小さいと右辺の方が得.式をいじると分かる)
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

ll n, m;

bool C(ll k, const vector<int> &x)
{
    ll l = 1;
    for (int i = 0; i < m; ++i) {
        ll p = x[i];

        if (k < p - l)
            return false;

        if (p <= l)
            l = p + k + 1;
        else
            l = max(k + 2 * l - p, p + (k - (p - l)) / 2) + 1; // 反省点2
    }

    if (n <= l - 1)
        return true;
    else
        return false;
}

int Solve()
{
    cin >> n >> m;
    vector<int> x(m);
    for (int i = 0; i < m; ++i)
        cin >> x[i];

    ll lb = -1, ub = 3 * n;
    while (ub - lb > 1) {
        ll mid = (lb + ub) / 2;
        if (C(mid, x))
            ub = mid;
        else
            lb = mid;
    }

    return ub;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cout << Solve() << endl;

    return 0;
}