AOJ-ICPC 「王様の視察」

問題
King's Inspection | Aizu Online Judge

解説
まずはアルファベットをずらしていくため、順番通りに並べた配列を用意します。
alp[]={'a' , 'b'..'z','A'....'Y','Z'} のような配列です。

また、「いくつずらすか」を保存した配列は何周もする可能性があるので、今何番目を見ているかを保存するv_countも用意しました。

最後に、今ずらそうとしている文字が配列alp上で何番目に当たるか（つまりずらし始める初期位置）を知らないといけないので、これをアスキーコードを利用しposという変数で取得します。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
 
using namespace std;
 
int main(){
    int n;
    vector<char> alp;
    rep(i,0,26)alp.pb('a'+i);
    rep(i,0,26)alp.pb('A'+i);
    //alp[]={'a','b'.......'Y','Z'}
    while(cin>>n){
        if(n==0)break;
        vector<int> v(n);
        rep(i,0,n)cin>>v[i];
        string s;
        cin>>s;
         
        int v_count=0; 
        //v_countはずらす回数を表す数字の配列の添字
        //下に出てくるposは'a'-'Z'までを格納した配列alpの添字
         
        rep(i,0,s.size()){
            if('a'<=s[i]&&s[i]<='z'){
                int pos=s[i]-'a';  //小文字の時、'a'との差がalpの添字
            }else {
                int pos=s[i]-'A'+26; //大文字の時、'A'との差に26を足せばalpの添字
            }
            //いざ、文字をずらす
            rep(j,0,v[v_count]){
                pos--;
                if(pos==-1)pos=51;
            }
            cout<<alp[pos]; //pos番目のalpを出力
            v_count++;
            if(v_count==n)v_count=0;
        }
        cout<<endl;
    }
     
    return 0;
}

AOJ-ICPC 「かけざん」

問題
Kakezan | Aizu Online Judge

解説
値は文字列で管理するのが良いですね。
文字列長より１少ない数だけforを回して、文字列をstring::substr(開始位置, 何文字切り抜くか)で分割の仕方を全探索し、結果が最大になったものを次に持ち越す感じです。

文字列から数字への変換は、std::stoiやstd::stolなどが標準で用意されていますが、たまに謎のエラーに見舞われるので、自作したSTOLを使っています。

無理なら-1の判定を結構雑に書いたんですが、まあ通ったので良しとします。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
 
using namespace std;
 
ll STOL(string s){
    ll ret=0;
    rep(i,0,s.size()){
        ret+=(s[s.size()-i-1]-'0')*pow(10,i);
    }
    return ret;
}
 
int main(){
    int n;
    cin>>n;
    rep(i,0,n){
        int ans=0;
        int x; cin>>x;
        while(1){
            string s=to_string(x);
            if(s.size()==1){ //１文字になれば終了
              cout<<ans<<endl;
              break;
            }
            ll max_num=0;
            rep(i,1,s.size()){
                //文字列の分割方法を全探索し、最大値を探します。
                max_num=max(max_num,STOL(s.substr(0,i))*STOL(s.substr(i,s.size()-i))); 
            }
            //最大値を次のループに持ち越します
            x=max_num;
            ans++;
            //1000000回操作しても１文字にならなければまあ無理そうなのでその時点で切ります。これで通ったので良いのです（）。
            if(ans==1000000){
                cout<<-1<<endl;
                break;
            }
        }
    }
     
    return 0;
}

ACM-ICPC 「ICPCの順位づけ」 解説

問題
ICPC Ranking | Aizu Online Judge

解説
少し考えることが多いのですが、とりあえず
・tim: 各チームの所要時間を格納する１次元int配列
・solve :各チームの各問題の解けたかどうかを格納する２次元bool配列
　→solve[チーム番号][問題番号]=true or false で管理
・WA: 各チームの各問題を何回間違えたかを格納する２次元int配列

は要りそうなので、これらを使ってうまくやる方針で解きました。
solveで問題の解答状況を保存した後、各チームが合計で何問解けたかを算出します。
この時に、ついでに間違えた数＊２０のペナルティも扱います。

必要な数字を揃えれば、あとはソートをすれば終わりです。
pairに入れることで、first要素を優先してソートし、firstが同じ時はsecondで判定します。今回はこれを入れ子にすることで３つの値を扱います。

また、問題数は多い順に順位が高く、解答時間は短いほうが良いです。つまり、ソートするにしても「昇順」か「降順」かが異なります。今回はまとめて昇順ソートするので、降順にしたいものについてはマイナスをかけることで対処しました。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
//typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

