AtCoder Beginner Contest 279

TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279) - AtCoder

結果

A - wwwvvvvvv:AC(2:46)
B - LOOKUP:AC(6:59)
C - RANDOM:AC(45:01)(1ペナ)
D - Freefall:WA

A - wwwvvvvvv

「v」と「w」のみからなる文字列$${S}$$が与えられ、その中に下に尖った部分が何箇所あるかを求める問題

自分の回答

int main(){
  string S;
  cin >> S;
  int ans = 0;
  for(int i = 0; i < S.size(); i++){
    char s = S[i];
    s == 'v' ? ans += 1 : ans += 2;
  }
  printf("%d\n",ans);
}

そのまま

公式解説

省略

B - LOOKUP

英小文字からなる文字列$${S,T}$$が与えられ、$${T}$$の中に$${S}$$がそのまま含まれているかを求める問題

自分の回答

int main(){
  string S, T;
  cin >> S >> T;
  if(S.find(T) == string::npos){
    printf("No\n");
  }
  else{
    printf("Yes\n");
  }
}

丸々含まれている、ならfindで調べて終わり

公式解説

省略

C - RANDOM

「#」と「.」からなる$${H}$$行$${W}$$列の図形$${S,T}$$が与えられ、図形$${S}$$の列を並び替えて$${T}$$と等しくできるかを求める問題

自分の回答

int main(){
  int H, W;
  cin >> H >> W;
  vector<string> S(W), T(W);
  char c;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> c;
      S[j] += c;
    }
  }
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> c;
      T[j] += c;
    }
  }
  
  map<string, int> Tmap;
  for(string s: T){
    Tmap[s]++;
  }
 
  for(int i = 0; i < W; i++){
    if(Tmap.count(S[i])){
      Tmap[S[i]]--;
    }
  }
  for(auto m: Tmap){
    if(m.second != 0){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}

列でまとめてvectorに入れて$${S}$$と$${T}$$で要素が全て一致するかを比べる
最初vectorのままやったらTLEしたためmapで種類とその個数で調べるようにした
今思えば$${S}$$もmapに入れてしまえばもっときれいか

公式解説

int main(){
  int h,w;
  cin >> h >> w;
  vector<string> s(h),t(h);
  for(auto &nx : s){cin >> nx;}
  for(auto &nx : t){cin >> nx;}

  // A.
  vector<string> Ts(w),Tt(w);
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      Ts[j].push_back(s[i][j]);
      Tt[j].push_back(t[i][j]);
    }
  }

  // B.
  sort(Ts.begin(),Ts.end());
  sort(Tt.begin(),Tt.end());

  if(Ts==Tt){cout << "Yes\n";}
  else{cout << "No\n";}
  return 0;
}

https://atcoder.jp/contests/abc279/editorial/5283より

そうかソートしちゃえば配列が一致するかでいいのか

なるほど

D - Freefall

高橋君があるビルから飛び降り、地上へ行こうとしている
地上へ到達するまでにかかる時間は重力を$${g}$$とすると$${\frac{A}{\sqrt{g}}}$$である
最初$${g}$$は1であり、高橋君は飛び降りる前に$${B}$$秒かけて$${g}$$を1増やすことを好きなだけできる
この時、地上に到達するまでの最短時間を求める問題

自分の回答

サンプルすらちゃんと動くものが書けなかった
小数絡みの問題は経験値が足りてない…

公式解説

using ll = long long;

int main() {
    ll a, b;
    cin >> a >> b;
    auto f = [&](ll n) -> double {
        return (double) a / sqrt(n + 1) + (double) b * n;
    };
    ll argmin = pow((double) a / (b * 2), 2. / 3.) - 1;
    ll l = max(argmin - 5, 0LL), r = min(argmin + 5, a / b);
    double ans = a;
    for (ll i = l; i <= r; i++) {
        ans = min(ans, f(i));
    }
    cout << fixed << setprecision(10) << ans << endl;
}

https://atcoder.jp/contests/abc279/editorial/5288より

まず何回操作するかを$${x}$$とすると、地面までの時間は$${f(x)=Bx+\frac{A}{\sqrt{x+1}}}$$であり、答えは$${x\leqq0}$$である整数における$${f(x)}$$の最小値
$${f(x)}$$の頂点は$${f(x)'=0}$$となる$${x}$$なため$${x=(\frac{A}{2B})^\frac{2}{3} -1}$$で求められる
後は誤差を考慮して$${x}$$の前後の整数をある程度余裕をもって調べてその中から最小値を出力する

なるほど