Atcorder 茶色問題集 part1

これから

茶色の問題が解けなくて、レートに伸び悩んでいたので茶色の問題一掃します。
問題傾向を分析してみる。

二分探索＆関数設定　問題

ABC146 C問題
https://atcoder.jp/contests/abc146/tasks/abc146_c

#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    ll a,b,x; cin >> a >> b >> x;
    ll left=0;//条件満たす！
    ll right=1e9+1;//条件満たせてない！

    //keta(mid)
    auto keta=[&](ll mid){
        int res=0;
        while(mid){
            mid/=10;
            res++;
        }
        return res;
    };

    //f(mid)
    auto f=[&](ll mid){
        return a*mid+b*keta(mid);
    };

    //二分探索
    while(right-left>1){
        ll mid=(right+left)/2;
        if(f(mid)<=x) left=mid;
        else right=mid;
    }
    cout << left;
}

関数設定問題（等差数列）

ARC099 C問題
https://atcoder.jp/contests/arc099/tasks/arc099_a

#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    int N,K; cin >> N >> K;
    vector <int> A(N);
    rep(i,N) cin >> A[i];

    //等差数列の方程式
    auto f=[&](int x){//xは項数
        return 1+(x-1)*(K-1);
    };

    int ans=0;
    int x=1;//初項
    while(1){
        if(f(x)>=N) break;//末項超えたら終了
        ans++;
        x++;
    }
    cout << ans;
}

文字列操作問題

AGC006 A問題
https://atcoder.jp/contests/agc006/tasks/agc006_a

#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    int N; cin >> N;
    string S; cin >> S;
    string T; cin >> T;
    ll ans=0;

    rep(i,N+1){
        if(S.substr(i,N-i)==T.substr(0,N-i)){ 
        //文字列.substr(開始位置, 取り出す長さ)
            ans=i+N;
            break;
        }
    }
    cout << ans;
}