JOI予選の問題を解いてみる

現役の時は参加しなかったので、参加するのは去年に引き続き二回目。
準備ができてなかったどころか寝過ごしたのでひどい。

1問目

問題

食事a,b,c,ドリンクd,eが与えられる。食事とドリンクをセットで注文すると50円引きになる。最も安いセットの価格を出力する。

方針

数値a,b,cの中の最小値とd,eの中の最小値を足して50を引いた値を出力する

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    int a,b,c,d,e;
    cin>>a>>b>>c>>d>>e;
    cout<<(min(min(a,b),c)+min(d,e)-50)<<endl;
    return 0;
}

2問目

問題

組み合わせ対戦結果から順位を求める。

方針

スコアでソートして順位を割り振った後に、チームidでソートして出力。

解答

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
using namespace std;

typedef pair<int,int> PII;
int score[100][100];

int main(){
    int n;
    cin>>n;
    vector<PII> points(n);
    vector<PII> ranks(n);
    int a,b,c,d;
    for(int i=0;i<n*(n+1)/2;i++){
        cin>>a>>b>>c>>d;
        if(c==d){
            score[a-1][b-1] = 1;
            score[b-1][a-1] = 1;             
        }
        else{
            score[a-1][b-1] = c>d?3:0;
            score[b-1][a-1] = d>c?3:0;
        }
    }
    
    for(int i=0;i<n;i++){
      int p = 0;
        for(int j=0;j<n;j++){
            if(i!=j){
                p += score[i][j];
            }
        }
        points[i] = PII(p,i);
    }
    
    sort(points.begin(),points.end());
    reverse(points.begin(),points.end());
    int sc = -1,rank = 0;
    for(int i=0;i<n;i++){
        if(points[i].first != sc){
            sc = points[i].first;
            rank = i;
        }
        ranks[i] = PII(points[i].second,rank);
    }
    
    sort(ranks.begin(),ranks.end());
    for(int i=0;i<n;i++){
        cout<<ranks[i].second+1<<endl;
    }
    
    return 0;
}

3問目

問題

みんながよくやる金額当たりのカロリーを最大化する問題。基本料金、カロリーが決まっているピザにトッピングを乗せる。トッピングの値段は一律で、カロリーのみが違う。

方針

トッピングのカロリーの大きい順にソートして、トッピングを足していった時の(カロリー/金額)の最大値を取る。

解答

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    int n,cost1,cost2,cal1;
    cin>>n;
    cin>>cost1>>cost2;
    cin >> cal1;
    vector<int> cal;
    int cc;
    for(int i=0;i<n;i++){
        cin>>cc;
        cal.push_back(cc);
    }
    sort(cal.begin(),cal.end());
    reverse(cal.begin(),cal.end());
    
    int ans = cal1/cost1;
    int m = 0;
    for(int i=0;i<n;i++){
            cal1 += cal[i];
            cost1 += cost2;
            ans = cal1/cost1;   
            m = max(ans,m);
    }
    cout<<m<<endl;
    return 0;
}

4問目

問題

メニューが3種類あり、いくつかの日食べるメニューは決まっている。
3日続けて同じメニューが現れない条件で、メニューの決め方は何通りあるか。
10000で割った余りを出力する。

方針

前二日のメニュー9通りx日数でDPを掛ける。同じメニューが3日続いていたり、メニューが決まっている日を考慮する。

解答

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int dp[9][100];
int menu[100];

