AtCoder Beginner Contest 309

Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309) - AtCoder

結果

A - Nine : AC(2:29)
B - Rotate : AC(18:15)
C - Medicine : AC(30:04)
D - Add One Edge : AC(48:06)
E - Family and Insurance : TLE

A - Nine

$${3×3}$$で左上から$${1,2,…,9}$$の数字が書かれた盤面がある
$${1}$$以上$${9}$$以下の整数$${A,B(A < B)}$$が与えられ、その数字が書かれたマスが左右に隣接しているか判定する問題

自分の回答

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

  if(A != 3 && A != 6){
    if(A + 1 == B){
      printf("Yes\n");
      return 0;
    }
  }
  printf("No\n");
}

そのまま

公式解説

省略

B - Rotate

$${0}$$か$${1}$$からなる$${N}$$行$${N}$$列のマス目が与えられる
このマス目の外周のマスを1つづつ時計回りにずらした結果を出力する問題

自分の回答

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

  vector<vector<char>> ans(N, vector<char>(N));
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(i == 0 && j != 0){
        ans[i][j] = A[i][j - 1];
      }
      else if(j == N - 1 && i != 0){
        ans[i][j] = A[i - 1][j];
      }
      else if(i == N - 1 && j != N - 1){
        ans[i][j] = A[i][j + 1];
      }
      else if(j == 0 && i != N - 1){
        ans[i][j] = A[i + 1][j];
      }
      else{
        ans[i][j] = A[i][j];
      }
    }
  }

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

そのまま
だけどもっときれいに書けるやり方ありそう

公式解説

同じだった…

C - Medicine

高橋君が$${N}$$種類の薬を処方され、それぞれ$${a_{i}}$$日間$${b_{i}}$$錠ずつ飲む必要がある
飲む薬が$${K}$$錠以下になるのは何日目か求める問題

自分の回答

int main(){
  int N, K;
  cin >> N >> K;
  map<int, vector<int>> M;
  set<int> D;
  int64_t now = 0;
  for(int i = 0; i < N; i++){
    int a, b;
    cin >> a >> b;
    M[a].push_back(b);
    D.insert(a);
    now += b;
  }

  if(now <= K){
    printf("1\n");
    return 0;
  }

  while(true){
    int nowd = *begin(D);
    D.erase(nowd);
    for(int x : M[nowd]){
      now -= x;
    }
    if(now <= K){
      printf("%d\n", nowd + 1);
      return 0;
    }
  }
}

1日目から見て行ったらTLEするからmapで日付ごとにまとめて日付を入れたsetで前から減らしていってK以下になったら出力

mapはvectorじゃなくて足していけばよかった

公式解説

int main() {
    
	int N,K;
	cin>>N>>K;
	
	vector<pair<int,int>> p(N);
	
	for(int i=0;i<N;i++){
		cin>>p[i].first>>p[i].second;
	}
	
	sort(p.begin(),p.end());
	
	long long sum = 0;
	
	for(int i=0;i<N;i++){
		sum += p[i].second;
	}
	
	if(sum<=K)cout<<1<<endl;
	else{
		for(int i=0;i<p.size();i++){
			if(sum<=K){
				cout<<p[i-1].first+1<<endl;
				return 0;
			}
			sum -= p[i].second;
		}
		cout<<p.back().first+1<<endl;
	}
	
	return 0;
}

https://atcoder.jp/contests/abc309/editorial/6746より

vectorに入れてソートすればよかったか

なるほど

D - Add One Edge

$${N_{1}+N_{2}}$$頂点$${M}$$辺の無向グラフがあり頂点$${1}$$と$${N_{1}+N_{2}}$$は非連結である
任意の頂点を結ぶ辺を$${1}$$つ追加して頂点$${1}$$と$${N_{1}+N_{2}}$$を連結にしたとき、頂点$${1}$$と$${N_{1}+N_{2}}$$の距離としてあり得る値のうち最大の値を求める問題

自分の回答

vector<vector<int>> G(300001, vector<int>());
vector<bool> seen(300001, false);
 
int bfs(int st){
  int rt = 0;
  queue<pair<int, int>> que;
  que.push({st, 0});
  seen[st] = true;
  while(!que.empty()){
    auto [now, dis] = que.front();
    rt = max(rt, dis);
    que.pop();
    for(int x : G[now]){
      if(seen[x]){
        continue;
      }
      que.push({x, dis + 1});
      seen[x] = true;
    }
  }
  return rt;
}
 
int main(){
  int N1, N2, M;
  cin >> N1 >> N2 >> M;
  for(int i = 0; i < M; i++){
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  int d1 = bfs(1), d2 = bfs(N1 + N2);

  printf("%d\n", d1 + d2 + 1);
}

頂点1とN1+N2のそれぞれから幅優先探索して最も遠い距離の和+1

公式解説

省略

E - Family and Insurance

人$${1}$$から$${N}$$までからなる家系があり、人$${i}$$の親は$${p_{i}}$$である
この家系の人が$${M}$$回保険に加入し、それぞれ人$${x_{i}}$$が加入し本人と$${y_{i}}$$代先までが対象である
保険の対象となっている人が何人いるか求める問題

自分の回答

有向グラフっぽく見えたからいろいろ削減はして探索してみたけどダメだった

公式解説

int main() {
    
	int N,M;
	cin>>N>>M;
	
	vector<int> p(N);
	
	for(int i=1;i<N;i++){
		cin>>p[i];
		p[i]--;
	}
	
	vector<int> dp(N,-1);
	
	for(int i=0;i<M;i++){
		int x,y;
		cin>>x>>y;
		x--;
		dp[x] = max(dp[x],y);
	}
	
	for(int i=1;i<N;i++){
		dp[i] = max(dp[i],dp[p[i]]-1);
	}
	
	int ans = 0;
	for(int i=0;i<N;i++){
		if(dp[i]>=0)ans++;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

https://atcoder.jp/contests/abc309/editorial/6748より

そうか上から動的計画法か

なるほど