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; }
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; }
標準ライブラリ一括インクルード
#include <bits/stdc++.h>
ABC050_A
文字列を分割して数値にする問題
#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))