0.はじめに
Cは、初見簡単に解けそうに感じたけど
意外とてこずりました。
1.A - Power
A、Bをインプットして問題通りに表示するだけの簡単な問題でした。
https://atcoder.jp/contests/abc283/submissions/37488139
2.B - First Query Problem
若干ややこしい感じではありましたが
Aのリストへクエリーごとに更新＆表示するだけの
簡単な問題でした。
https://atcoder.jp/contests/abc283/submissions/37494709
3.C - Cash Register
これも簡単やな！と思って実装したら
最後が0の時にWAとなってしまいました。
油断大敵。
【考え方】
Sを頭から見ていく
0以外→変数ansに1加算
0の時、ジャッジを次の数字に繰り越し
→0の次が0の時ansに1を加算
→0の次が0以外の時ansに2を加算
https://atcoder.jp/contests/abc283/submissions/37498322
- D - Scope
テスト時は試行錯誤したけどTLEを解消できずに時間切れでした。
2022/12/27追記
その後細かい調整をして提出しなおしACをゲット
考え方
変数
・英小文字のボール状態を保持する辞書dictを定義
-辞書に存在しない場合は箱にボールが入っていない
-辞書に存在かつ、値が0の時は箱にボールが入っていない
-辞書に存在かつ、値が1の時は箱にボールが入っている
・現在何番目の”（）”の中にいるかを表す変数LVを定義
・現在までの”（）”の最大多重度を表す変数MLVを定義
・”（）”の多重度ごとに出現したアルファベットを保持する2次元表Lを定義
処理
1)文字列Sを1文字目からチェックしていく
1-1)S[i]が"("の時
1-1-1)LVに1加算
1-1-2)LV>MLVの時
1-1-2-1)MLVにLVをセット
1-1-2-1)Lに空配列を追加
1-2)S[i]が")"の時
1-2-1)L[LV]配列内のすべてのアルファベットについてdictの値を0にする
1-2-2)L[LV]配列を空にする
1-2-2)LVを1減算
1-3)S[i]が"("でも")"でもない時(アルファベットの時)
1-3-1)S[i]が辞書に存在し、かつ値が1の時
1-3-1-1)気絶条件を満たすので、”No”を出力しPG終了
1-3-2)L[LV]にS[i]を追加
1-3-3)dict[S[i]]に1をセット
2)気絶せずに文字列Sのチェックが終わったら、”Yes”を表示
NGだった考え方１と大して変わらない気もしましたが、
”変数preから当該アドレスまでの文字について辞書の値を0にする”
の部分をさかのぼってチェックして消すのと配列に持っておいて消すので
だいぶ処理回数に差が出るのだなぁと思いました。
あとは、試験時にうまくいかなかったのが、配列内に配列を追加の部分が
MAXの場合新規配列を追加というロジックが入っていなかったからでした。
他にも応用が利きそうなので覚えておかないと。
https://atcoder.jp/contests/abc283/submissions/37577568
NGだった時のメモ
考え方１
文字列Sを頭からチェック
→"("の時
アドレスを変数preに保存
→")"の時
変数preから当該アドレスまでの文字について
辞書の値を0にする
→上記以外
当該文字が辞書にあるかをチェック
→あった場合、値をチェック
→値が1の時”No”表示
PG終了
上記以外
→辞書の当該文字の値に1をセット
最後までチェックが終わったら”Yes”を表示
余裕でTLEな上に、おそらく、(a(bc)a)みたいなときにエラーを判断できなさそう。
考え方２
”（”毎にレベル分けし、レベル毎に文字を配列に格納
”）”がきたら当該レベルの配列はクリアし1レベルを下に戻す
的な感じで実装。
→2次元配列の存在チェックがうまくいかずに終了。
そして、それでもTLE
その後回答を見たら、考え方は間違ってなさそうなのですが
ちょっと実装がうまくいってなさそうなので
時間が出来たら見直してみよう・・・。
以上。