A. ABC Preparation, B. Shift only, C - To Infinity, D - Powerful Discount Tickets

2021年2月10日　くじかつ
精進問題

A - ABC Preparation

O(1)

python

a, b, c, d = list(map(int, input().split()))

print(min(min(a, b), min(c, d)))

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 argc, const char * argv[]) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << min(min(a, b), min(c, d)) << endl;

    return 0;
}

B - Shift only

O(N*loop)

python

N = int(input())
A = list(map(int, input().split()))
ans=0
isLoop=True
while(isLoop):
    c=0
    for i in range(0, N):
        if A[i]%2==0:
            c+=1
        else:
            isLoop=False

    if c==N:
        for i in range(0, N):
            A[i] = A[i]/2

        ans+=1

print(ans)

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);
    rep(i, n) cin >> A[i];

    int cnt=0;
    int loop=true;
    while(loop){
        rep(i, n){
            if(A[i] % 2 == 0){
                A[i] = A[i] / 2;
            }else{
                loop = false;
                break;
            }
        }
        if(loop) cnt++;
    }
    cout << cnt << endl;

    return 0;
}

C - To Infinity

O(N)
２を5000兆倍した際、オーバフローします。
左端から右へ判定し、最初に見つかった1以外の数字が答えになります。
例外としてKまで全て１だった際に１になります。

python

N = str(input())
K = int(input())

K = K - 1

value = 1
for i in range(0, len(N)):
    if N[i] != '1':
        value = int(N[i])
        break
    if K == i and N[i] == '1':
        break

print(value)

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() {
    string s;
    ll k;
    cin >> s >> k;

    int v=1;
    k--;
    rep(i, s.length()){
        if(s[i] != '1'){
            v = s[i] - '0';
            break;
        }
        if(k == i && s[i] == '1'){
            v = 1;
            break;
        }
    }
    cout << v << endl;

    return 0;
}

D - Powerful Discount Tickets

O(M log N)
最初にMAX値のINDEXを探して２で割り、二分探索で要素を配列へ戻すという処理を行いました。
TLEでした。
初めてプライオリティキューを使いました。

python

import heapq

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))

heapq.heapify(A)
for i in range(0, M):
    a = heapq.heappop(A)
    a = a // 2 + (a % 2)
    heapq.heappush(A, a)

print(sum(A)*-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, m;
    cin >> n >> m;

    priority_queue<int> que;
    rep(i, n){
        int a;
        cin >> a;
        que.push(a);
    }

    rep(i, m){
        int a = que.top();
        que.pop();
        que.push(a/2);
    }

    ll total=0;
    rep(i, n){
        total += que.top();
        que.pop();
    }
    total = total;
    cout << total << endl;

    return 0;
}