今週の競プロ（2024/04/15 〜 21）
今週の復習
復習のルール
【平日】前日にACできなかった問題を復習する。月曜日の場合は、過去にACできなかった問題を適当に選んで復習する。
【土日】平日に復習した問題をACできるかチェックする（週末は平日に復習した問題に集中する）。
今週、復習したABCの問題は以下の9問です。
ABC325-C Sensors
ABC328-D Take ABC
ABC330-C Minimize Abs 2
ABC335-D Loong and Takahashi
ABC340-C Divide and Divide
ABC342-C Many Replacement
ABC344-D String Bags
ABC344-E Insert or Erase
ABC349-C Airport Code
ABC325-C Sensors
8方向で連動しているセンサを連結成分と見て、連結成分の数を数えるという感じ。
連結成分の数が絡む問題は、Union-Findを使うとやりやすい場合が多い。
ABC328-D Take ABC
空の文字列に前から1文字ずつ追加していきます。
文字列が3文字以上だったら、末尾3文字を取り出してABCのチェックします。
ABCだったら取り出したまま。
ABCじゃなかったら文字列に戻します。
こんな感じの問題やサンプルですと、文字列全体を見てしまうので、1文字ずつ追加して調べてみるという発想を忘れないようにしたいです。
ABC330-C Minimize Abs 2
x を固定して場合分け。
数学の問題みたいな問題も苦手だなぁ。
ABC335-D Loong and Takahashi
中央からぐるぐる回るイメージ。
・パーツを配置します。
・次に配置する方向を決めます。
・次に配置する場所へ移動します。
という感じに分割して実装した方がコードは長くなりますが、あせらずに実装できそうです。
ABC340-C Divide and Divide
メモ化再帰。
こんな感じの問題で、Nyaanさんの解説にあるような漸化式がパッと書けないので、練習が必要です。
ABC342-C Many Replacement
$${c_i}$$ に対する $${d_i}$$ を更新していくイメージ。
$${c_i}$$ に対する $${d_i}$$ をchar型（C++）で受け取った場合うまくいかなかったので、stringで受け取りました。
入力をchar型で受け取るのは避けた方がいいなぁ。
ABC344-D String Bags
先週できなかったので、再度復習。
選ぶ、選ばない系のDP。
DPのところはスムーズに実装できるようになってきた感じがしますが、文字列の比較もスッと書けません。
実装量が多そうだなと思うと「何か楽な方法はないか」と考えてしまうので、それはやめよう。
計算業が大丈夫そうなら多少長くても確実に実装できる方で。
ABC344-E Insert or Erase
先週できなかったので、再度復習。
前と後ろを管理する問題。
頭の中がこんがらがってきたら、紙に書いて整理してから実装する。
結局これが早いです。
ABC349-C Airport Code
先週のABCで大失敗した問題を復習。
・大文字の文字列を小文字の文字列にして返す関数
・s に t が部分列（連続じゃなくていい）として先頭から何文字含まれているかを返す関数
が過去に作ってあったので、それを使ったら楽になりました。
ABC350に参加しました
Unratedですが、ABC350に参加しました。
結果は、ABCの3完（2WA）で 5929 / 12847 でした。
A問題では、ABC000を考えていなくて1WA。
C問題では、ソートの途中経過を表示するパターンだと問題を勘違いしてて、長い間悩んでいました。
その結果、実装あせって1WA。
まぁ、なかなかうまいこといきませんが、次回もがんばります。
今日のAtCoder NoviSteps
今週は3Qの問題をACできるようになろうと復習していたので、3Qが埋まりました。
来週は2Qの問題を中心に復習します。
この記事が気に入ったらサポートをしてみませんか？