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　　　　　
subjecto to　　　
　　　　　　　　　

変数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が最大となるものを選ぶ．

次の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;
}