高速Fibonacci数の計算
これを使ってFibonacci数の計算を高速に行うことができる.
(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count);偶数だったら2回分の変換を1回で (fib-iter a b (+ (* p p) (* q q));p' (+ (* q q) (* 2 p q));q' (/ count 2))) (else;奇数だったら素直に1回分の変換 (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))
ABC027_B
島の人口を均等に分散すべく橋をかける問題
総人口/島の数で目標値を求め,その状態にしていったときに隣の島に流入、流出(マイナス流入)を加算していく.
#include <bits/stdc++.h> using namespace std; int main() { int n,a[100],total=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; total += a[i]; } if(total%n!=0){ cout<<-1<<endl; }else{ int t = total/n;//目標とする人数 int ans = 0; for(int i=0;i<n-1;i++){ if(a[i]!=t){ a[i+1]+=a[i]-t; ans++; } } cout<<ans<<endl; } return 0; }
ABC032_B
集合setを用いる問題
集合への挿入は
set<string> ss; ss.insert("aaa"); ss.insert("bbb"); ss.insert("aaa"); cout<<(int)ss.size()<<endl;//2
この時(int)でキャストしないと幾つかのテストケースでREをとってしまった.
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) int main() { set<string> ss; string s; int k; cin>>s>>k; REP(i,(int)s.size()-k+1){ ss.insert(s.substr(i,k)); } cout<<(int)ss.size()<<endl; return 0; }
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; }