C - 節制

時間制限 : 2sec / メモリ制限 : 256MB

問題文

セキュリティ意識が高く、最新鋭の錠を購入した高橋君ですが、財布の管理は甘かったらしくお金がピンチな状況です。

高橋君の収入は安定せず、次の収入があるのは今から N 日後です。高橋君は N 日間、できるだけ食費を抑えて節約生活を送ることにしました。

はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。

普通の食事: A 円の出費をして、満腹度が B 増える。質素な食事: C 円の出費をして、満腹度が D 増える。（ただし、C<A かつ D<B）食事抜き: 出費なしで、満腹度が E 減る。厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、N 日間で一度も満腹度が 0 以下にならないようにしなければなりません。

高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか？

ただし、高橋君は超人級の胃袋を持っており、その満腹度には上限がないとする。すなわち、いくら食事をしても高橋君の満腹度が頭打ちになることはない。

note

変数が三つあるが、変数を一つ固定すると、他の二つの変数の範囲がわかるので、それを元に固定が出来るやつ。　計算量はO(n)

#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long 

using namespace std;

const ll INF=1LL<<60;

struct Food{
    ll price;
    ll value;
};

class Temperance
{
public:
    ll days, resource;
    Food cheap, luxuary;
    ll down;
    ll expense;
    Temperance();
    ~Temperance();
    void exec();
};

Temperance::Temperance(){
    expense = 0;
    cin >> days >> resource;
    cin >>  luxuary.price >> luxuary.value >> cheap.price >> cheap.value >> down;
}

Temperance::~Temperance(){}

void Temperance::exec(){
    expense = INF;
    for (ll i = 0; i <= days; ++i)
    {
        ll luxuary_num = (double)((days - i) * down - i * cheap.value - resource) / (luxuary.value + down) + 1;
        if(luxuary_num < 0) luxuary_num = 0;
        expense = min( expense, cheap.price * i + luxuary.price * luxuary_num);
    }
    cout << expense << endl;

}

int main(){
    Temperance t = Temperance();
    t.exec();
}

D - 阿弥陀

時間制限 : 4sec / メモリ制限 : 256MB

問題文

古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？

あみだくじを行うときは、まず N 本の平行な縦線を引く。次に、M 本の横線をその中に引いていく。それぞれの横線は隣り合う 2 本の縦線を結ぶように引かなければならず、2 本以上の横線がまったく同じ高さにあってはいけない。ここでは、上から i (1 ≦ i ≦ M) 番目にある横線が、左から Ai (1 ≦ Ai<N) 番目の縦線と Ai+1 番目の縦線を結んでいるとしよう。

N=5, M=7, A={1,4,3,4,2,3,1} の場合のあみだくじを以下に示す。くじを引くときは、縦線を 1 本選び、その上端から線を下っていく。途中で横線に遭遇したときには必ず曲がらなければならず、また縦線を上向きに辿ってはいけない。たとえばこのあみだくじで左から 4 番目の縦線から始めてくじを引くと、左から 3 番目の縦線に辿り着く。

さて、ここまでは普通のあみだくじであるが、何かにつけビッグデータという言葉が騒がれる昨今である。あみだくじがこれから先生きのこるためには、あみだくじもビッグになってビッグデータに対抗していかなければならない。

そこで、あみだくじを縦に D 個つなげることで巨大なあみだくじを作ることを考えよう。たとえば、先ほど例に挙げたあみだくじを 2 個つなげてみると以下のようになる。この場合、左から 4 番目の縦線から始めてくじを引くと、辿り着く場所は左から 5 番目の縦線になる。

こうして作った巨大あみだくじだが、あみだくじ本来の目的を果たせなければビッグになった意味もない。つまり、この巨大なあみだくじを使ってくじを引いた結果がどうなるかを効率よく計算できなければ、せっかく作った巨大あみだくじもただの落書きである。

そこで、1 ≦ k ≦ N を満たすすべての整数 k に対し、巨大あみだくじの左から k 番目の縦線を選んで線を辿っていったとき、最終的に下端で左から何番目の縦線に行き着くかを計算するプログラムを書いて欲しい。

note

ダブリングを使うことで、あるあみだくじをn個つなげたときの、あみだくじの行き先を log(n)で求めることが出来る。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Amida
{
public:
    int n, m, d;
    vector<int> a;
    vector<int> to_a;

    Amida();
    ~Amida();
    void exec();
    void setResultAmida();

};

Amida::Amida(){
    cin >> n >> m >> d;
    for (int i = 0; i < m; ++i)
    {
        int tmp;
        cin >> tmp;
        tmp--;
        a.push_back(tmp);
    }
}

Amida::~Amida(){}

void Amida::exec(){
    setResultAmida();
    vector<int> ans;
    for (int i = 0; i < n; ++i)
    {
        ans.push_back(i);
    }
    for (int i = 0; d >> i > 0; i++)
    {
            if(d >> i & 1){
                vector<int> tmp(n);
                for (int j = 0; j < n; ++j)
                {
                    tmp[j] = to_a[ans[j]];
                }
                for (int j = 0; j < n; ++j)
                {
                    ans[j] = tmp[j];
                }
            }

            vector<int> new_to_a(n);
            for (int j = 0; j < n; ++j)
            {
                new_to_a[j] = to_a[to_a[j]];
            }

            for (int j = 0; j < n; ++j)
            {
                to_a[j] = new_to_a[j];
            }
    }

    for (int i = 0; i < n; ++i)
    {
        cout << ans[i] + 1 << endl;
    }
}

void Amida::setResultAmida(){
    vector<int> tmp;
    for (int i = 0; i < n; ++i)
    {
        tmp.push_back(i);
    }
    for (int i = 0; i < m; ++i)
    {
        swap(tmp[a[i]], tmp[a[i]+1]);
    }

    to_a.reserve(n);
    for (int i = 0; i < n; ++i)
    {
        to_a[tmp[i]] = i;
    }

}

int main(){
    Amida amida = Amida();
    amida.exec();
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 013 #38

C - 節制

問題文

note

D - 阿弥陀

問題文

note