int main(){
    for(int i=0;i<9;i++){
        for(int j=0;j<100;j++){
            dp[i][j] = 0;
        }
    }
    for(int i=0;i<100;i++){
        menu[i] = -1;
    }
    
    int n,k;
    cin>>n>>k;
    int a,b;
    for(int i=0;i<k;i++){
        cin>>a>>b;
        menu[a-1] = b-1;   
    }
    
    if(menu[0] == -1&&menu[1] == -1){
        for(int i=0;i<9;i++){
            dp[i][1] = 1;
        }
    }
    else if(menu[1] == -1){
        for(int i = 0;i<3;i++){
            dp[menu[0]*3+i][1] = 1;
        }
    }
    else if(menu[0] == -1){
        for(int i = 0;i<3;i++){
            dp[i*3+menu[1]][1] = 1;
        }
    }
    else{
        dp[(menu[0])*3+menu[1]][1] = 1;
    }

    for(int i=2;i<n;i++){
        for(int j=0;j<9;j++){
              dp[j][i] = dp[j/3][i-1] + dp[j/3+3][i-1] + dp[j/3+6][i-1];
        }
        
        dp[0][i] -= dp[0][i-1];
        dp[4][i] -= dp[4][i-1];
        dp[8][i] -= dp[8][i-1]; 
        
        if(menu[i] != -1){
            for(int j=0;j<9;j++){
                if(j%3 != menu[i]) dp[j][i] = 0;
            }    
        }
    for(int j=0;j<9;j++){
          dp[j][i] %= 10000;
          }
    }
    
    int sum = 0;
    for(int j = 0;j<9;j++){
        sum+= dp[j][n-1];
    }
    cout<<sum%10000<<endl;
 
   return 0;
}

問題5

問題

ハニカム構造で出来たマップに建物があり、それを取り囲むイルミネーションの長さを求める問題。
イルミネーションは外から見える場所にのみ設置する。

方針

外側からbfsを掛け、「外側」を特定する。それぞれの建物が「外側」に面している個数を数える。

解答

なぜか01がくっついた文字列の入力だと勘違いしていたのでstringで実装してます。
ハニカム構造ライブラリとか持ってないや。

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

typedef pair<int,int> PII;

int main(){
    int w,h;
    cin>>w>>h;
    vector<string> field;
    string s;
    for(int i=0;i<h;i++){
        string s="";
        int a;
        for(int x=0;x<w;x++){
            cin>>a;
            if(a==0)s+="0";
            if(a==1)s+="1";
        }
         field.push_back(s);        
    }
    
    queue<pair<int,int> >qu;
    for(int i=0;i<h;i++){
        qu.push(PII(0,i));
        qu.push(PII(w-1,i));
    }    
    for(int i=0;i<w;i++){
        qu.push(PII(i,0));
        qu.push(PII(i,h-1));
    }    

    while(!qu.empty()){
        PII p = qu.front();
        qu.pop();
        int x = p.first;
        int y = p.second;
        if(x>=0 && x<w && y>=0 && y< h){
            if(field[y][x] == '0'){
                field[y][x] = '-';
                qu.push(PII(x+1,y));
                qu.push(PII(x-1,y));
                qu.push(PII(x,y+1));
                qu.push(PII(x,y-1));
                if(y%2 == 1){
                    qu.push(PII(x-1,y+1));
                     qu.push(PII(x-1,y-1));                
                }
                else{
                  qu.push(PII(x+1,y+1));
                  qu.push(PII(x+1,y-1));                                
                }   
            }
        }
    }
    
     for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){      
            if(field[y][x] == '0') field[y][x] = '1';
          cout<<field[y][x];
        }
        cout<<endl;
    }
    
    int count = 0;
    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            if(field[y][x] == '1'){
                int c = 6;
                if(x<w-1) c -= field[y][x+1] == '1';
                if(x>=1) c -= field[y][x-1] == '1';
                if(y<h-1) c -= field[y+1][x] == '1';
                if(y>=1) c -= field[y-1][x] == '1';
               if(y%2 == 1){
                    if(x>=1){
                        if(y<h-1) c -= field[y+1][x-1] == '1';
                        if(y>=1) c -= field[y-1][x-1] == '1';
                    }
                }
                else{
                    if(x<w-1){
                        if(y<h-1) c -= field[y+1][x+1] == '1';
                        if(y>=1) c -= field[y-1][x+1] == '1';                    
                    }
                }
            count += c;
            cout<<c<<" ";
            }
            else{
            cout<<0<<" ";            
            }
        }
        cout<<endl;
    }
    
    cout<<count<<endl;
    return 0;
}