CODE FESTIVAL 2014 予選B C - 錬金術士

1 WAしたコード

簡単に考えて書いてみましたがWA。

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s1,s2,s3;
  cin>>s1>>s2>>s3;
  int len=s1.length();
  map<char,int>mp1;
  map<char,int>mp2; 
  map<char,int>mp3;     

  for(int i=0;i<len;i++){
    mp1[s1.at(i)]++;
    mp2[s2.at(i)]++;
    mp3[s3.at(i)]++;
  }
  int flag=1;
  int cnt1=0;
  int cnt2=0;
  for(char c='A';c<='Z';c++){
    if(mp3[c] != 0){
      if(min(mp1[c],len/2)+min(mp2[c],len/2)>=mp3[c]){
        if(mp3[c]>mp2[c]){
          cnt1+=(mp3[c]-mp2[c]);
          //cout<<mp3[c]<<" "<<mp2[c]<<" "<<cnt1<<endl;
          continue;
        }
        if(mp3[c]>mp1[c]){
          cnt2+=(mp3[c]-mp1[c]);
          continue;
        }
      }
      else{
        flag=0;
      }
    }
  }
  if(cnt1>len/2 || cnt2>len/2){
    flag=0;
  }
  //cout<<cnt1<<" "<<cnt2<<" "<<len<<endl;
  if(flag){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  } 
  return 0;
}

ACしたコード

解説ACです。

各文字についてs1からとれる最大と最小をもとめて合算しNがその範囲内にあるかで判定します。
最小の方のカウントが最初に考えた方法では甘かったです。

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s1,s2,s3;
  cin>>s1>>s2>>s3;
  int len=s1.length();
  map<char,int>mp1;
  map<char,int>mp2; 
  map<char,int>mp3;     

  for(int i=0;i<len;i++){
    mp1[s1.at(i)]++;
    mp2[s2.at(i)]++;
    mp3[s3.at(i)]++;
  }
  int max1=0;
  int min1=0;
  for(char c='A';c<='Z';c++){
    min1+=max(0,mp3[c]-mp2[c]);
    max1+=min(mp1[c],mp3[c]);
  }
  if(min1<=len/2 && max1>=len/2){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  }
  return 0;
}