code-festival-2016-qual c

[TakefumiYamamura]

http://code-festival-2016-qualc.contest.atcoder.jp/

[TakefumiYamamura]

A - CF

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

配点 : 100 点

問題文

このコンテストの名前はCODEFESTIVALで、いくつかの文字を消すとCFという文字列にすることが出来ます。

好奇心旺盛な高橋君は、他の文字列に対してもこのようにCFを得られるか気になりました。

英大文字アルファベットからなる文字列sが与えられるので、sからいくつかの文字を消してCFという文字列にすることが出来るか判定してください。

制約

2≦|s|≦100 sは英大文字(A-Z)のみからなる文字列である

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#define ll long long 
using namespace std;

int main(){
    string s;
    cin >> s;

    bool flag1 = false;
    bool flag2 = false; 

    for (int i = 0; i < s.length(); ++i)
    {
        if(s[i] == 'C'){
            flag1 = true;
        }
        if(flag1 && s[i] == 'F'){
            flag2 = true;
        }
    }
    if(flag2){
        cout << "Yes" << endl; 
    }else{
        cout << "No" << endl;
    }

}

[TakefumiYamamura]

B - K個のケーキ / K Cakes

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

配点 : 200 点

問題文

K 個のケーキがあります。高橋君は、1日に一つずつ、K 日かけてこれらのケーキを食べようと考えています。

ケーキはT 種類あり、種類i(1≦i≦T) のケーキはai 個あります。

二日連続で同じ種類のケーキを食べると飽きてしまうため、高橋君は、うまくケーキを食べる順番を決めて、前日と同じ種類のケーキを食べる日数を最小にしようと考えました。

高橋君のために前日と同じ種類のケーキを食べる日数の最小値を求めてください。

制約

1≦K≦10000,1≦T≦100 1≦ai≦100 a1+a2+...+aT=K

メモ

半分超えたやつだけ気にすればええのさ

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long 
using namespace std;

int main(){
    ll k, t;
    ll a[101];
    ll max = 0;
    cin >> k >> t;
    for (int i = 0; i < t; ++i)
    {
        cin >> a[i];
        if(a[i] > max){
            max = a[i];
        }
    }
    if(max > k/2){
        if(k % 2 == 0){
            cout << 2 * (max - k/2) - 1 << endl;
        }else{
            cout << 2 * (max - k/2 - 1) << endl; 
        }
    }else{
        cout << 0 << endl;
    }

}

[TakefumiYamamura]

C - 二人のアルピニスト / Two Alpinists

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

配点 : 400 点

問題文

アルピニストである高橋君と青木君は最近ある有名な山脈を踏破しました。この山脈はN 個の山からなっており、西から東に向けて山1,山2,…,山Nと一直線に並んでいます。高橋君は西から、青木君は東からこの山脈を踏破しました。

山i の高さはhi ですが、二人とも各hi の値は忘れてしまいました。その代わり、各i(1≦i≦N) に対して、山i の山頂にたどり着いた時の、それまでに登った山(山i も含む)の高さの最大値を記録しています。 高橋君の記録した値はTi で、青木君の記録した値はAi です。

各山の高さhi が正の整数であることはわかっています。山の高さの列としてありうるものが何通りあるかを109+7 で割ったあまりを求めてください。

ただし記録が間違っていてありうる山の高さの列が存在しないこともあります。この場合は0を出力してください。

制約

1≦N≦105 1≦Ti≦109 1≦Ai≦109 Ti≦Ti+1(1≦i≦N−1) Ai≧Ai+1(1≦i≦N−1)

note

ごり押し感ぱない、矛盾する場合0出力の過程でコードが汚くなるの巻

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

const ll MOD = 1e9 + 7;

int main(){
    int n;
    ll t[100001];
    ll a[100001];
    ll mint[100001];
    ll mina[100001];
    ll dect[100001];
    ll deca[100001];
    ll ans = 1;

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> t[i];
        dect[i] = 0;
        deca[i] = 0;
    }

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    if(t[n-1] != a[0]){
        cout << 0 << endl;
        return 0;
    }
    ll tmp;
    mint[0] = 1;
    tmp = t[0];
    for (int i = 1; i < n; ++i)
    {
        if(tmp < t[i]){
            mint[i] = 1;
            tmp = t[i];
            dect[i] = t[i];
        }else{
            mint[i] = tmp;
        }
        if(tmp > t[i]){
            cout << 0 << endl;
            return 0;
        }
    }

    mina[n-1] = 1;
    tmp = a[n-1];
    for (int i = n-2; i >= 0; --i)
    {
        if(tmp < a[i]){
            mina[i] = 1;
            tmp = a[i];
            deca[i] = a[i];
        }else{
            mina[i] = tmp;

        }
        if(tmp > a[i]){
            cout << 0 << endl;
            return 0;
        }
        if(dect[i] != 0){
            if(tmp >= dect[i]){

            } else{
                cout << 0 << endl;
                return 0;
            }
        }
    }

    tmp = t[0];
    for (int i = 0; i < n; ++i)
    {
        ans *= min(mint[i], mina[i]) % MOD;
        ans %= MOD;
        if(tmp < t[i]){

            tmp = t[i];
        }
        if(deca[i] != 0){
            if(tmp >= deca[i]){

            } else{
                cout << 0 << endl;
                return 0;
            }
        }
    }

    cout << ans << endl;

}