ABC035_B

文字列のカウント

string str = "a1a2a3a4a5a6";
int cnt = count(str.begin(),str.end(),'a');//6

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

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main()
{
    string s;
    int t;//t==1 max, t==2 min
    int x=0,y=0;
    int ans=0;
    cin>>s>>t;
    int cnt = count(s.begin(),s.end(),'?');
    for(int i=0;i<s.size();i++){
        switch(s[i]){
            case 'U':y++;break;
            case 'D':y--;break;
            case 'L':x--;break;
            case 'R':x++;break;
        }
    }
    if(t==1){//max
        ans = abs(x)+abs(y)+cnt;
    }else{//min
        for(int i=0;i<cnt;i++){
            if(!(x==0 && y==0)){//原点以外
                if(x>0)x--;
                else if(x<0)x++;
                else if(y>0)y--;
                else if(y<0)y++;
            }else{//原点
                x++;
            }
        }
        ans = abs(x)+abs(y);
    }
    cout<<ans<<endl;
    return 0;
}

便利ワザ3

早くなる.

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

ABC039_B

文字列を右90度に回転させる問題

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 50;
int main()
{
    char a[MAX_N][MAX_N+1];
    char b[MAX_N][MAX_N+1];
    int n;
    cin>>n;
    //input
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    //回転
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            b[j][n-i-1] = a[i][j];
        }
    }
    //output
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<b[i][j];
        }
        cout<<endl;
    }
    return 0;
}

右180度の場合
(i)操作を2回繰り返す
(ii)

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            b[n-i-1][n-j-1] = a[i][j];
        }
    }

右270度の場合
(i)操作を3回繰り返す
(ii)

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            b[n-j-1][i] = a[i][j];
        }
    }

ABC048_B

a以上b以下の数字のうちxで割り切れるものの数を答える.
for文でループで解くのは一重ループだとしてもb = 10^18とか与えられるとキツイ.

上図で赤はxで割り切れる数
上段 = 中段 - 下段で考えた.
aがxで割り切れた場合はaの1つ分を足す必要がある.

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

int main()
{
    ll a,b,x;
    cin>>a>>b>>x;
    cout<<b/x - a/x + !(a%x) <<endl;
    return 0;
}

ABC051_B

counter変数の加算で右辺に条件式を持ってきてもよいことがわかった.
ex)

int cnt = 0;
cnt += 0<=k && k<=10;
//kが0<=k<=10ならばTrue=1が加算され,そうでなければFalse=0が加算される.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int k,s;
    int x,y,z;
    int cnt = 0;
    cin>>k>>s;
    for(int x=0;x<=k;x++){
        for(int y=0;y<=k;y++){
            z = s-x-y;
            cnt += 0<=z && z<=k;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

便利ワザ2

定数

const int N = 1000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 31;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MAX_INT = (1 << 31) - 1;
const double eps = 1e-6;
const double pi = atan2(0, -1);
const double pi2 = atan(1) * 4;

ABC053_B

文字列反転の問題
文字列反転は次のようにする.

string str = "abcde";
reverse(str.begin(),str.end());//"edcba"

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    
    int start=0,end=0;
    for(int i=0;i<str.size();i++){
        start++;
        if(str[i]=='A')break;
    }

    reverse(str.begin(),str.end());
    for(int i=0;i<str.size();i++){
        end++;
        if(str[i]=='Z')break;
    }
    end = str.size()-end+1;
    cout<<end-start+1<<endl;
    return 0;
}
    

ABC055_B

factorialを求める問題
大きい数値はll型を使う.
int型(4byte)の範囲は20億くらいを目安にする.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (ll)1e9+7
#define MAX(X,Y) ((X)>(Y)?(X):(Y))
#define MIN(X,Y) ((X)<(Y)?(X):(Y))

int fact(int x)
{
    ll res = 1;
    for(int i=1;i<=x;i++){
        res *= i;
        res %= MOD;
    }
    return res;
}

int main()
{
    int x;
    cin>>x;
    cout<<fact(x)<<endl;
    return 0;
}

ABC025_A

文字列についての問題
文字列の要素1つはchar型だと知った.
ex)

string str = "abcde";
cout<<typeid(str[1]).name()<<endl;
//c

よってsubstr(ポインタの位置,そこから何文字分?)を使って部分文字列を使った.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int n;
    vector<string> ss;
    cin>>s>>n;
    sort(s.begin(),s.end());
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            string new_ss = s.substr(i,1)+s.substr(j,1);
            ss.push_back(new_ss);        
        }
    }
    cout<<ss[n-1]<<endl;
    
    return 0;
    
}

便利ワザ

入力に対して出力を行うのをプログラムがやってくれる.
mainの後ろに置く.

//	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	#endif

ABC046_A

種類を数える問題
集合(set)を用いる

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	set<int> s;
	cin>>a>>b>>c;
	s.insert(a);//集合sにaを挿入
	s.insert(b);
	s.insert(c);
	cout<<s.size()<<'\n';
	return 0;

標準ライブラリ一括インクルード

#include <bits/stdc++.h>

ABC050_A

文字列を分割して数値にする問題

C++におけるsplit関数の実装
qiita.com

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int stoi(std::string str){
  int ret;
  std::stringstream ss;
  ss<<str;
  ss>>ret;
  return ret;
}

vector<string> split(const string &s, char delim) {
  /*
    文字列分割してvector<string>を返す
   */
    vector<string> elems;
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim)) {
    if (!item.empty()) {
            elems.push_back(item);
        }
    }
    return elems;
}


int main()
{
  string Str;
  vector<string> ans;
  int a,b;
  getline(cin, Str);//空白ごと1行入力
  ans = split(Str,' ');
  a = stoi(ans[0]);
  b = stoi(ans[2]);
  if(ans[1]=="+")
    printf("%d\n",a+b);
  else
    printf("%d\n",a-b);
  return 0;
}

空白を含めて一行入力したい場合は

getline(cin,str);

ABC051_A

文字列の置換
www.geocities.jp

#include<iostream>
#include<string>
using namespace std;

//  文字列を置換する
std::string Replace(std::string String, std::string From, std::string To )
{
    std::string::size_type  Pos( String.find( From ) );

    while( Pos != std::string::npos )
    {
        String.replace( Pos, From.length(), To );
        Pos = String.find( From, Pos + To.length() );//さっきまで探してた位置以降のFromを探す
    }

    return String;
}

int main()
{
    string s;
    cin >> s;
    s = Replace(s,","," ");
    cout<<s<<endl;
    return 0;
}

Newton法で平方根を求める

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (imporve guess x)
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))