AtCoder Beginner Contest 193

A - Discount

O(1)
*100した際に誤差出るかなって一瞬考えました。
A問題だし２桁なら大丈夫かと思い提出。

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    double A, B;
    cin >> A >> B;
    double res = B / A * 100;
 
    cout << fixed_setprecision(6) << 100.0 - res << endl;
 
    return 0;
}

B - Play Snuke

O(N)
0.5スタート１.0分事に１つ在庫が減る。
在庫数から到着時間を引いて、X[i] - A[i] > 0 なら商品を購入できる。
その最小値を取得。
ないなら-1。

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    int n;
    cin >> n;
 
    vector<int> A(n), P(n), X(n);
    rep(i, n) cin >> A[i] >> P[i] >> X[i];
 
    int res = 1e9+7;
    rep(i, n){
        if(X[i] - A[i] > 0) res = min(res, P[i]);
    }
    
    if(res == 1e9+7) cout<< "-1" << endl;
    else  cout<< res << endl;
 
    return 0;
}

C - Unexpressed

o(N)
この問題の意図は10^10の配列を用意できない所、Nの制約が大きい事だと思います。
上記に気づくと圧縮系の問題だと分かります。

10^10の配列ではなく何かしらのデータ構造に追加していく事になります。
正解はsetを使用する事です。
コンテストではvectorでもできるかなって思ってvectorを試しました。

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    ll N;
    cin >> N;
 
    vector<ll> t;
    for(ll i=2; i*i<=N; i++){
        for(ll j=i; j*i<=N; j*=i){
            if(find(t.begin(), t.end(), j*i) == t.end()) t.push_back(j*i);
        }
    }
 
    cout << N - t.size() << endl;
    return 0;
}

D - Poker

O(N)
数学の確率の問題です。
問題の系統としては確率、実装問題です。

Deckに1~9事の数字をk枚数ほど用意してます。
２人のプレイヤーに配ったカードをDeckから引きます。
後はスコアを計測し勝ったパターンをカウント、最後に#の２枚を使用した全ての組み合わせで割ります。

コンテスト中は「D[i] * D[j]」を「D[i]」にて考えてました。
完全な数学力のなさが出ました。

python

import math
import heapq
import itertools
from functools import reduce

def score_total(S):
    res = 0
    for i in range(1, 10):
        cnt = S.count(str(i))
        res += i * (10 ** cnt)
    return res

# main
def main():
    k = int(input())
    S = str(input())[0:4]
    T = str(input())[0:4]

    D = [k] * 10
    D[0] = 0
    for i in range(0, len(S)):
        D[int(S[i])] -= 1
    for i in range(0, len(T)):
        D[int(T[i])] -= 1

    res = 0
    for i in range(1, 10):
        if D[i] == 0:
            continue
        for j in range(1, 10):
            if i == j or D[j] == 0:
                continue
            if score_total(S+str(i)) > score_total(T+str(j)):
                res += D[i] * D[j]

    for i in range(1, 10):
        if D[i] < 2:
            continue
        if score_total(S+str(i)) > score_total(T+str(i)):
            res += D[i] * (D[i]-1)

    print(res / ((9*k-8) * (9*k-9)))
        

# エントリポイント
if __name__ == '__main__':
    main()

感想

灰色diffが解けないことはなくなりました。
しかし茶色diff, 緑diffが解けません。
勉強の仕方を模索していきたいです。