Code Festival 2016 qualB

[TakefumiYamamura]

http://code-festival-2016-qualb.contest.atcoder.jp/ A○B○C×D○E×

[TakefumiYamamura]

A - Signboard

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

配点 : 100 点

問題文

CODE FESTIVAL 2016が開催されます。開催にあたって、高橋君はCODE FESTIVAL 2016の看板を作ることにしました。

看板にはCODEFESTIVAL2016と書きたかったのですが、高橋君は間違えて異なる文字列Sを書いてしまいました。幸い、書いた文字列の長さは間違っていませんでした。

そこで高橋君は、ある文字を別の文字に書き換えるという操作を最小の回数行って、この文字列をCODEFESTIVAL2016に書き換えることにしました。

書き換えの回数の最小値を求めてください。

制約

Sの長さは16である。 S は英大文字、英小文字、数字からなる。

#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long 

using namespace std;

int main(){
    string s;
    string ans;
    ans = "CODEFESTIVAL2016";
    int count = 0;
    cin >> s;
    for (int i = 0; i < 16; ++i)
    {
        if (s[i] != ans[i])
        {
            count++;
        }
    }
    cout << count << endl;
}

[TakefumiYamamura]

B - Qualification simulator

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

配点 : 200 点

問題文

CODE FESTIVAL 2016の予選にはN人が参加しました。参加者は、国内の学生であるか、海外の学生であるか、どちらでもないかのどれかです。

予選は国内または海外の学生のみが通過することができ、上位の学生から順に、以下の条件を満たすときに通過します。学生でない参加者は予選を通過できません。

国内の学生は、現在予選の通過が確定した参加者がA+B人に満たなければ、予選を通過する 海外の学生は、現在予選の通過が確定した参加者がA+B人に満たず、さらに海外の学生の中での順位がB位以内なら、予選を通過する 参加者の情報を表す文字列Sが与えられます。 Sのi文字目がaのとき予選でi位の参加者が国内の学生であることを、 Sのi文字目がbのとき予選でi位の参加者が海外の学生であることを、 Sのi文字目がcのとき予選でi位の参加者がそのどちらでもないことを表しています。

すべての参加者について、上位から順に、予選を通過した場合はYes、そうでない場合はNoを出力するプログラムを作成してください。

制約

1≦N,A,B≦100000 A+B≦N S の長さはNである。 S は文字aとbとcのみからなる。

#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long

using namespace std; 

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    string s;
    cin >> s;
    int sum = 0;
    int sum_b = 0;
    for (int i = 0; i < N; ++i)
     {
        if (s[i] == 'c')
        {
            cout << "No" << endl;
        }else if(s[i] == 'a' && sum < (A+B) ){
            cout << "Yes" << endl;
            sum++;
        }else if(s[i] == 'b' && sum < (A+B) && sum_b < B){
            cout << "Yes" << endl;
            sum++;
            sum_b++;
        }else{
            cout << "No" << endl;
        }
     } 
}

[TakefumiYamamura]

C - Gr-idian MST

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

配点 : 500 点

問題文

xy平面上の0≦x≦W,0≦y≦Hをみたす領域にあるx,yともに整数である点すべてに、ひとつずつ家があります。

x座標が等しくy座標の差が1であるか、y座標が等しくx座標の差が1であるような2点の組のうち、両方の点に家が存在するような全てのものに対し、その2点の間には舗装されていない道路があります。

座標(i,j)と(i+1,j)にある家の間の道路を舗装するのにはjの値にかかわらずコストがpi、 座標(i,j)と(i,j+1)にある家の間の道路を舗装するのにはiの値にかかわらずコストがqjかかります。

高橋君は、このうちいくつかの道路を舗装し、舗装された道路のみを通って任意の2つの家の間を行き来できるようにしたいです。 かかるコストの総和の最小値を求めてください。

制約

1≦W,H≦105 1≦pi≦108(0≦i≦W−1) 1≦qj≦108(0≦j≦H−1) pi(0≦i≦W−1)は整数である qj(0≦j≦H−1)は整数である

note

最小全木をクラスカル法かプリム法で求めるだけと思いきや、一工夫必要。 実際はクラスカル法の時みたいにunion find を使わなくても問題のヒューリスティックにきずけば解ける。

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>

#define ll long long
using namespace std;

int main(){
    ll w, h;
    cin >> w >> h;
    std::vector<pair<ll, ll> > v;
    for (ll i = 0; i < w; ++i)
    {
        ll p;
        cin >> p;
        v.push_back(pair<ll, ll>(p, 0)); 
    }
    for (ll i = 0; i < h; ++i)
    {
        ll q;
        cin >> q;
        v.push_back(pair<ll, ll>(q, 1));
    }
    sort(v.begin(), v.end());

    ll ans = 0;
    ll a = w + 1;
    ll b = h + 1;

    for (ll i = 0; i < w+h; ++i)
    {
        ll tmp;
        if (v[i].second == 0)
        {
            ans += v[i].first * b;
            a--; 
        }else{
            ans += v[i].first * a;
            b--;
        }
    }

    cout << ans << endl;

}

[TakefumiYamamura]

D - Greedy customers

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

配点 : 700 点

問題文

高橋商店の前には、N 人の人が 1 列に並んでいます。前から i 人目の人の所持金は正整数 Ai です。

店主の高橋君は、「品物を選んでその価格を表す正の整数 P を設定し、前の人から順にその品物を見せていく」というステップを繰り返します。

各ステップにおいて、各人は、品物を見せられた時、その価格 P が現時点でのその人の所持金以下だった場合その品物を購入し、高橋君の 1 回のステップは終了します。 すなわち、所持金が P 以上の最初の人の所持金が P 減少し、次のステップに移ります。

高橋君は正整数 P の値を、ステップごとに独立に決めることができます。

高橋君はできるだけ多くの品物を売りたいですが、品物を売った人の所持金が 0 になってしまうと、その人は帰れなくなってしまいます。人が帰れなくなってしまうと高橋君は困ってしまうので、どの人の所持金も 0 にしてはいけません。

高橋君に代わって、各人の最初の所持金が与えられたとき、高橋君が最大でいくつの品物を売ることができるかを求めるプログラムを作成してください。

制約

1≦N≦100000 1≦Ai≦109(1≦i≦N) 入力はすべて整数である

note

問題文に書いてあるようにgreedyにやれば解けるぐりぐり。

#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long

using namespace std; 

ll a[100001];
ll sum = 0;
int n;

int main(){
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    sum += a[0] - 1;
    ll limit = 2;
    for (int i = 1; i < n; ++i)
    {
        ll tmp_limit = limit;
        if(a[i] == limit){
            limit++;
        }

        sum += a[i]/tmp_limit;
        if(a[i] % tmp_limit == 0){
            sum--;
        } 
    }
    cout << sum << endl;
}