AtCoder Beginner Contest 335

2024年1月8日 15:19

結果

A - 202<s>3</s> : AC(2:15)
B - Tetrahedral Number : AC(6:32)
C - Loong Tracking : AC(22:48)
D - Loong and Takahashi : AC(60:34)
E - Non-Decreasing Colorful Path : 提出無し

A - 202<s>3</s>

英小文字と数字からなり「2023」で終わる文字列$${S}$$が与えられ、その末尾を「4」にして出力する問題

自分の回答

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

  for(int i = 0; i < S.size(); i++){
    if(i != S.size() - 1){
      printf("%c", S[i]);
    }
    else{
      printf("4\n");
    }
  }
}

そのまま

公式解説

省略

B - Tetrahedral Number

正整数$${N}$$が与えられ、非負整数の組$${(x,y,z)}$$であって$${x+y+z \leqq N}$$であるもの全てを辞書順で小さい順に出力する問題

自分の回答

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

  int x = 0, y = 0, z = 0;
  while(x < N){
    printf("%d %d %d\n", x, y, z);
    z++;
    if(x + y + z > N){
      z = 0;
      y++;
    }
    if(x + y + z > N){
      y = 0;
      x++;
    }
  }
  printf("%d %d %d\n",x,y,z);
}

小さい順に総当たり

公式解説

N=int(input())

for x in range(N+1):
  for y in range(N+1):
    for z in range(N+1):
      if x+y+z<=N:
        print(x,y,z)

Pythonによるもの
https://atcoder.jp/contests/abc335/editorial/9025より

そうかforでよかったか

C - Loong Tracking

座標平面上に$${N}$$パーツからなる龍が存在しパーツ$${1}$$を頭と言い、最初パーツ$${i}$$は$${(i,0)}$$に存在する
以下のクエリ$${Q}$$個を処理する問題
・1 C : 頭を方向$${C}$$へ$${1}$$移動させる。他のパーツは番号が一つ前のパーツがいた場所へ移動する
・2 p : パーツ$${p}$$のいる座標を出力する

自分の回答

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

  deque<pair<int, int>> P;
  for(int i = 1; i <= N; i++){
    P.push_back({i, 0});
  }
  for(int _ = 0; _ < Q; _++){
    int q;
    cin >> q;
    if(q == 1){
      char c;
      cin >> c;
      auto [i, j] = P.front();
      if(c == 'R'){
        P.push_front({i + 1, j});
      }
      else if(c == 'L'){
        P.push_front({i - 1, j});
      }
      else if(c == 'U'){
        P.push_front({i, j + 1});
      }
      else{
        P.push_front({i, j - 1});
      }
      P.pop_back();
    }
    else{
      int p;
      cin >> p;
      p--;
      printf("%d %d\n", P[p].first, P[p].second);
    }
  }
}

dequeならpush_frontもアクセスも速いためそれで終わり

公式解説

https://atcoder.jp/contests/abc335/editorial/9026より

dequeを使わない方法
配列にpush_backしていって答える時は後ろからi番目がそれぞれのパーツのいる場所

なるほど

D - Loong and Takahashi

一辺が奇数$${N}$$マスである正方形のグリッドがある
グリッドの中央には高橋君が存在し、高橋君のいるマスを除いた全てのマスに上下左右の移動で一筆書きし全てのマスを通るにはどのように移動すればいいか求める問題

自分の回答

void move(int &i, int &j, queue<char> d){
  if(d.front() == 'R'){
    j++;
  }
  else if(d.front() == 'D'){
    i++;
  }
  else if(d.front() == 'L'){
    j--;
  }
  else{
    i--;
  }
}

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

  vector<vector<int>> F(N + 2, vector<int>(N + 2, -1));
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      if(i == (N + 1) / 2 && j == (N + 1) / 2){
        continue;
      }
      F[i][j] = 0;
    }
  }

  queue<char> d;
  d.push('R');
  d.push('D');
  d.push('L');
  d.push('U');
  int m = 1, i = 1, j = 0;
  while(m <= N * N - 1){
    int goi = i,goj = j;
    move(goi, goj, d);
    if(F[goi][goj] != 0){
      d.push(d.front());
      d.pop();
      goi = i,goj = j;
      move(goi, goj, d);
    }
    F[goi][goj] = m;
    m++;
    i = goi, j = goj;
  }

  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      if(i == (N + 1) / 2 && j == (N + 1) / 2){
        printf("T ");
        continue;
      }
      printf("%d ", F[i][j]);
    }
    printf("\n");
  }
}

どんなサイズでも角から渦巻で行けるからそうして終わり

公式解説

省略

E - Non-Decreasing Colorful Path

$${N}$$頂点$${M}$$辺の連結な無向グラフがあり、各頂点には整数$${A_{v}}$$が書かれている
頂点$${1}$$から$${N}$$への単純なパスに対して、通った順に頂点の整数が広義単調増加であるならばその種類数を得点として得られ、そうでないなら$${0}$$となる
最大で何点得られるか求める問題

自分の回答

ダイクストラ法っぽい感じはするけど書ききれなかった

公式解説

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  UnionFind uf(n);
  vector<vector<pair<int,int>>> vp(200005);
  for(int i=0;i<m;i++){
    int u,v;
    cin >> u >> v;
    u--;v--;
    if(a[u]>a[v]){swap(u,v);}
    if(a[u]==a[v]){uf.unionSet(u,v);}
    else{vp[a[u]].push_back({u,v});}
  }

  vector<int> dp(200005,-1e9);
  dp[uf.root(0)]=1;
  for(auto &nx : vp){
    for(auto [u,v] : nx){
      u=uf.root(u);
      v=uf.root(v);
      if(dp[u]>0){
        dp[v]=max(dp[v],dp[u]+1);
      }
    }
  }
  cout << max(0,dp[uf.root(n-1)]) << "\n";
  return 0;
}

https://atcoder.jp/contests/abc335/editorial/9037より

点数が0となるルートを消して有向グラフとする
動的計画法をしたいが同じ値での移動が可能だとできないためUnion-Findでそれをまとめて動的計画法

なるほど

ダイクストラ法でもできるっぽい

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