AtCoder Beginner Contest 320

Toyota Programming Contest 2023#5（AtCoder Beginner Contest 320） - AtCoder

A - Leyland Number : AC(2:34)
B - Longest Palindrome : AC(14:22)
C - Slot Strategy 2 (Easy) : AC(52:26)
D - Relative Position : AC(68:26)
E - Somen Nagashi : AC(95:38)

A - Leyland Number

正整数$${A,B}$$が与えられ、$${A^B+B^A}$$を求める問題

自分の回答

int main(){
  int A, B;
  cin >> A >> B;

  printf("%.0lf\n", pow(A, B) + pow(B, A));
}

そのまま

公式解説

省略

B - Longest Palindrome

文字列$${S}$$が与えられ、その中の連続する部分文字列で回文であるもののうち最大の長さを求める問題

自分の回答

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

  int ans = 0;
  for(int i = 0; i < S.size(); i++){
    for(int j = S.size(); j >= 0; j--){
      int L = i, R = j;
      bool c = true;
      while(L <= R){
        if(S[L] != S[R]){
          c = false;
          break;
        }
        L++;
        R--;
      }
      if(c){
        ans=max(ans, j - i + 1);
      }
    }
  }

  printf("%d\n", ans);
}

始点と終点総当たり

公式解説

省略

C - Slot Strategy 2 (Easy)

$${3}$$個のリールからなるスロットがあり、$${i}$$番目のリールの配列は文字列$${S_{i}}$$で与えられる
リールは$${1}$$秒で$${1}$$文字進み、$${1}$$秒間に$${1}$$回任意のリールを止めることができる
$${3}$$つのリールを止めた時、表示されている文字が全て同じであるようにするには最小何秒かかるか求める問題

自分の回答

int main(){
  int M;
  cin >> M;
  vector<string> R(3);
  cin >> R[0] >> R[1] >> R[2];

  vector<bool> C(10, false);
  for(int i = 0; i < 10; i++){
    if(R[0].find(48 + i) != string::npos && R[1].find(48 + i) != string::npos && R[2].find(48 + i) != string::npos){
      C[i] = true;
    }
  }

  int ans = -1;
  for(int i = 0; i < 10; i++){
    if(!C[i]){
      continue;
    }
    char n = 48 + i;
    vector<int> o = {0, 1, 2};
    do{
      int j = 0, k = 0;
      while(k < 3){
        if(R[o[k]][j % M] == n){
          k++;
        }
        j++;
      }
      if(ans == -1){
        ans = j - 1;
      }
      else{
        ans = min(ans, j - 1);
      }
    }while(next_permutation(o.begin(), o.end()));
  }

  printf("%d\n", ans);
}

まずどの文字が揃えられるかを調べて、その後文字ごとにnext_permutationでリールの止める順番を総当たり

公式解説

省略

D - Relative Position

座標平面上に$${N}$$人の人がいる
人$${1}$$は原点にいて、人$${A_{i}}$$から見て人$${B_{i}}$$はx軸正方向に$${X_{i}}$$、y軸正方向に$${Y_{i}}$$離れた位置にいるという情報が$${M}$$個与えられる
それぞれの人がいる座標を求める問題
ただし一意に定まらないときは「undecidable」とする

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<tuple<int, int64_t, int64_t>>> G(N + 1);
  for(int i = 0; i < M; i++){
    int a, b, x, y;
    cin >> a >> b >> x >> y;
    G[a].push_back({b, x, y});
    G[b].push_back({a, -x, -y});
  }

  vector<pair<int64_t,int64_t>> ans(N + 1);
  vector<bool> con(N + 1, false);
  queue<int> bfs;
  bfs.push(1);
  ans[1] = {0, 0};
  con[1] = true;
  while(!bfs.empty()){
    int n = bfs.front();
    bfs.pop();
    for(auto [go, x, y] : G[n]){
      if(con[go]){
        continue;
      }
      int64_t nx = ans[n].first + x, ny = ans[n].second + y;
      ans[go] = {nx, ny};
      bfs.push(go);
      con[go] = true;
    }
  }

  for(int i = 1; i <= N; i++){
    if(con[i]){
      printf("%ld %ld\n", ans[i].first, ans[i].second);
    }
    else{
      printf("undecidable\n");
    }
  }
}

幅優先探索みたいな感じ

公式解説

省略

E - Somen Nagashi

$${N}$$人で流しそうめんをする
人は$${1}$$を先頭に番号順に並んでいる
以下のイベントが$${M}$$回行われた後、それぞれの人が合計でどれだけのそうめんを得られたか求める問題
・時刻$${T_{i}}$$に量$${W_{i}}$$のそうめんを流し、列の先頭にいる人がそれを全て得る。その人は列を離れ、$${S_{i}}$$秒後に列の元の位置に戻る

自分の回答

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

  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> ct;
  priority_queue<int, vector<int>, greater<int>> st;
  for(int i = 1; i <= N; i++){
    st.push(i);
  }
  vector<int64_t> ans(N + 1, 0);
  for(int i = 0; i < M; i++){
    int t, w, s;
    cin >> t >> w >> s;
    if(!ct.empty()){
      while(ct.top().first <= t && !ct.empty()){
        st.push(ct.top().second);
        ct.pop();
      }
    }
    if(st.empty()){
      continue;
    }
    int e = st.top();
    st.pop();
    ans[e] += w;
    ct.push({t + s, e});
  }

  for(int i = 1; i <= N; i++){
    printf("%ld\n", ans[i]);
  }
}

列にいる人と離れている人が帰ってくる時間をそれぞれpriority_queueで管理すれば時間内に終わる
離れている人を列に戻す処理の部分がちょっと時間無くてぐちゃってる

公式解説

省略