AtCoder Beginner Contest 283

OKU

結果

A - Power:AC(3:10)
B - First Query Problem:AC(6:18)
C - Cash Register:AC(19:32)(1ペナ)
D - Scope:AC(48:28)(1ペナ)
E - Don't Isolate Elements:提出無し

A - Power

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

自分の回答

int main(){
  int A, B;
  cin >> A >> B;
  int X = pow(A, B);
  printf("%d\n", X);
}

そのまま

公式解説

省略

B - First Query Problem

長さ$${N}$$の数列$${A=(A_{1},A_{2},…,A_{N})}$$と$${Q}$$個のクエリが与えられ、クエリを与えられた順に処理する問題
クエリは以下の2種類のいずれか
・1 k x:$${A_{k}}$$の値をxにする
・2 k:$${A_{k}}$$の値を出力

自分の回答

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

  int Q;
  cin >> Q;
  int q, k, x;
  for(int i = 0; i < Q; i++){
    cin >> q;
    if(q == 1){
      cin >> k >> x;
      A[k - 1] = x;
    }
    else{
      cin >> k;
      printf("%d\n",A[k - 1]);
    }
  }
}

そのまま

公式解説

省略

C - Cash Register

00,0,1,2,3,4,5,6,7,8,9のキーがあるレジスターで整数$${S}$$を表示するには最低何回キーを押せばいいかを求める問題

自分の回答

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

  int ope = 0, zero = 0;
  for(int i = 0; i < S.size(); i++){
    if(S[i] == '0'){
      zero++;
    }
    else{
      ope++;
      if(zero % 2 == 1){
        ope += (zero / 2) + 1;
      }
      else{
        ope += zero / 2;
      }
      zero = 0;
    }
  }
  if(zero % 2 == 1){
    ope += (zero / 2) + 1;
  }
  else{
    ope += zero / 2;
  }
  printf("%d\n", ope);
}

文字列で読み込んで先頭から文字を見て行って0以外なら操作回数をプラス、0なら次0以外が出て来るまで0の個数を数えて0以外が出たらまとめて回数をプラス

最初は2文字目から見て行って今見ている文字とその前の文字を見ていく方法で書いたけど偶数個の0で終わるときの処理を忘れてWA
そこの処理も面倒そうだったから回答の方法にチェンジ

書いている時ですらきれいにできないかと思ってはいたが後から考えれば

  int ope = 0;
  bool zero = false;
  for(char c : S){
    if(c == '0'){
      if(zero){
        ope++;
        zero = false;
      }
      else{
        zero = true;
      }
    }
    else{
     ope++;
     if(zero){
       ope++;
       zero = false;
      }
    }
  }
  if(zero){
    ope++;
  }

これでよかったか

公式解説

int main() {
    using namespace std;

    string S;
    cin >> S;

    int ans = 0;
    while (!empty(S)) {
        const auto back{S.back()};
        S.pop_back();
        if (back == '0' && S.back() == '0')
            // S が 100 の倍数なら、さらに 1 文字消す
            S.pop_back();
        ++ans;
    }
    cout << ans << endl;

    return 0;
}

https://atcoder.jp/contests/abc283/editorial/5428より

Sのケツ1文字をbackに移してbackとSのケツが共に0ならSのケツを追加で削除、その後操作回数をプラスか
そしてそれをSが無くなるまで繰り返す

なるほど

D - Scope

英小文字、「(」「)」からなる文字列のうち
・英小文字を全て削除する
・連続する「()」がある限りそれを削除する
この操作をした後、空文字列となる文字列を「良い文字列」とする
良い文字列$${S}$$が与えられ、先頭から順に以下の操作をする
・それが英小文字ならば箱にその文字を入れる、ただしすでに同じ文字がある場合処理を終了する
・「(」ならば何もしない
・「)」ならばその「)」を末端とした良い文字列になるまで遡り、その間に入れた文字を箱から取り出す
この操作を最後まで完了させられるかを判定する問題

