ABC457の記録

AtCoderBeginnerContest457の感想と自分が解いたところまでの解説を書いていきます
今回はA,B,C,DをC++,をA,Bをpython,A,Bをrustで解きます
AtCoder Beginner Contest 457

1.感想

A問題
やるだけだね
B問題
やるだけだね
C問題
累積和だね
D問題
二分探索だね
E問題
F問題
G問題

2.結果

-4

3.解説

A問題Array

入力してA[x]を出力する

C++での例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, X;
    cin >> N;
    vector<int> A(N);
    for (int& i : A) cin >> i;
    cin >> X;
    cout << A[X-1] << endl;
}

pythonでの例

N = int(input())
A = list(map(int, input().split()))
X = int(input())
print(A[X-1])

rustでの例

use proconio::input;

fn main(){
    input!{
        n: usize,
        a: [usize; n],
        x: usize,
    }

    println!("{}", a[x-1]);
}

B問題Arrays

2次元配列を作ってA[x][y]を出力
C++の場合は長さを入力してからresize
pythonの場合はlist(map(int, input().split()))でyは1indexedにしたほうがいいかも

C++での例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<vector<int>> A(N);
    for (int i = 0; i < N; i++){
        int l;
        cin >> l;
        A[i].resize(l);
        for (int& j : A[i]) cin >> j;
    }

    int X, Y;
    cin >> X >> Y;
    cout << A[X-1][Y-1] << endl;
}

pythonでの例

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
X, Y = map(int, input().split())
print(A[X-1][Y])

rustでの例

use proconio::input;

fn main(){
    input!{
        n: usize,
    }
    
    let mut a = Vec::with_capacity(n);
    for _ in 0..n{
        input!{
            l: usize,
            v: [usize; l],
        }
        a.push(v);
    }

    input!{
        x: usize,
        y: usize,
    }

    println!("{}", a[x-1][y-1]);
}

C問題Long Sequence

累積和からの二分探索

C++での例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int N;
    ll K;
    cin >> N >> K;
    vector<int> L(N);
    vector<vector<int>> A(N);
    for (int i = 0; i < N; i++){
        cin >> L[i];
        A[i].resize(L[i]);
        for (int& j : A[i]) cin >> j;
    }
    vector<ll> C(N), S(N);
    for (ll& i : C) cin >> i;
    for (int i = 0; i < N; i++) S[i] = S[max(0, i-1)]+C[i]*L[i];

    auto it = lower_bound(S.begin(), S.end(), K)-S.begin();
    int prev = (it == 0? 0: S[it-1]);
    int pos = (K-prev-1)%L[it];
    cout << A[it][pos] << endl;
}

D問題Raise Minimum

二分探索をする

C++での例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1ll<<60;

int main(){
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N);
    for (ll& i : A) cin >> i;

    auto check = [&](ll x){
        ll n = 0;
        for (int i = 0; i < N; i++) if (A[i] < x){
            n += (x-A[i]+i)/(i+1);
            if (n > K) return false;
        }
        return true;
    };

    ll lo = 0, hi = INF;
    while (hi-lo > 1){
        ll mid = (lo+hi)/2;
        if (check(mid)) lo = mid;
        else hi = mid;
    }

    cout << lo << endl;
}