int main(){
    int M,T,PP,R;
    while(cin>>M>>T>>PP>>R && M){
        vector<int> tim(T,0); //各チームの所用時間
        vector<vector<bool>> solve(T,vector<bool>(PP,false)); //チームごとに各問題が解けたかどうかをboolで
        vector<vector<int>> WA(T,vector<int>(PP,0)); //チームごとに各問題を何回間違えたか
    
        rep(i,0,R){
            int m,t,p,r;
            cin>>m>>t>>p>>r;
            t--; p--; 
            if(r==0){ //正解したら、その時のmを足してとsolveをtrueに
                solve[t][p]=true;  
                tim[t]+=m;   
            }
            else WA[t][p]++; //間違えたらWAを増やす
        }
    
        vector<int> solve_count(T,0); //チームごとに結局何問正解できたか
        //２重forで数えます
        rep(i,0,T){
            rep(j,0,PP){
                if(solve[i][j]){
                    solve_count[i]++;
                    tim[i]+=WA[i][j]*20;   
                }
            }
        }
        vector<pair<int,pair<int,int>>> rank; //いよいよソートします。この配列は３つの値を持ち、<問題数、時間、チーム番号>で格納。
        /*ソート自体は昇順で行いますが、問題数は降順、時間は昇順、チーム番号は降順でソートしたいので、
        降順にしたいものにはマイナスをつけることで対処します。これにより、元の値が大きいほど値が小さくなるのでうまくいきます。
        */
        rep(i,0,T){
            rank.pb(MP(-solve_count[i],MP(tim[i],-(i+1))));
        }
        Sort(rank);
        
        /*rep(i,0,T){
            cout<<rank[i].fi<<" "<<rank[i].se.fi<<" "<<-rank[i].se.se<<endl;
        }*/
        
        //最後に出力です。出力するものはrank[].se.seだけですが、マイナスをつけて格納しているのでマイナスをつけて出力します。
        rep(i,0,T){
            if(i)cout<<",";
            cout<<-rank[i].se.se;
            while(i+1<T && rank[i].fi==rank[i+1].fi && rank[i].se.fi==rank[i+1].se.fi){
                i++;
                cout<<"=";
                cout<<-rank[i].se.se;
            }
        }
        cout<<endl;
    }
    
    return 0;
}

ACM-ICPC 「ICPC Score Totalizer Software」 解説

問題
ICPC Score Totalizer Software | Aizu Online Judge
n個の数字が入力されるので、その中から最大値と最小値を除いたものの中での平均を求めよう。

解説
n個の整数を全て足し合わせたsum、最小値を格納するmi、最大値を格納するmaを用意し、処理をします。
このとき、平均を求めるにあたり使用する合計値はsum-ma-miです。また、個数はn-2個です。
これらを元に、実装すれば正解になります。

#include <bits/stdc++.h>
 #define INF (int)1e9
using namespace std;

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        int mi=INF,ma=0;
        int sum=0;
        for(int i=0;i<n;i++){
            int x; cin>>x;
            sum+=x;
            mi=min(mi,x);
            ma=max(ma,x);
        }
        cout<<(sum-ma-mi)/(n-2)<<endl;
    }
    
    return 0;
}

AOJ Numeral System 解説

問題
Numeral System | Aizu Online Judge

解説

方針としては、文字列を読み込んで、数字に直し、足し算した後で再びMCXI文字列に直します。

まずは、読み込んだ文字列をどう処理するかを考えます。
まず、1000,100,10,1の時は、m,c,x,i の文字が単体で置かれます。
2000や500のような時は、2mや5cのように数字が文字の左側につきます。

この法則から、文字列を読み込んで前から順番に見ていく中で、i番目が数字であれば、その次に必ず文字が来ることが分かります。つまり、i+1番目が必ず配列外参照になりません。
よって、数字が来れば、その次の文字も見て、掛け算で値を取り出すことができます。この時、i++として追加でiを進めることで、i+1番目の文字を再度見ないようにします。

i番目が文字の時、それは単体で存在していることがわかります。もし左側に数字があれば、それは前述の処理で飛ばされているはずです。
この時は、普通に文字を数字に変換します。

次に足し算をした後にMCXI文字列に戻す作業を考えます。
ここでも、m,c,x,iに対応した位を見て、「0」,「1」,「それ以外」の３つのパターンで場合分けします。
1000の位を見たければ1000で割るだけで取り出せることに注意しつつ、０なら何もなし、１ならそのまま文字を出力、それ以外なら数字と文字を続けて出力します。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)

using namespace std;

//文字を数字に変換する関数
int chan(char c){
    if(c=='m')return 1000;
    if(c=='c')return 100;
    if(c=='x')return 10;
    if(c=='i')return 1;
}
 
