今週の競プロ（2024/04/08〜14）
今週の復習
復習のルール
【平日】は、過去にACできなかった問題を適当に選んで復習する。
【土日】は、復習した問題をACできるかチェックする（週末は平日に復習した問題に集中する）。
今週、復習した問題は以下の7問です。
ABC338-E Chords
ABC344-D String Bags
ABC344-E Insert or Erase
ABC345-C One Time Swap
ABC346-D Gomamayo Sequence
ABC346-E Paint
ABC347-C Ideal Holidays
ABC338-E Chords
下図のように、円環を点1, 2Nの間で切って直線にして、弦を曲線にしてみます。
そうすると、括弧列の対応関係の問題（※1）を応用した感じにみえました。
括弧列の対応関係の問題は C++ だと stack が便利なので、同じような要領でACできるようになりました。
※1 括弧列の対応関係の問題は、以下のような問題があります。
・競技プログラミングの鉄則 演習問題集 B51 Bracket
・アルゴ式 データ構造 7章：スタックとキュー Q5. 括弧列の対応関係 (1)
・アルゴ式 データ構造 7章：スタックとキュー Q6. 括弧列の対応関係 (2)
・アルゴ式 データ構造 7章：スタックとキュー Q7. 括弧列の整合性判定
ABC344-D String Bags
この問題は読んだ瞬間にDPだとわかりました。
しかし、実装はなかなか難しいかったです。
「文字列Tの中なかに文字列Aが含まれてる場合は文字列Tの何文字目からですか？」と聞かれるとスッと実装できますが、DPだと思ってしまうと、途端に難しく感じます。
週末のチェックでは、無事ACできました。
どなたかが「DPは機械的に表を埋めるイメージ」と言っていましたが、その感覚が掴めてきたような気がします。
ABC344-E Insert or Erase
過去に「前」と「後ろ」を管理する問題をやった記憶があったので、この問題も「前」と「後ろ」を管理するんだなと方針はすぐにわかりました（過去のどの問題かは忘れてしまいました）。
しかし、実装に手こずりました（今も手こずっています）。
数列内で最初と最後の要素が絡んでくると、訳がわからなくなります。
落ち着いてやりたいです。
ABC345-C One Time Swap
kyopro_friends さんの解説（解説はこちら）で復習してACできるようになりました。
S自身が作れる分として答えに 1 加えるのを忘れていて失敗したときもあったので、注意が必要です。
サンプルを試すことで気が付くことがあるのでサンプルってありがたいです。
ABC346-D Gomamayo Sequence
解説では「問題の性質を利用して前後から文字列を扱う方法」と「dp により前からのみ文字列を扱う方法」を紹介していただいていましたが、「問題の性質を利用して前後から文字列を扱う方法」でACできました。
一致するところで切って、前の文字列と後ろの文字列で考えるとか、なかなかできない発想だなぁ。
ABC346-E Paint
「後ろから考える」問題。
日があくと忘れてしまう発想。
決まったところとか個数の管理はそんなに難しくないので、ACできました。
ABC347-C Ideal Holidays
解説を読んでもなかなか理解できなかった問題。
「なんで『 > B 』なん？」という点がなかなか理解できませんでした。
snukeさんが「<= A」のパターンで実装してくれたコード（コードはこちら）の方がしっくりきました。
実際に週末にチェックしたときも「<= A」のパターンでACできました。
ABC349に参加しました
Unratedですが、ABC349に参加しました。
結果は、ABCの3完（6WA）で 7016 / 11977 でした。
C問題でやらかしてしまいました。
「部分列」ではなく、単純に使用している文字の数で考えてしまいWA連発でした。
次回もがんばります。
今日のAtCoder NoviSteps
今日の段階での私のAtCoder NoviStepsはこんな感じです。
4QまでACできましたが、3Q以降、まだまだ解説ACが多いです。来週はこの3Qの解説ACの問題を中心に復習します。
この記事が気に入ったらサポートをしてみませんか？