[AtCoder]AtCoder Beginner Contest 130

はじめに

• AtCoder Beginner Contestの過去問の解法及び提出したソースコードをまとめています。
• 基本的に自分が振り返ることを目的としておりますが、誤りや気になった点、その他質問等もお待ちしておりますので遠慮なくお願いします。

コンテストページ

A問題

題意通りであるため割愛。

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

int main()
{
    int x,a;
    cin >> x >> a;
    cout << ((x < a) ? 0 : 10) << endl;
    return 0;
}

B問題

Lを座標移動距離と考えることができるので、座標移動の合計(=Lの合計)がXを超えない範囲の座標移動回数を求めればよいです。
ソースコードではXを超えるまでLを足し続ける回数を0未満になるまでXからLを引く回数と置き換えています。

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

int main()
{
    int n,x;
    cin >> n >> x;

    int ans = 1;
    for(int i = 0; i < n; i++){
        int l;
        cin >> l;
        if((x -= l) < 0) break;
        ans++;
    }
    
    cout << ans << endl;
    return 0;
}

C問題

長方形の中心を通る線を引くことで必ず長方形を二分割することができるので面積は長方形の面積/2です。
また直線の引き方は基本的に座標(x,y)と長方形の中心を通る直線に定まりますが、その二点が同一である場合のみ分割方法が無数に存在します。

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

int main()
{
    int w,h,x,y;
    cin >> w >> h >> x >> y;
    int ans = (x == w-x && y == h-y) ? 1 : 0;
    cout << setprecision(16) << (double)w*h/2 << " " << ans << endl;
    return 0;
}

D問題

部分列の和は累積和を用いて求めることができますが、それでもそのまま全探索しようとするとO(n^2)で間に合いません。
そこで部分列の左端を固定し、条件を満たす最左の右端を二分探索で求めてそれより右のものの個数を数えていくことでO(NlogN)となります。

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

int main()
{
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n+1);
    vector<ll> sum(n+1, 0);
    for(int i = 0; i < n; i++){
        cin >> a[i+1];
        if(i==0) sum[1] = a[1];
        else sum[i+1] = sum[i] + a[i+1];
    } 

    ll ans = 0;
    for(ll i = 1; i <= n; i++){
        ll l = i-1;
        ll r = n+1;
        while(r-l>1){
            ll x = l + (r-l)/2;
            if(sum[x] - sum[i-1] >= k){
                r = x;
            }
            else l = x;
        }
        ans += n - r + 1;
    }

    cout << ans << endl;
    return 0;
}

E問題(未AC)

まだ解いていません。

F問題(未AC)

まだ解いていません。