AtCoder beginner Contest 172

A - Calc

PYthon

A = int(input())
print(A+A**2+A**3)

B - Minor Change

PYthon

S = input()
T = input()

c=0
for i in range(len(S)):
    if S[i] != T[i]:
        c+=1

print(c)

C - Tsundoku

• 一番最初に考えるのが、貪欲法のAとBの一番上の本の読書時間を比較し小さい方を計測していく。

しかし、
4 3 200
80 1 1 1
70 70 70
みたいな入力だとWAになります。

• 累積和を使用します。
• しかし、O(N*Q)では間に合いません。
• O(N * NlogM)にするために累積和と二分探索を使用します。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_N 200001
#define MAX_M 200001

int N, M;
ll K = 0;
int res = 0;

ll A[MAX_N];
ll B[MAX_M];

int main(int argc, const char * argv[]) {

    cin >> N >> M >> K;

    rep(i, N){
        int a;
        cin >> a;
        A[i+1] = A[i] + a;
    }

    rep(i, M){
        int b;
        cin >> b;
        B[i+1] = B[i] + b;
    }

    for(int i=0; i<N+1; i++){
        int l = 0;
        int r = M+1;
        while(r-l > 1){
            int mid = (l+r) / 2;
            if(B[mid]<=K-A[i]) l=mid;
            else r=mid;
        }

        if(A[i]+B[l]<=K) res = max(res, i + l);
    }

    cout << res << endl;

    return 0;
}