Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】AtCoder Beginner Contest 351 - 参加記 | 茶コーダーが解くAtCoder

AtCoder コンテストまとめ ABC プログラミング

コンテスト時間: 2024-04-27(土) 21:00 ~ 2024-04-27(土) 22:40 (100分)

A - The bottom of the ninth

Difficulty: ???
解答時間: 3:08

2チーム A, B が野球の試合をしたときの各回の得点が9回表まで与えられるので、 B が9回裏に何点を取れば A に勝てるかを求める問題。
2チームの現在の得点を計算し、その差 + 1 を出力すればよい。

B - Spot the Difference

Difficulty: ???
解答時間: 3:06

各マスに英小文字が書かれた2つのグリッド $A, B$ が与えられる。両者を比較したときに1か所だけ書かれている文字が異なるマスがあるので、そのインデックスを出力する問題。
グリッドのマスは最大で $100 \times 100 = 10000$ なので、愚直に2重ループを回して1個ずつ比較していけばよい。

C - Merge the balls

Difficulty: ???
解答時間: 19:13

$i$ 個目の大きさが $2^{A_i}$ である $N$ 個のボールと空の列がある。以下の操作を $N$ 回繰り返した後の、列に残っているボールの数を出力する問題。
$i$ 回目の操作 :

$i$ 個目のボールを列の一番右に付け加える。
列にあるボールが1つ以下ならばこの操作を終了する。
列にあるボールのうち右から1番目と2番目の大きさが異なるならば操作を終了する。
列にあるボールのうち右から1番目と2番目の大きさが等しいならば、2つのボールを取り除き、「取り除かれた2つのボールの大きさの和」の大きさのボール1つを列の一番右に付け加える。その後、手順2に戻り以降の手順を繰り返す。

まず、 $2^A + 2^A = 2^{A+1}$ であることから、ボールの大きさを底を2とする対数で管理してよい。
列をstackで管理し、手順3, 4について、加えるボールの大きさをnextとして以下のような再帰関数f()で対応する (大きさを結合する操作を再帰して、最後にstackに反映する感じ。~~うまく言語化できませんでした。~~) 。

void f(stack<int> &st, int next)
{
    if (!st.empty() && st.top() == next)
    {
        int temp = st.top();
        st.pop();
        f(st, temp + 1);
    }
    else
    {
        st.push(next);
    }
}

結果

Performance: 743
Rating: 572 → 590 (+18)

良い感じで3完できて嬉しい。