Codeforces Round #373 (Div. 2)

A. Vitya in the Countryside

問題文

codeforces.com

解法

n=1でもa=0またはa=15のときは増減が分かることに注意して解く。

感想

UPをuPとtypoして落としてしまったので猛省。

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      100000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int a[100];

int main(){
    cin >> n;
    rep(i,n) cin >> a[i];
    if(n == 1){
        if(a[0] == 0){
            cout << "UP" << endl;
        } else if(a[0] == 15){
            cout << "DOWN" << endl;
        } else{
            cout << -1 << endl;
        }
        return 0;
    }
    bool up = false;
    if(a[n-2] < a[n-1]) up = true;
    if(up){
        if(a[n-1] != 15){
            cout << "UP" << endl;
        } else{
            cout << "DOWN" << endl;
        }
    } else{
        if(a[n-1] != 0){
            cout << "DOWN" << endl;
        } else{
            cout << "UP" << endl;
        }
    }
}

B. Anatoly and Cockroaches

問題文

codeforces.com

解法

目的の文字列の先頭がrの場合とbの場合を試す。
aiのiの偶奇それぞれにおいて本来あるべき文字と異なる文字の数を数え、その最大値を求めればよい。（swapで両方減らせるから）

感想

swapは隣り合うものだけ許されてるのだと勘違いして1WAしたので反省。（この勘違い、たまにする）

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      100000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
string str;

int main(){
    cin >> n;
    cin >> str;
    int ans = 0;
    int a1 = 0, a2 = 0;
    string s = str;
    rep(i,n){
        if(i%2){
            if(s[i]!='r'){
                a1++;
            }
        } else{
            if(s[i]!='b'){
                a2++;
            }
        }
    }
    ans = max(a1,a2);
    int cnt = 0;
    s = str;
    a1 = 0; a2 = 0;
    rep(i,n){
        if(i%2){
            if(s[i]!='b'){
                a1++;
            }
        } else{
            if(s[i]!='r'){
                a2++;
            }
        }
    }
    cnt = max(a1,a2);
    cout << min(ans,cnt);

}

C. Efim and Strange Grade

問題文

codeforces.com

解法

小数点第一位から順に5以上の数がないかどうかチェックしていき、もし存在したらそこから大きい桁に許されているだけ繰り上げていけばよい。
9のときに繰り上がりがきたら四捨五入しないで繰り上がるということや、9.9のようなときに新たな桁が現れること、整数になることもあるということに気を付ける。

感想

やるだけ。

コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      100000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n, t;
string str;
char input[200001];

int main(){
    cin >> n >> t;
    scanf("%s",input);
    str = input;
    string tmp = "0";
    str = tmp+str;
    bool st = false;
    bool up = false;
    bool in = false;
    int en = str.size();
    for(int i = 1; i < str.size(); i++){
        if(!st){
            if(str[i] != '.'){
                continue;
            }
            st = true;
            continue;
        }
        if(str[i]-'0' >= 5){
            up = true;
            int j = i;
            while(str[j]-'0'>=5 && t > 0){
                en = j;
                t--;
                if(str[j-1] == '.'){
                    in = true;
                    str[j-2]++;
                    j -= 2;
                    t = 0;
                } else{
                    str[j-1]++;
                    j -= 1;
                }
                while(str[j] > '9'){
                    str[j] = '0';
                    str[j-1]++;
                    j--;
                }
            }
            break;
        }
    }
    if(!st){
        rep(i,str.size()){
            if(i == 0) continue;
            printf("%c",str[i]);
        }
        return 0;
    }
    rep(i,str.size()){
        if(i == 0 && str[0] == '0'){
            continue;
        }
        if(i == en){
            break;
        }
        if(str[i] == '.' && in == true){
            break;
        }
        printf("%c",str[i]);
    }
    printf("\n");
}

D.

問題文

解法

感想

幻の問題。不可能問題らしい。
これに時間をずっと使っていたのでE解けなくてつらい（解けるとは言ってない）。

コード

E. Sasha and Array

問題文

codeforces.com

解法

フィボナッチ数の第n項は行列累乗で求まるので、スターリースカイツリーに行列を乗せれば解ける。

感想

解法自体は思いつくのは一瞬だけどコンテスト中には時間がなすぎた。
今度通す。

コード