自分の回答

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

  set<char> box;
  map<int, set<char>> floor;
  int now = 0;
  for(char c : S){
    if(islower(c)){
      if(box.count(c)){
        printf("No\n");
        return 0;
      }
      else{
        box.insert(c);
        floor[now].insert(c);
      }
    }
    else if(c == '('){
      now++;
    }
    else{
      for(char d : floor[now]){
        box.erase(d);
      }
      floor[now].clear();
      now--;
    }
  }
  printf("Yes\n");
}

今どの階層にいるかを記録して、どの階層でどの文字が入れられたかを階層をキーとしてcharのsetをバリューとしたmapで記録
後は先頭から見て操作していけばおｋ

)が出た時の階層下げを忘れてて1回WA

公式解説

int main() {
	string s;
	cin >> s;
	int n = s.size();
	vector<vector<char>> v(n);
	vector<bool> used(256);
	int now = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '(') now++;
		else if (s[i] == ')') {
			for (char c : v[now]) used[c] = false;
			v[now].clear();
			now--;
		}
		else {
			if (used[s[i]]) {
				cout << "No\n";
				return 0;
			}
			v[now].push_back(s[i]);
			used[s[i]] = true;
		}
	}
	cout << "Yes\n";
}

https://atcoder.jp/contests/abc283/editorial/5441より

やってることは一緒だけど箱の部分そんなやり方があるのか
charは数字として扱えるからそのままvactorの位置指定に使ってboolで箱に入っているかを記録

なるほど

E - Don't Isolate Elements

各要素の値が「0」もしくは「1」である$${H}$$行$${W}$$列の配列$${A}$$が与えられ、任意の要素の上下左右いずれかの位置に同じ値が存在しない要素を「孤立した要素」とする
配列$${A}$$の任意の行の値を全て反転する操作を好きなだけ行い、全ての要素が孤立した要素でなくすることはできるか、可能ならば最低何回の操作で行えるかを求める問題

自分の回答

とっかかりすら掴めなかった

公式解説

#define rep(i, n) for (int i = 0; i < (n); i++)
constexpr int inf = 1000000010;
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<int>> a(h, vector<int>(w));
	rep(i, h) rep(j, w) cin >> a[i][j];
	vector<vector<vector<int>>> dp(h, vector<vector<int>>(2, vector<int>(2, inf)));
	dp[0][0][0] = 0;
	dp[0][0][1] = 1;
	for (int i = 1; i < h; i++) {
		rep(j, 2) {
			rep(k, 2) {
				rep(l, 2) {
					vector<int> x(w, -1);
					if (i != 1) x = a[i - 2];
					if (j) rep(m, w) x[m] = 1 - x[m];
					vector<int> y = a[i - 1];
					if (k) rep(m, w) y[m] = 1 - y[m];
					vector<int> z = a[i];
					if (l) rep(m, w) z[m] = 1 - z[m];
					bool ok = true;
					rep(m, w) if (x[m] != y[m] && y[m] != z[m] && (m == 0 || y[m] != y[m - 1]) && (m == w - 1 || y[m] != y[m + 1])) ok = false;
					if (i == h - 1) {
						rep(m, w) if (z[m] != y[m] && (m == 0 || z[m] != z[m - 1]) && (m == w - 1 || z[m] != z[m + 1])) ok = false;
					}
					if (ok) chmin(dp[i][k][l], dp[i - 1][j][k] + l);
				}
			}
		}
	}
	int ans = inf;
	rep(j, 2) rep(k, 2) chmin(ans, dp[h - 1][j][k]);
	cout << (ans == inf ? -1 : ans) << '\n';
}

https://atcoder.jp/contests/abc283/editorial/5433より

まず根本として$${i}$$行目が孤立するかは前後の行のみに依存し、上から順に操作するかしないかを考えていくとすると$${i}$$行目の要素が孤立するかは$${i+1}$$行目の操作で決まる、また、全ての要素が孤立しないならば$${i}$$行目を操作するときには$${i-2}$$行目までのすべてが孤立していない必要がある
そのためdp[i行目まで][i-1を操作したか][iを操作したか]の操作回数で動的計画法、$${i-1}$$行目に孤立している要素があるならば-1とする

この理解で合ってるのかな

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