# 芝浦ばちゃ#9

# A - 居合を終え、青い絵を覆う / UOIAUAI

# 概要

  • 英小文字cがvowel(a/i/u/e/o)ならばvowel,そうでなければconsonantを出力せよ

# 提出コード

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

int main(){
  char c; cin>>c;
  switch(c){
  case 'a':
  case 'i':
  case 'u':
  case 'e':
  case 'o':
    cout<<"vowel"<<endl;
    break;
  default:
    cout<<"consonant"<<endl;
    break;
  }
  return 0;
}

# B - Not Found

# 概要

  • 文字列SSに含まれない英小文字のうち, 辞書式最小のものを出力せよ
  • そのような英小文字が存在しない場合は, Noneを出力せよ

# 解法

  • 26文字の英小文字(a〜z)について, 数え上げれば良い
  • その後, 1回以上使われた文字の存在を確認すればよい

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  string s; cin>>s;
  vector<int> cnt(26,0);
  for(auto &&si: s){
    ++cnt[si-'a'];
  }

  for(int i=0;i<26;++i){
    if(cnt[i]>0) continue;
    // 文字コードで'a'からiだけずれている英小文字を出力
    printf("%c\n", 'a'+i);
    return 0;
  }
  cout<<"None"<<endl;
  return 0;
}

# A - Shrinking

# 概要

  • 英小文字からなる文字列ssが与えられる
  • 次の操作をしてssが単一の文字のみからなるようにする時の, 最小の操作回数を求めよ
    • 長さNNの文字列ttを長さN1N-1の文字列tt'に変更する
    • この時, tt'ii文字目は, tti,i+1i, i+1文字目のどちらかである

e.g.)

  • abcbに1度の操作を加えると
  • bbbにすることができる
    • a \rightarrow b (abcbbを1つずらして持ってきた(i+1i+1文字目を採用))
    • b \rightarrow b (abcbbをそのまま持ってきた(ii文字目を採用))
    • c \rightarrow b (abcbbを1つずらして持ってきた(i+1i+1文字目を採用))

# 解法

  • 制約が |s|≦100とゆるゆるなので, 全探索したくなります(なります)
  • 全探索 とは, 具体的にa〜zの26文字全てで条件が満たせるかを 探索 することです

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
constexpr int INF = 1LL<<60;

signed main() {
  string s; cin>>s;
  vector<int> cnt(26,0);
  for(int i=0;i<s.size();++i){
    // 出現する文字数をカウント
    ++cnt[s[i]-'a'];
  }
 
  int ans = INF;
  for(int i=0;i<26;++i){
    // 出現しなかった文字はスルー
    if(!cnt[i]) continue;

    string cpy_s = s;
    int cnt = 0;

    // breakを含んでいるので, 兵庫県警には捕まりません
    while(true){
      // 全ての文字が同じ文字の時はbreak
      if(string(cpy_s.size(), cpy_s[0])==cpy_s) break;

      // i文字目かi+1文字目に'a'+iがあれば, それに変更(操作)
      for(int j=0;j<cpy_s.size();++j){
        if(cpy_s[j+1]=='a'+i || cpy_s[j]=='a'+i) cpy_s[j]='a'+i;
      }
      // 末尾を削除
      cpy_s.pop_back();
      ++cnt;
    }
    ans = min(ans,cnt);
  }
  cout<<ans<<endl;
}

# C - 検索

# 概要

  • NN個の文字列SiS_iが与えられる
  • 文字列TT検索 すると, SiS_iの中から先頭T|T|文字が一致している文字列が検索結果として得られる
  • A1A_1, A2A_2, ..., AkA_k番目の文字列だけを検索結果として得たい時, そのような検索文字列T|T|が存在するか判定し, 存在する場合は長さが最小のものを求めよ

# 解法

  • editorialに沿って書いていく

  • 検索ワードをT|T|とすると, 検索結果に出るか否かは次のように言い換えられる

    • サイトvvが検索結果に出るとき, SvS_vの先頭T|T|文字はTTである

e.g.)

  • TT = "ab"の時, サイトSvS_v = "abcde"が挙げられる
  • この時, SvS_vの先頭(T|T|=2)文字は, "ab"である
  • サイトvvが検索結果に出ないとき, SvS_vの先頭T|T|文字はTTでない

e.g.)

  • TT = "ab"の時, サイトSvS_v = "adcde"が挙げられる
  • この時, SvS_vの先頭(T|T|=2)文字は, "ab"ではない
  • ここで, 検索に出したいサイトをrrとすると, 先ほどの条件を用いると以下のように言い換えられる
    • SrS_rTTを含む

      • これは, 先ほどの考察により分かる
    • サイトvvを検索結果に出したいとき, SvS_vSrS_rの共通接頭辞がTTを含む

