AtCoder Beginner Contest 278

2022年11月22日 14:40

結果

A - Shift:AC(10:06)
B - Misjudge the Time:AC(24:58)
C - FF:AC(36:43)
D - All Assign Point Add:AC(78:48)(1ペナ)
E - Grid Filling:提出無し

A - Shift

長さ$${N}$$の数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、$${A}$$の先頭の要素を取り除き、末尾に0を挿入する操作を$${K}$$回行った後の$${A}$$の要素全てを出力する問題

自分の回答

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> A;
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    if(i < K){
      continue;
    }
    A.push_back(a);
  }
  while(A.size() != N){
    A.push_back(0);
  }

  for(int i = 0; i < N; i++){
    printf("%d", A[i]);
    if(i < N - 1){
      printf(" ");
    }
    else{
      printf("\n");
    }
  }
}

$${K}$$回$${A}$$の要素をスルーして、後で要素数が$${N}$$になるまで0を挿入

公式解説

省略

B - Misjudge the Time

24時制で$${AB}$$時$${CD}$$分を$${\begin{matrix}AC\\BD\end{matrix}}$$と表示する時計がある
現在の時刻が$${h}$$時$${m}$$分であるとき、$${AC}$$時$${BD}$$分と読んでしまっても時刻として破綻が無い時刻に初めてなるのが現在時刻も含めていつかを求める問題

自分の回答

int main(){
  int H, M;
  cin >> H >> M;
 
  while(true){
    if(H % 10 >= 0 && H % 10 <= 5){
      if(!(H / 10 == 2 && M / 10 >= 4)){
        printf("%02d %02d\n", H, M);
        return 0;
      }
    }

    M++;
    if(M == 60){
      H++;
      M = 0;
      if(H == 24){
        H = 0;
      }
    }
  }
}

$${B}$$が0~5、$${B}$$が2であるとき$${C}$$が4以下である、の2つを満たしたときが求める時刻のため、後は1分づつ進めて確認

公式解説

省略

C - FF

とあるSNSに$${1}$$から$${N}$$番の番号が付いた$${N}$$人のユーザーが存在し、$${Q}$$回の操作が行われた
$${i}$$回目の操作は3つの整数$${T_{i},A_{i},B_{i}}$$で表され
・$${T_{i}=1}$$の時、$${A_{i}}$$が$${B_{i}}$$をフォロー
・$${T_{i}=2}$$の時、$${A_{i}}$$が$${B_{i}}$$をフォロー解除
・$${T_{i}=3}$$の時、$${A_{i}}$$と$${B_{i}}$$が相互フォローならYesを出力し、違うならNoを出力する
全てのユーザーが誰もフォローしていない状態から$${i}$$が小さい順に全ての操作をする問題

自分の回答

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

  map<int, set<int>> F;
  for(int i = 0; i < Q; i++){
    int T, A, B;
    cin >> T >> A >> B;
    
    if(T == 1){
      F[A].insert(B);
    }
    else if(T == 2){
      F[A].erase(B);
    }
    else{
      if(F[A].count(B) && F[B].count(A)){
        printf("Yes\n");
      }
      else{
        printf("No\n");
      }
    }
  } 
}

すでにフォローしている状態でのフォロー操作やフォローしていない状態でのフォロー解除操作もあるため、重複を無くすためにユーザー番号をキーとしたmapにsetを入れてフォロー状態を管理

公式解説

int main() {
    using namespace std;

    unsigned N, Q;
    cin >> N >> Q;

    // フォロー関係を保持する集合
    set<pair<unsigned, unsigned>> follows;

    for (unsigned _{}; _ < Q; ++_) {
        unsigned type, A, B;
        cin >> type >> A >> B;
        if (type == 1)
            // 順序対 (A, B) を追加
            follows.emplace(A, B);
        else if (type == 2)
            // 順序対 (A, B) を削除
            follows.erase({A, B});
        else
            // 順序対 (A, B), (B, A) がどちらも含まれるか判定
            cout << (follows.count({A, B}) && follows.count({B, A}) ? "Yes" : "No") << endl;
    }
    return 0;
}

