結果

問題 No.145 yukiover
ユーザー chakkuchakku
提出日時 2016-12-27 12:08:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 3,034 bytes
コンパイル時間 3,649 ms
コンパイル使用メモリ 177,720 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-05-08 19:10:27
合計ジャッジ時間 2,703 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 5 ms
6,944 KB
testcase_12 AC 7 ms
6,944 KB
testcase_13 AC 6 ms
6,944 KB
testcase_14 AC 7 ms
6,940 KB
testcase_15 AC 7 ms
6,940 KB
testcase_16 AC 4 ms
6,940 KB
testcase_17 AC 7 ms
6,944 KB
testcase_18 AC 8 ms
6,944 KB
testcase_19 AC 8 ms
6,944 KB
testcase_20 AC 8 ms
6,944 KB
testcase_21 AC 7 ms
6,940 KB
testcase_22 AC 8 ms
6,944 KB
testcase_23 AC 8 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }

constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    int N; cin>>N;
    string s; cin>>s;
    sort(all(s));
    cerr << s << endl;
    int cntz = count_if(s.begin(),s.end(),[](char c){return c=='z';});
    int cnty = count_if(s.begin(),s.end(),[](char c){return c=='y';});
    int cntu = count_if(s.begin(),s.end(),[](char c){return c=='u';});
    int cntk = count_if(s.begin(),s.end(),[](char c){return c=='k';});
    int cnti = count_if(s.begin(),s.end(),[](char c){return c=='i';});

    int ans=cntz;
    priority_queue<char> que;
    for(int i=0;i<N;i++) if(s[i]!='y' and s[i]!='u' and s[i]!='k' and s[i]!='i' and s[i]<'y'){
        que.push(s[i]);
    } 

    while(!que.empty()){
        char p = que.top();
        que.pop();
//        cout << p << endl;

        if(cnty==0) break;

        if(p>'u'){
            ans++;
            cnty--;
        }else if(p>'k'){
            if(cntu==0) break;
            ans++;
            cnty--;
            cntu--;
        }else if(p>'i'){
            if(cntu==0 or cntk==0) break;
            ans++;
            cnty--;
            cntu--;
            cntk--;
        }else{
            if(cntu==0 or cntk==0 or cnti==0) break;
            ans++;
            cnty--;
            cntu--;
            cntk--;
            cnti--;
        }
    }


    if(cntu>0 and cntk>0 and cnti>=2){
        int t=min({cnty,cntu,cntk,cnti/2});
        ans+=t;
        cnty-=t;
        cntu-=t;
        cntk-=t;
        cnti-=t*2;
    }

    if(cntu>0 and cntk>=2){
        int t=min(min(cnty,cntu),cntk/2);
        ans+=t;
        cnty-=t;
        cntu-=t;
        cntk-=t*2;
    }

    if(cntu>=2){
        int t=min(cnty,cntu/2);
        ans+=t;
        cnty-=t;
        cntu-=t*2;
    }

    if(cnty>=2){
        ans += cnty/2;
    }
    cout << ans << endl;
}
0