えんじにあ備忘録

脱よわよわエンジニアを目指すブログ

AtCoder Beginner Contest 283 に参加しました＆反省会

競技プログラミング

AtCoder Beginner Contest 283の振り返り

  • コンテスト前にC++の開発環境を入れたコンテナにvscodeからアクセスできなくなり、miでコーディングした
  • A、B問題は解けた
  • A問題：for文で入力の回数だけ乗算する（提出時間04:42）
  • B問題：配列の添字と問題文とのずれに気が付くのが遅かった（提出時間41:15）
  • C問題：入力値を文字列として扱い処理する。２ケースだけWAになった
  • D問題：整数ｊをどう求めるかで手が止まった。入力値を変数に格納し忘れるミスを犯した

A問題

atcoder.jp

考えたこと

  • 答えを１で初期化し、for文で答えにAをかける操作をB回行う

その他

  • 乗算を行う関数が存在する
  std::cout << "pow(2.0, 2.0)  = " << std::pow(2.0, 2.0) << std::endl; // pow(2.0, 2.0)  = 4.000000

https://cpprefjp.github.io/reference/cmath/pow.html

注意*1

C++ における std::pow 関数は float や double などの浮動小数点数型に対応した関数であるため、本問題の制約下では正答を得ることができますが、例えば以下のような大きいケースでは誤差が生じる可能性があることに注意してください。 3の38乗のケース

B問題

atcoder.jp

考えたこと

  • 受け取ったクエリをその場で操作する
  • 配列を利用する

C問題

atcoder.jp

考えたこと

  • Sが64bitを超えるため文字列として扱う
  • 10/100で割る処理は文字列から0を1つあるいは2つ削除する処理とする
  • 配列が空になるまでループさせる

実装例

 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;

その他

D問題

atcoder.jp

考えたこと - 使った文字を管理する問題文で言う箱はmapを使う - ()で括られる文字列を管理するのはstackを使う

入力例ab(cd(efg)hi)を考える
gまで処理を終えた状態では
mapは{a:1, b:1, c:1, d:1, e:1, f:1, g:1}
stackは{"ab", "cd", "efg"}
となっている
最初の)を処理し終えた状態は
mapは{a:1, b:1, c:1, d:1, e:0, f:0, g:0}
stackは{"ab", "cd"}
となっている

実装例

#include<bits/stdc++.h>
using namespace std;

int main () {
    string s;
    cin >> s;
    
    stack<string> stack;
    map<char, int> chars;

    stack.push("");
    
    for (auto c : s) {
        if (c == '(') {
            stack.push("");
        } else if (c == ')') {
            string now = stack.top();
            stack.pop();
            for (auto cn : now) {
                chars[cn]--;
            }
        } else {
            if (chars[c] >= 1) {
                cout << "No" << endl;
                return 0;
            }
            stack.top() += c;
            chars[c]++;
        }

    }   
    
    cout << "Yes" << endl;

    return 0;
}

実装は次の動画を参考にした

【よくわかる】ABC283 D問題 Scope - YouTube

*1:https://atcoder.jp/contests/abc283/editorial/5440