AtCoder Regular Contest #001

問題A:センター採点

N文字の文字列で一番出現回数が多いものと一番出現回数が少ないものを出力します。文字は'1', '2', '3', '4'の4種類しかありません。max,minを使っても良いですが, max_element, min_elementを使うとちょっとだけコードの見栄えがすっきりします。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main(){
    int N;
    string s;
    cin >> N >> s;

    int f[4] = {0};
    for(int i=0 ; i < N ; i++ ){
        f[s[i] - '1']++;
    }
    cout << *max_element(f,f+4) << " " << *min_element(f,f+4) << endl;
}

問題B:リモコン

リモコンでエアコンの設定温度を±1,±5,±10変更でき, 整数A,B(0 <= A,B <= 40)が与えられるので設定温度を温度Aから温度Bまで変えるときの最小回数を求めます。
幅優先探索で求めることができます。温度が負の数に遷移するときに注意してコードを書きます。別解としてグラフを作ってワーシャルフロイドでも解くことができます。

#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
int a,b;
int d[6] = {1,5,10,-1,-5,-10};
 
int solve(){
    queue<P> q;
    q.push( P(a,0) );
    map<int,bool> m;

    while( !q.empty() ){
        P now = q.front(); q.pop();
        m[now.first] = true;
        if( now.first == b ){
            return now.second;
        }
	
        for(int i=0 ; i < 6 ; i++ ){
            int next = now.first + d[i];
            if( m[next] != true ){
                q.push( P(next,now.second+1) );
            }
        }
    }
    return -1;
}
 
int main(){
    cin >> a >> b;
    cout << solve() << endl;
}

ワーシャルフロイドで解く

#include <iostream>
#include <algorithm>
using namespace std;
 
const int INF = 1e+8;
 
int main(){
    int g[51][51] = {0};
    for(int i=0 ; i < 51 ; i++ ){
        for(int j=0 ; j < 51 ; j++ ){
            if( i == j ){
                g[i][j] = 0;
            }else if( abs(i-j) == 1 || abs(i-j) == 5 || abs(i-j) == 10 ){
                g[i][j] = 1;
            }else{
                g[i][j] = INF;
            }
        }
    }
    for(int i=0 ; i < 51 ; i++ ){
        for(int j=0 ; j < 51 ; j++ ){
            for(int k=0 ; k < 51 ; k++ ){
                g[i][j] = min( g[i][j] , g[i][k] + g[k][j] );
            }
        }
    }
    int a,b;
    cin >> a >> b;
    cout << g[a+10][b+10] << endl;
}

問題C:パズルのお手伝い

8クイーン問題を変形した問題です。深さ優先探索します。複数回出力してしまわないように気をつけましょう。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int dx[8] = {-1,-1,-1, 0, 0,+1,+1,+1};
int dy[8] = {-1, 0,+1,-1,+1,-1, 0,+1};
bool ans_flag = false;
 
void debug(vector<string>& c){
    cout << "[debug]" << endl;
    for(int y=0 ; y < c.size() ; y++ ){
        cout << c[y] << endl;
    }
    cout << endl;
}
 
bool check(int x,  int y, int i, vector<string>& c){
    if( c[y][x] == 'Q' ) return false;
    
    c[y][x] = '*';
    int mx = x + dx[i];
    int my = y + dy[i];
    if( 0 <= mx && 0 <= my && mx < 8 && my < 8 ){
        if( c[my][mx] == 'Q' ){
            return false;
        }else{
            return check( mx , my , i , c );
        }
    }
    return true;
}
 
void dfs(vector<string> c, int x){
    if( ans_flag ) return;
    
    if( x == 8 ){
        for(int y=0 ; y < c.size() ; y++ ){
            for(int x=0 ; x < 8 ; x++ ){
                if( c[y][x] == '*' ) c[y][x] = '.';
                cout << c[y][x];
            }
            cout << endl;
        }
        ans_flag = true;
        return;
    }
    
    for(int y=0 ; y < 8 ; y++ ){
        if( c[y][x] == 'Q' ){
            dfs( c , x+1 );
        }else if( c[y][x] == '.' ){
            vector<string> c_ = c;
            c_[y][x] = 'Q';
            bool flag = true;
            for(int i=0 ; i < 8 ; i++ ){
                int mx = x + dx[i];
                int my = y + dy[i];
                if( 0 <= mx && 0 <= my && mx < 8 && my < 8 ){
                    flag = flag && check( mx , my , i , c_ );
                }
            }
            if( flag ) dfs( c_ , x+1 );
        }
    }
}
 
int main(){
    vector<string> c(8);
    
    for(int y=0 ; y < 8 ; y++ ){
        cin >> c[y];
    }
    bool exist_flag = true;
    for(int y=0 ; y < 8 ; y++ ){
        for(int x=0 ; x < 8 ; x++ ){
            if( c[y][x] == 'Q' ){
                for(int i=0 ; i < 8 ; i++ ){
                    int mx = x + dx[i];
                    int my = y + dy[i];
                    
                    if( 0 <= mx && 0 <= my && mx < 8 && my < 8 ){
                        exist_flag = exist_flag && check( mx , my , i , c );
                    }
                }
            }
        }
    }
    
    if( exist_flag == false ){
        cout << "No Answer" << endl;
        return 0;
    }else{
        dfs( c , 0 );
    }
    
    if( ans_flag == false ){
        cout << "No Answer" << endl;
    }
}