https://atcoder.jp/contests/abc278/editorial/5230より

pairのsetでもいいのか

なるほど

D - All Assign Point Add

長さ$${N}$$の数列$${A=(A_{1},A_{2},…A_{N})}$$と$${Q}$$個のクエリが与えられるため、全てのクエリを順番に処理していく問題
$${q}$$番目のクエリは以下3つのいずれかである
・1 $${x_{q}}$$の時、$${A}$$の要素全てを$${x_{q}}$$にする
・2 $${i_{q} \space x_{q}}$$の時、$${A_{i_{q}}}$$に$${x_{q}}$$を足す
・3 $${i_{q}}$$の時、$${A_{i_{q}}}$$を出力する

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int64_t> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }

  int Q;
  cin >> Q;
  set<int> check;
  int64_t R =- 1;
  for(int i = 0; i < Q; i++){
    int q;
    cin >> q;
    if(q == 1){
      cin >> R;
      check.clear();
    }
    if(q == 2){
      int a, b;
      cin >> a >> b;
      if(R != -1 && !check.count(a)){
        A[a - 1] = R;
        check.insert(a);
      }
      A[a - 1] += b;
      continue;
    }
    else if(q == 3){
      int a;
      cin >> a;
      if(R != -1 && !check.count(a)){
        A[a - 1] = R;
        check.insert(a);
      }
      printf("%ld\n", A[a - 1]);
      continue;
    }
  }
}

1回駄目だろうなとは思いながら操作を問題に書かれている通りで提出したらTLEした
原因は操作1しかないため、書き換える値を別で保持しておいて必要が出たらその場所を書き換え、どの場所を書き換えたかを記憶しておくsetに記録

いろいろ考えながら書いてた残骸を消し忘れていらないものがあったりifがおかしい

公式解説

省略

E - Grid Filling

縦$${H}$$行、横$${W}$$列のグリッドがあり、上から$${i}$$行目、左から$${j}$$列目を$${(i,j)}$$で表し、$${(i,j)}$$には1以上$${N}$$以下の整数$${A_{i,j}}$$が書かれている
このグリッドを縦$${h}$$行、横$${w}$$列の長方形で塗りつぶす
塗りつぶす長方形の左上の座標を$${(k,l)(1 \leqq k \leqq H-h-1,1 \leqq l \leqq W-w-1)}$$としたとき、全ての$${(k,l)}$$に対して塗りつぶされていないマスに書かれている数字の種類を求める問題

自分の回答

いい方法は思いつかなかったから愚直に調べていく方法で書いてみたけど時間内にちゃんと動くものまで行けなかった

公式解説

int main() {
    using namespace std;
 
    int H, W, N, h, w;
    cin >> H >> W >> N >> h >> w;
 
    vector minX(N, H + 1);
    vector maxX(N, 0);
    vector minY(N, W + 1);
    vector maxY(N, 0);
 
    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            int a;
            cin >> a;
            a -= 1;
            minX[a] = min(minX[a], i);
            maxX[a] = max(maxX[a], i);
            minY[a] = min(minY[a], j);
            maxY[a] = max(maxY[a], j);
        }
    }
 
    for (int i = 0; i <= H - h; ++i) {
        for (int j = 0; j <= W - w; ++j) {
            int k = i + h, l = j + w, ans = N;
            for (int a = 0; a < N; ++a) {
                if (i < minX[a] and maxX[a] <= k and j < minY[a] and maxY[a] <= l) {
                    ans -= 1;
                }
            }
            cout << ans << " \n"[j == W - w];
        }
    }
 
    return 0;
}

https://atcoder.jp/contests/abc278/editorial/5236より

全ての値に対して出てくる$${i,j}$$の最小値と最大値を求めることでその数字が出る範囲を調べ、最大最小共に塗りつぶされる範囲内にあるならその数字は全て塗り潰されている
と判断できるのか

なるほど

この記事が気に入ったらサポートをしてみませんか？