読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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

ABC024_B

ドアの合計の開いた時間を求める問題
f:id:umashika5555:20170301044851p:plain

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = (int)1e5;
int main()
{
    int n,t,a[MAX_N];
    cin>>n>>t;
    for(int i=0;i<n;i++)cin>>a[i];
    int res=t;//最後に開く分
    for(int i=1;i<n;i++){
        res += min(t,a[i]-a[i-1]);
    }
    cout<<res<<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;
}

便利ワザ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とか与えられるとキツイ.
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;
}