昨日 10/18、atcoder ABC428に参加しました。
ジャッジ運用の変更に関するトラブルのためか、開始が21:30と30分遅れでスタートしました。
結果は、A・B問題の2完でした。
C問題は、スタックを自前の配列とポインタ変数で管理していたため、バグを混入してしまいました。
反省点として、スタックは素直に vector 配列を使い、push_back() / pop_back() で実装していれば防げたと思います。
🅰️ A問題
小学生高学年で習う速度算のような問題。
決められた距離を、人が「一定時間走って止まる」を繰り返す場合、どのくらい時間がかかるかを求める内容でした。
ループ処理を使って、力業で実装しました。
思ったより、提出に時間がかかってしまいました。
🅱️ B問題
問題の概要は、文字列の同じ長さの部分文字列をすべて取り出し、最も出現回数の多い部分文字列とその出現数を求めるというものです。
解説でも触れられていましたが、部分文字列を辞書（map）で管理するのがポイントでした。
実装の流れは次の通りです。
// 部分文字列の出現回数を辞書で管理 map<string, int> dic; // 部分文字列の取得 string t = s.substr(i, k); // 出現数が最大のものを出力 for (const auto &[key, value] : dic) { if (value == maxv) cout << key << " "; } map の利用により、
出現回数のカウントと辞書順での出力を簡潔に実現できました。
🅲 C問題
クエリに応じて '('・')' を追加・削除し、
常に括弧列として成立しているか（正しいペアになっているか） を判定する問題でした。
例
-
ケース1：
( ( ) ( ) )→ Yes -
ケース2：
( ( ) ( )→ No -
ケース3：
( ) ) (→ No
主なポイント
-
括弧の追加・削除をスタックで管理する
-
'('と')'に応じてカウンタを増減させる -
不正な
')'が入った場合（例：ケース3の3文字目）は、
その位置を記録しておき、その部分が削除されるまでは常に "No" を出力する
私は当初、スタックを配列とポインタ変数で管理していましたが、
間違えてポインタ変数を char 型で定義していたため、WA（不正解） となりました。
時間内にバグを見つけられず、終了後 ChatGPT に投げたところ、
一瞬で間違いを指摘してもらい、ポインタ変数を long に変更すると AC（正解） となりました。
やはり、スタックは一般的な vector 配列（もしくは文字列）と push_back() / pop_back() を使うのが安全ですね。
🏁 まとめ
8月3日以来、久しぶりの AtCoder 投稿でした。
先週は安全確保支援士試験の前日だったため参加を控えましたが、
それ以外はほぼ毎週参加しています。
安全確保支援士試験も終わったので、しばらくは AtCoder に集中して、アルゴリズム力をしっかり鍛えていきたいと思います。
📈 成績推移
-
8/2 時点（ABC417）Rating：511
-
10/18（ABC428）Rating：550 （※9回参加）
満足はしていませんが、着実に上がってきています！