昨日のABCがまぁ惨憺たる結果で結構ショックを受けておりました。
Cはもう仕方なかったとして、D問題の二分探索は*1類題をしっかり思い出してそのACコードまで並べながらやっていたのにボロボロであまりにもあんまりだ、ということでこちらはまだ具体的に出来る対策がありそうだということでちょっと時間を割いてみました。
ケンカ中の恋人か何かかな？にぶたんの気持ちが分からない…
— あのぶる+@隙あらばサウナに行きたい🦥㌠ (@thatblue_plus) 2023年9月9日
ABC319終了時点の当人のスペック
- 二分探索の基本的な考え方は理解しており、後述する記事にある「テスト何点だった？」の例題であれば適切に質問を組み立てられる
- Rubyの組み込み関数である
Array#bsearchやArray#bsearch_indexで解決できるようなタイプであれば特に引っかかることなく記述できる
というわけで何をしたか
この記事を読みました。とても読みやすく、大変分かりやすかったのでお勧めです。
どのくらい分かりやすかったかと言うと、私が過去3回やって3回とも自力で解けなかった典型90のYokan Partyがようやく解説を読まずに解けたくらい分かりやすかったです*2。
紹介されているスタイルを「めぐる式二分探索」と呼ぶそうなのですが、二分探索の評価周りをバグらせにくくてすごく良いと思いました。
実際にやってみた問題
どちらも何とか解説を読まず解くことができました🎉
その1
最初にもう一度昨日のD問題を解きました。
どうやら解説のコードが概ね近いスタイルだったみたいで、細かいところがよりRubyっぽくなった以外は昨日のコードとあまり大きな違いはないです。
その2
次はその類題と判断した、因縁のYokan Party。
改めてちゃんと自分のコードで解けるようになってみて、やっぱり類題とみてよい内容だと思いました。目の付け所はよかったんだけどな…
これでやっと羊羹を美味しく食べることが出来そうです(？)