e.g.)

  • TT = "ab"の時, SrS_r = "abcd"が挙げられる
  • ここで, SvS_vを"abcc"とすると, SvS_vSrS_rの共通接頭辞は"abc"である
  • 共通接頭辞"abc"は"ab"を含んでいるので, T|T| = "ab"の時にサイトSvS_vは検索結果に表示される
  • サイトvvを検索結果に出したくないとき, SvS_vSrS_rの共通接頭辞がTTを含まない

e.g.)

  • TT = "ab"の時, SrS_r = "abcd"が挙げられる
  • ここで, SvS_vを"accc"とすると, SvS_vSrS_rの共通接頭辞は"a"である
  • 共通接頭辞"a"は"ab"を含んでいないので, T|T| = "ab"の時にサイトSvS_vは検索結果に表示されない
  • 以上の考察により, rr以外のサイトvvについてSvS_vSrS_rの共通接頭辞の長さをLv|L_v|とする

e.g.)

  • SrS_r = "abcd, SvS_v = "abbd"の時, 共通接頭辞は"ab"である
  • したがって, LvL_v = 2である
  • すると, 条件はつぎのように言い換えられる
    • SrS_rTTを含む

      • これは, 先ほどの考察で触れた
    • サイトvvを検索結果に出したいとき, LvT|L_v| \geq |T|

e.g.)

  • TT = "ab", SrS_r = "abcd"とする
  • SvS_vを検索結果に出したい時, SvS_vとしては"abc"や"ab", "abcdefg"などが挙げられる
  • これらの文字列の特徴として, LvTL_v \geq |T|であることがわかる
    • SvS_v = "abc"の時, Lv=32L_v = 3 \geq 2
    • SvS_v = "ab"の時, Lv=22L_v = 2 \geq 2
    • SvS_v = "abcdefg"の時, Lv=42L_v = 4 \geq 2
  • サイトvvを検索結果に出したくないとき, Lv<T|L_v| < |T|

e.g.)

  • TT = "ab", SrS_r = "abcd"とする
  • SvS_vを検索結果に出したい時, SvS_vとしては"adc"や"a", "adcdefg"などが挙げられる
  • これらの文字列の特徴として, LvTL_v \geq |T|であることがわかる
    • SvS_v = "adc"の時, Lv=1<2L_v = 1 < 2
    • SvS_v = "a"の時, Lv=1<2L_v = 1 < 2
    • SvS_v = "adcdefg"の時, Lv=1<2L_v = 1 < 2
  • 以上の考察より, 検索結果に出したいサイトのLiL_iの最小値をshow_minshow\_min,検索結果に出したくないサイトのLiL_iの最大値をhide_maxhide\_maxとすると, TTの条件は次のようになる

    • SrS_rTTを含む
    • hide_max<Tshow_minhide\_max < |T| \leq show\_min
  • これを実装すればよい

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  int n,k;cin>>n>>k;
  // 0で初期化
  vector<int> a(n,0);
  int r;
  for(int i=0;i<k;++i) {
    cin>>r;
    // 表示したいものは1にする
    a[--r] = 1;
  }
  vector<string> s(n);
  for(int i=0;i<n;++i) cin>>s[i];

  // S_rが含まれているもののうち, 最大のものを求める
  string ans=s[r];
  for(int i=0;i<n;++i) {
    if(!a[i]) continue;
    int cnt = 0;
    for(int j=0;j<min(ans.size(), s[i].size());++j) {
      if(ans[j]==s[i][j]) ++cnt;
      else break;
    }
    // substrで再代入せずともresizeでおk
    ans.resize(cnt);
  }

  // S_rが含まれていないもののうち, 最大のものを求める
  int hide_max = -1;
  for(int i=0;i<n;++i) {
    if(a[i]) continue;
    int cnt = 0;
    // forループの条件より, hide_max < ans.size()が保証される
    for(int j=0;j<min(ans.size(), s[i].size());++j) {
      if(ans[j]==s[i][j]) ++cnt;
      else break;
    }
    hide_max = max(hide_max, cnt);
  }

  // hide_max ==show_mnとなった時, 条件を満たさない
  if(hide_max == ans.size()){
    cout<<-1<<endl;
  }else{
    // hide_maxが1度も更新されずhide_max=-1の時は, substr(0,0), すなわち空文字が出力される
    cout<<ans.substr(0,hide_max+1)<<endl;
  }

  return 0;
}
  • お疲れ様でした
Last Updated: 2019-4-4 01:34:22