AtCoder Beginner Contest 277

2022年11月15日 15:35

結果

A - ^{-1}:AC(2:31)
B - Playing Cards Validation:AC(47:22)(2ペナ)
C - Ladder Takahashi:提出無し
D - Takahashi's Solitaire:提出無し

A - ^{-1}

$${(1,2,…,N)}$$を並べ替えた数列$${P}$$と整数$${X}$$が与えられ、$${X}$$が$${P}$$で何番目かを求める問題

自分の回答

int main(){
  int N, X;
  cin >> N >> X;
  for(int i = 0; i < N; i++){
    int P;
    cin >> P;
    if(P == X){
      printf("%d\n", i + 1);
      return 0;
    }
  }
}

そのまま

公式解説

同じため省略

B - Playing Cards Validation

英大文字および数字からなる2文字の文字列が$${N}$$個与えられ、全ての文字列に対して
・1文字目がH , D , C , Sのどれかである
・2文字目がA , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , T , J , Q , K のどれかである
・全ての文字列は相異なる
を全て満たすかを判定する問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }
 
  for(int i = 0; i < N - 1; i++){
    for(int j = i + 1; j < N; j++){
      if(S[i] == S[j]){
        printf("No\n");
        return 0;
      }
    }
  }
 
  for(int i = 0; i < N; i++){
    char S1 = S[i][0], S2 = S[i][1];
    if(S1 != 'H' && S1 != 'D' && S1 != 'C' && S1 != 'S'){
      printf("No\n");
      return 0;
    }
    if(S2 < 50 || S2 > 57){
      if(S2 != 'A' && S2 != 'T' && S2 != 'J' && S2 != 'Q' && S2 != 'K'){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
}

まず全ての文字列が異なるかを判定し、文字の条件を満たすかを判定
ASCIIの数字の位置と分岐条件のミスでそれぞれ1ペナ

公式解説

int main() {
	int n;
	cin >> n;
	vector<string> s(n);
	for (int i = 0; i < n; i++) cin >> s[i];
	bool ans = true;
	for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (s[i] == s[j]) ans = false;
	string s1 = "HDCS";
	string s2 = "A23456789TJQK";
	for (int i = 0; i < n; i++) {
		if (!count(s1.begin(), s1.end(), s[i][0]) || !count(s2.begin(), s2.end(), s[i][1])) ans = false;
	}
	cout << (ans ? "Yes" : "No") << '\n';
}

https://atcoder.jp/contests/abc277/editorial/5211より

文字判定そんなやり方があるのか！

なるほど

C - Ladder Takahashi

$${10^9}$$階のビルにはしごが$${N}$$本かかっており、$${i}$$番目のはしごは$${A_{i}}$$階と$${B_{i}}$$階を双方向に移動できる
このはしごを用いて最大で何階へ行けるかを求める問題

自分の回答

辺に対して使ったかを判定する幅優先探索みたいな感じで考えてみたけどそこまで行くのに時間がかかり、時間内でまとまり切らなかった
終了後に書いてみたけどTLEしたから根本的に違うか？

公式解説

int main() {
	int n;
	cin >> n;
	map<int, vector<int>> graph;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	queue<int> que;
	que.push(1);
	set<int> S;
	S.insert(1);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (int i : graph[v]) {
			if (!S.count(i)) {
				que.push(i);
				S.insert(i);
			}
		}
	}
	cout << *S.rbegin() << '\n';
}

https://atcoder.jp/contests/abc277/editorial/5209より

そのままだと頂点が$${10^9}$$個になって要素数の上限に引っかかるから、頂点とそこから繋がってる頂点の管理をどうするか思いつかなくて辺に使用判定を入れたけどそうか、$${A_{i},B_{i}}$$で出てきたらそれをmapで入れればよかったのか

なるほど

D - Takahashi's Solitaire

$${N}$$枚のカードを手札として持ち、$${i}$$番目のカードには非負整数$${A_{i}}$$が書かれている
手札から好きなカードを1枚テーブルに置く、その後
・最後にテーブルに置かれたカードに書かれている数を$${X}$$とする、手札から$${X}$$もしくは$${(X+1) \space mod \space M}$$となるカードの中から1枚をテーブルに置く
という操作を任意の回数繰り返し、最終的に手札に残ったカードに書かれている数の総和としてあり得る中で最小の値を求める問題

自分の回答

C問題を考えてる時にチラッと見て難しそうだなって戻ったけどこれ制約で$${A_{i} < M}$$なんだったら$${X}$$の次に出せるのは$${X+1}$$($${X=N+1}$$ならば0)のカードだけだから、少なくとも1枚ある数がどれだけ連続しているかを見て、初期手札の総和から出せるカードの総和の最大を引けばいいのでは？

公式解説

typedef long long ll;

ll s[200005];

int main(void)
{
  ll n, m, a, sum = 0; 
  map<ll, ll> mp;
  
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a;
    mp[a]++;
    sum += a;
  }  
  vector<pair<ll, ll>> vec;
  for(auto p : mp) vec.push_back(p);
  int k = vec.size();
  
  if(k == m){
    cout << 0 << endl;
    return 0;
  }
  
  int p;
  for(int i = 0; i < k; i++){
    if(vec[(i+1)%k].first != (vec[i].first+1)%m){
      p = i;
      break;
    }
  }
  
  for(int i = 0; i < k; i++){
    int j = (p-i+k)%k;
    s[j] = sum;
    if(vec[(j+1)%k].first == (vec[j].first+1)%m) s[j] = s[(j+1)%k];
    s[j] -= vec[j].first * vec[j].second;
  }
  
  ll ans = sum;
  for(int i = 0; i < k; i++) ans = min(ans, s[i]);
  cout << ans << endl;
  
  return 0;
}

https://atcoder.jp/contests/abc277/editorial/5203より

そういう感じだったか
答えの計算のスタート位置を次が出せない数字にしてそこから下がっていくことで処理を統一できてるのかな

なるほど

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