AtCoder Beginner Contest 352

AtCoder Beginner Contest 352 - AtCoder

結果

A - AtCoder Line : AC(2:24)
B - Typing : AC(5:52)
C - Standing On The Shoulders : AC(10:45)
D - Permutation Subsequence : WA

A - AtCoder Line

AtCoder線という鉄道があり、そこには$${1}$$から$${N}$$までの駅がある
AtCoder線には$${1}$$を始発駅として$${N}$$まで各駅に停止する上り列車と$${N}$$を始発駅として$${1}$$まで各駅に停止する下り列車がある
駅$${X}$$から駅$${Y}$$まで移動するとき、駅$${Z}$$に停車することがあるか判定する問題

自分の回答

int main() {
  int N, X, Y, Z;
  cin >> N >> X >> Y >> Z;

  if(min(X, Y) <= Z && max(X, Y) >= Z){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
}

ZがXとYの間にあるか調べて終わり

公式解説

省略

B - Typing

英小文字からなる文字列$${S}$$をキーボードで入力しようとしたが、画面を見ておらず、誤って別の文字を入力した際にバックスペースを押したがバックスペースキーが故障していたため実際に入力した結果は$${T}$$となった
正しく入力された文字が$${T}$$の何文字目か求める問題

自分の回答

int main() {
  string S, T;
  cin >> S >> T;

  int i = 0, j = 0;
  while(i < S.size()){
    if(S[i] == T[j]){
      printf("%d ", j + 1);
      i++;
    }
    j++;
  }
}

SとTを前から見て行って一致したらTの何文字目かを出力してSの見る文字を進める

今思えばiはforにして良かったな

公式解説

省略

C - Standing On The Shoulders

$${N}$$人の巨人がいて、それぞれの巨人が立った時の肩までの高さは$${A_{i}}$$、頭までの高さは$${B_{i}}$$である
巨人全員を任意の順番で積み重ねる、この時上の巨人は下の巨人の肩に立っている
積み重ねた高さの最大を求める問題

自分の回答

int main() {
  int N;
  cin >> N;

  int64_t sum = 0, maxhead = 0;
  for(int i = 0; i < N; i++){
    int64_t a, b;
    cin >> a >> b;
    sum += a;
    maxhead = max(maxhead, b - a);
  }

  printf("%ld\n", sum + maxhead);
}

結局頭が一番大きいのを一番上にする以外はどんな順番でも変わらないため肩までの高さの総和と頭の大きさの最大を調べてそれを足して終わり

公式解説

省略

D - Permutation Subsequence

$${1}$$から$${N}$$までの整数を並び替えた数列$${P=(P_{1},P_{2},…,P_{N})}$$がある
この数列から$${K}$$個の連続する整数を取り出したとき、$${P}$$における末尾の位置-先頭の位置は最小いくつか求める問題

自分の回答

数字毎に何番目にあるかを記録してそこから連続する塊の中の最小と最大を出して調べる
毎回塊を作っていたら計算量が怪しいためsetで管理して新しく入ってくるやつを入れて抜けたやつを消すとすれば計算量は少なくなり最大最小も取り出せるため全パターン調べられる
ここまでは良かったというかこれで良かったんだけど問題の理解が正確じゃなかったせいでこの後余計な処理を付けてWA
終了直前で気付いたが間に合わなかった

公式解説

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> q(n);
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        --p;
        q[p] = i;
    }
    set<int> st;
    for (int i = 0; i < k; i++) {
        st.insert(q[i]);
    }
    // *st.rbegin() : 最大値の取得
    // *st.begin() : 最小値の取得
    int ans = *st.rbegin() - *st.begin();
    for (int i = k; i < n; i++) {
        st.erase(q[i - k]);
        st.insert(q[i]);
        ans = min(ans, *st.rbegin() - *st.begin());
    }
    cout << ans << endl;
}

https://atcoder.jp/contests/abc352/editorial/9919より

やっぱりそうだよね