高速Fibonacci数の計算

{ \displaystyle
T_{pq}は(a,b)をa\leftarrow bq+aq+apとb\leftarrow bp+aqの写像とする.\\
T_{pq}を2回作用させると同じ形式のT_{p'q'}を1回作用させたときと同じ効果を及ぼすことの証明\\

T_{pq}を(a,b)に1回作用させると\\
(a,b)\rightarrow(bq+aq+ap,bp+aq)\\
T_{pq}を(bq+aq+ap,bp+aq)に作用させると\\
(bq+aq+ap,bp+aq)\rightarrow(b(q^{2}+2pq)+a(q^2+2pq)+a(q^2+p^2),\ b(p^{2}+q^{2})+a(q^{2}+2pq))\\

よってp'=p^{2}+q^{2}, q' = q^{2}+2pqとすればT_{pq}を2回作用させた変換と同等の変換が得られる.
}

これを使って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

島の人口を均等に分散すべく橋をかける問題
f:id:umashika5555:20170301075423p:plain
総人口/島の数で目標値を求め,その状態にしていったときに隣の島に流入、流出(マイナス流入)を加算していく.

#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;
}

ABC033_B

pairについて
この問題では結局使わなかったけど調べたので書いとく.

//市の名前と人口を入力
string s;
int x;
vector<pair<string, int> > city;
for(int i=0;i<n;i++){
    cin>>s>>x;
    city.push_back(make_pair(s,x));
}
vector<pair<string, int>> city;
int>>はint> >

と書かないとcompilation errorを吐く.

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;
}

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とか与えられるとキツイ.
f:id:umashika5555:20170226065442p:plain
上図で赤は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"

f:id:umashika5555:20170225200150p:plain

#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