AtCoder ABC

ABC154反省会

むっっっず。Not Todayな気持ちです。。。。(アルゴ習得から逃げて灰diff狩りしているので当然の末路でもあるかもです。。。)

CLionで書いているのですが、main()内だけショトカでのコード綺麗にする奴発動させられませんか？

AtCoder Beginner Contest 154 - AtCoder

A

どっちを引くか分岐させましょ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    string S,T;
    int A,B;
    string U;

    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    if ( U== S) A--;
    else B--;

    cout << A << " " << B << endl;


    return 0;
}

B

他の言語にもあるぞってツッコミされそうですが、ストリームに少しづつ流して答えを形成できるのはC++の好きなところです。 文章の中身は読む必要ないので、文字数分だけxを出力しましょう。

提出 #9977323 - AtCoder Beginner Contest 154

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    string S;
    cin >> S;
    REP(i,S.size()) cout << "x";
    cout << endl;

    return 0;
}

C

setを使うと秒殺出来ます。 入力をかたっぱしからinsertしてあげて、set.size()とNが一致するかで答えの出し分けをしましょう。

提出 #9979859 - AtCoder Beginner Contest 154

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    set<int> A;
    int N;
    cin >> N;
    REP(i,N) {
        int a;
        cin >> a;
        A.insert(a);
    }

    if (A.size() != N) {
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << endl;
    return 0;
}

D

期待値の出し方わからなくてググりました。

考えたこと

  • サイコロの配列を、期待値の配列にしてしまえば、後はその区間の期待値の和が最大になる所を選べば良い

  • 期待値を雑に求めようとすると、一回辺りpi回計算が走るので、期待値の配列を雑に作ると間に合わなくなるかも。10^3 * 10^5回for-roop することになりそう

    • 1 <= pi <= 1000なので予め1~1000種類の目のサイコロを一回振ったさいの期待値を配列保存しておこう。

  • 後は配列から読み込んでいくだけなのでO(N)のはず

2WA叩き出して笑顔になりました。笑うしかないです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

double kitaichi(int part) {
    double res = 0;
    FOR(i,1,part+1) {
        res += (double)i * 1/(double)part;
    }
    return res;
}

int main() {
    // 前計算
    vector<double> tbl(1001);
    FOR(i,1,1001) {
        tbl[i] = kitaichi(i);
    }
    int N,K;
    cin >> N >> K;
    vector<int> p(N);
    REP(i,N) cin >> p[i];

    double now_kitai = 0;
    double ans = 0;
    // init
    REP(i,K) now_kitai += tbl[p[i]];
    chmax(ans,now_kitai);
    FOR(i,K,N) {
        now_kitai -= tbl[p[i-K]];
        now_kitai += tbl[p[i]];
        chmax(ans,now_kitai);
    }

    cout << fixed << setprecision(12) << ans << endl;

    return 0;
}

E

んんんわからん！ 桁いっぱいあるので桁DPじゃね？？名前しか知らんけど。

完

学ばないと永遠にAC出来ないのでここいらで学ぼうと思います。

解説ベースでいきます。

桁DP的な考え方(お気持ち)を知っていると解けるかもしれない

けんちょんさんの解説ガン見しながらコードを書いていたら写経ACになりました。(関係ないけどしゃけいってずっと読んでいたけどしゃきょう何ですね・・・)

AtCoder ABC 154 E - Almost Everywhere Zero (500 点) - けんちょんの競プロ精進記録

提出 #10044807 - AtCoder Beginner Contest 154

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}



long long combination(int n, int k){
    static const int maxi = 1e6+1;
    static vector<ll> fac(maxi,0),finv(maxi,0),inv(maxi,0);
    static const int mod = 1e9+7;
    // キャッシュされてない場合COMinit()と同様のことをする。
    if (fac[0]==0) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < maxi; i++){
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = mod - inv[mod%i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}


string N;
ll K;

// i桁目まで見たとして、残りがk回0以外を入れられていて、未満確定ならsmallerはtrueで答えを出す。
ll solve(ll i,ll k,bool smaller) {
    // 途中だがkが0になった。(=残りの桁があっても、0で埋まるので1を返す)
    if (k == 0) return 1;

    // 最後の桁まで走査した(= 最後の桁まで決定した && k != 0 なので 0を返す)
    if ( i == N.size()) return 0;

    // N未満であることが確定しているならば残りの桁は何でも入るので組み合わせを使って返す
    if (smaller) return combination(N.size()-i,k) * (ll)pow((ll)9,(ll)k);

    // まだ未満とは限らない場合

    // 今見ている桁に相当するNの値が0なら先に進む。
    if (N[i] == '0') return solve(i+1,k,false);

    // N[i]が0でない場合、 その桁には0,1,...と入る可能性がある。
    // i桁目に0を入れた場合の個数 (明らかにN以下の値になるためフラグはtrueになる)
    auto zero = solve(i+1,k,true);
    // i桁目に0<k<N[i]を満たす様な値を入れた場合(明らかにN以下の値になるためフラグはtrueになる)
    // N[i] == 1ならmidはないし、N[i] == 3ならmidはN[i] == 1,2のことになるので適宜調整をする。
    auto mid =  solve(i+1,k-1,true) * (N[i]- '1');
    // i桁目にN[i]を入れた場合
    auto last = solve(i+1,k-1,false);

    return zero + mid + last;

}

int main() {
    cin >> N;
    cin >> K;
    cout << solve(0,K, false) << endl;
    return 0;
}

感想

桁DP分からなさすぎて多分またやっても解けないと思う(遠い目)

せめて、smallerの概念くらいは持って帰れる様にしておきたい。

Licensed under CC BY-NC-ND 4.0
© 2017 - 2024 reud.net
Built with Hugo
テーマ Stack は Jimmy によって設計されています。