Codeforces Round #372 (Div. 2)

2回目のCodeforces

A問題

http://codeforces.com/contest/716/problem/A

入力の間隔がcを超えたらリセット、そうでなければインクリメントという感じで数えていく

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)

int main(void) {
    int n, c, ans, t, before;
    cin >> n >> c;
    ans = 0;
    before = 0;
    rep(i, n) {
        cin >> t;
        if(t - before > c) ans = 1;
        else ans++;
        before = t;
    }
    cout << ans << endl;
}

B問題

http://codeforces.com/contest/716/problem/B

入力文字列の長さ26の部分列がA〜Zを重複なく含むようにする。

長さ26の部分列を全て見て、2回以上出現するアルファベットがなければいい感じに埋めてつくれる。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)

int main(void) {
    string S;
    cin >> S;
    bool none = true;

    if(S.size() < 26) {
        cout << -1 << endl;
        return 0;
    }

    char list[26];
    rep(i, S.size()-25) {
        rep(j, 26) list[j] = 0;
        for(int j=i; j<i+26; ++j) {
            list[S[j]-'A']++;
        }
        bool flag = true;
        rep(j, 26) {
            if(list[j] > 1) flag = false;
        }
        if(flag) {
            int k = 0;
            for(int j=0; j<S.size(); ++j) {
                if(j >= i && j<i+26) {
                    if(S[j] == '?') {
                        for(; k<26; ++k) {
                            if(list[k] == 0) {
                                char c = 'A'+k;
                                cout << c;
                                list[k] = 1;
                                break;
                            }
                        }
                    } else {
                        cout << S[j];
                    }
                }
                else {
                    if(S[j] == '?') {
                        cout << 'A';
                    } else {
                        cout << S[j];
                    }
                }
            }
            cout << endl;
            none = false;
            break;
        }
    }
    if(none) cout << -1 << endl;
}

C問題

http://codeforces.com/contest/716/problem/C

変なルールに従ってレベルアップするために何回ボタンを押せばいいか。

今のレベルと次のレベルの公倍数の平方になるまでボタンを押せばレベルアップできるので、各レベルの回数はO(1)で求まる。 全部用意しておいて入力に従って表示するだけ。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i=0; i<(int)(n); ++i)

ll dp[100001];

int main(void) {
    dp[1] = 2;
    for(ll k=2; k<=100000; ++k) {
        dp[k] = (k+1)*(k+1)*k - (k-1);
    }
    int n;
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cout << dp[i] << endl;
    }
}

D問題, E問題

Dは?を1としてdijkstraで最短路を求めてから、最短路がLになるよう増やせばいいのかなと思っていろいろ試したがそれが最短路ではなくなってしまう場合を考慮してなくて時間内に解けず。 Eは開いてすらいない。

まだsystem test通っていないのでACかは不明。