int main(){
    int n;
    cin>>n;
    rep(p,0,n){
        int num[2]={0};  //num[0],num[1]は１つ目、２つ目の文字列の値を表す
        rep(j,0,2){  //２つの文字列について処理
            string s;
            cin>>s;
            rep(i,0,s.length()){
                if('0'<=s[i] && s[i]<='9'){ //i番目が数字なら、i+1番目をみる
                    num[j]+=(s[i]-'0')*chan(s[i+1]);
                    i++;
                }else { //i番目が文字なら、そのまま数字に
                    num[j]+=chan(s[i]);
                }
            }
        }
        
        int ans=num[0]+num[1];  //足し算する
　　
        //以下が出力部で、各位の値を見て出力を場合分け
        if(ans/1000==1)cout<<'m';
        else if(ans/1000!=0)cout<<ans/1000<<'m';
        ans%=1000;
        
        if(ans/100==1)cout<<'c';
        else if(ans/100!=0)cout<<ans/100<<'c';
        ans%=100;
        
        if(ans/10==1)cout<<'x';
        else if(ans/10!=0)cout<<ans/10<<'x';
        ans%=10;

        if(ans==1)cout<<'i';
        else if(ans!=0)cout<<ans<<'i';
        cout<<endl;
        
    }
    return 0;
}

AOJ Amida, the City of Miracle 解説

問題
Amida, the City of Miracle | Aizu Online Judge

解説
あみだくじの問題です。
あみだくじ系の問題では、最初、i番目には番号iが繋がっていますが、横棒が追加されるたびに繋がる先が入れ替わると考えることができます。

例えば最初、縦棒1 2 3 4 5には番号1 2 3 4 5が繋がっていますが、2と３を繋ぐ横棒が現れた瞬間、番号1 3 2 4 5に繋がることになります。
この方法では、横棒の深さが浅い順に処理する必要がありますが、今回は深さが浅い順に与えられるとは限りません。そこで、一度深さでソートしてから処理を始める必要があります。

このために、vector< pair< int, pair< int,int>>> v；として、pairを入れ子にすることを考えます。１つ目のpairのsecond要素にさらにpairが来ます。
pairはsort()関数でソートしたとき、first要素を優先してソートされます。

これにより、配列の中身は以下のようになります。
v[I].first 階層
v[I].second.first 横棒の始点
v[I].second.second 横棒の終点

入力を受けてソートした後、前から順にans[横棒の始点-1] と　ans[横棒の終点-1] を交換していけば、正解にたどり着けます。
始点と終点は１オリジン、配列の要素は０オリジンであることに注意です。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define Sort(x) sort((x).begin(),(x).end())
 
using namespace std;
 
int main(){
    while(1){
    int n,m,a;
    cin>>n>>m>>a;
    if(n==0&&m==0&&a==0)break;
    vector<int> ans(n);
    rep(i,0,n)ans[i]=i+1; //最初は横棒i は番号i に繋がる（オリジンの違いに注意）
     
    vector<pair<int,pair<int,int>>> v(m);
    rep(i,0,m){
        cin>>v[i].first>>v[i].second.first>>v[i].second.second; //入力
    }
     
    Sort(v); //階層順にソート
    rep(i,0,m){
        swap(ans[v[i].second.first-1],ans[v[i].second.second-1]); //階層の浅い順に繋がる先を交換
    }
    cout<<ans[a-1]<<endl; //a番目の縦棒につながる数字を出力
    }
    return 0;
}

AOJ 列車の編成パート(Organize Your Train part II) 解説

問題
Organize Your Train part II | Aizu Online Judge

解説
文字列を２分割した後は以下の操作ができます。以下、分割した後の２つの文字列をA,Bとおきます。

・A,Bはそれぞれ反転できる。
・文字列を　AB 、またはBA のどちらの順でも連結できる。

これ以外にできる操作はありません。
また、文字列の重複による２重カウントを除くために、集合のsetを使います。setは自由に要素を追加できますが、既に存在する要素を追加しようとしたときは追加されません。
生成された文字列を全てsetに入れた後、setに格納された要素数を見ればそれが答えになります。

また、A,Bを反転するしないかは、反転するを1、反転しないを０とすれば00, 01,10,11の４通りです。これはforで全探索します。

int main(){
    int n;
    cin>>n;
    rep(i,0,n){
        set<string> st;
        string s;
        cin>>s;
        string ls,rs;
        rep(i,0,s.length()){
            ls=s.substr(0,i);
            rs=s.substr(i,s.length()-i);
            rep(j,0,2){
                rep(k,0,2){
                    st.insert(ls+rs);
                    st.insert(rs+ls);
                    reverse(all(ls));
                     
                }
                reverse(all(rs));
            }
        }
         
        cout<<st.size()<<endl;
    }
     
    return 0;
}