# 芝浦ばちゃ#10

# A - Programming Education

# 概要

  • 1の時, Hello Worldを出力せよ
  • 2の時, A+Bを出力せよ

# 提出コード

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

int main(){
  int n; cin>>n;
  if(n==1) cout<<"Hello World"<<endl;
  else {
    int a,b; cin>>a>>b;
    cout<<a+b<<endl;
  }
  return 0;
}

# A - Digits Sum

# 概要

  • 2つの正整数A,BA,Bの和NNが与えられる
  • A,BA, Bの各桁の和の合計として考えられる最小値を求めよ

# 解法

  • 制約が10^5程度なので, 全てのA+B=NA+B=NとなるようなA,BA,Bに対して全探索が可能
  • したがって, その中の最小値を求めればよい

# 提出コード

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

int getSum(int n){
  int res = 0;
  string s = to_string(n);
  for(auto &&si: s){
    res += si-'0';
  }
  return res;
}

signed main() {
  int n; cin>>n;

  int ans = 1LL<<30;
  for(int i=1;i<=(n/2)+1;++i){
    ans = min(ans, getSum(i) + getSum(n-i));
  }
  cout<<ans<<endl;
  return 0;
}

# C - Train Ticket

# 概要

  • Aop1Bop2Cop3D=7A op1 B op2 C op3 D = 7となるようなop1〜3の組を探し, 求めよ
  • op1〜3は, +または-とする

# 解法

  • op1〜3を全探索すれば良い
  • 色々書き方はあるが, 話題に出たbit全探索で書いてみる
    • bit全探索は, iビット目が立っているか否かを調べれば良い
  • 一部ぺぺさんのコードを参考にした

bit全探索の判定

  • 次のどちらの記法も使用可能
    • (1<<i) & bit
    • (bit>>i) & 1
  • 個人的には, 2つ目をお勧めしたい
    • なぜなら(1<<i)は, i>29の時オーバーフローして正しく判定されない時があるため
    • (1LL<<i)と書けば良い話ではあるが

# 提出コード

#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;
  
  for(int bit=0;bit<(1<<3);++bit){
    int res = s[0]-'0';
    for(int i=0;i<3;++i){
      // iビット目が立っている時は+1, 立っていない時は-1をかけることで, +-としている
      res += ((bit>>i)&1?+1:-1) * (s[i+1]-'0');
    }
    if (res == 7) {
       // 解ができた時は出力
       cout<<s[0];
       for(int i=0;i<3;++i){
         // この書き方でもok
         cout<<(bit&(1<<i)?"+":"-")<<s[i+1];
       }
       cout<<"=7"<<endl;
       return 0;
    }
  }
  return 0;
}

# D - Decayed Bridges

# 概要

  • NN個の島とMM本の橋がある
  • ii本目の橋は島aia_ibib_iを結ぶ

# 解法

  • 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-29 15:06:42