Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ABC136 反省会

AtCoder Beginner Contest 136 - AtCoder 最悪すぎる。Dで発狂して終わってしまった。今週も4完以上するという目標を失敗してしまい、絶望している。 C おれは最初の要素だけは低くすることが無条件で良いので低くして、あとはindex=1から順に、広義単調増加…

ライツアウト系の基本を学ぶ

ライツアウト系の問題は、地道にシミュレートすると100%間に合わないので、フリップするとはその問題でいうとどういう意味を持つのか?ということを考える必要があります。そこまでの累積和的なものだったり、パリティだったり、問題の性質そのものを利用し…

大手前プロコン2019 反省会

AとCしか解けなかったです。Eは惜しかった。Bは問題文の誤読。Fも方針は見えていたので、個人的にそう悪いとは思っていない。G以降には着手すらしてない。全体的に問題文がいつもより長い気がした。 B B - 駒 (Pieces) 一度も動かされたことがない駒を1つ選…

二分探索を一般化するライブラリを作りました

二分探索の一般化 www.rustforbeginners.com で話したとおり、二分探索はTFの列に出現する最初のTを探す操作に他なりません。従って、インデックスを入力として、ブール値を出力とする関数を与えてあげれば、最初のTないしはFとTの境界を出力するという関数…

二分探索の本質を考える

二分探索について頭を整理します。 二分探索の応用事例 ソートされた列から最小値を探す 半分全列挙の相方を探す あるxについて成り立つか問いを設定して(貪欲に計算出来ることが多い)、問題条件にあったxを探す 二分探索とは?問い系の二分探索が本質 問…

ローリングハッシュ題材にした問題

ローリングハッシュとは? 蟻本上級のテク。決してエロい名前ではない。 文字列S(長さn)の中に文字列T(長さm)が存在するかを愚直に調べると、O(nm)かかる。これをO(n)程度にしたい。 そこで、文字列に対するハッシュ値を使うことにする。衝突は、諦める。競…

LISを題材にした問題

配列内の数の関係性について議論している問題はよく出されていて、LIS (Longest Increasing Sequenceの略) が題材となってるものはLISだと気づかないことが多すぎる。 この記事では、LISについて復習して、LISを題材とした問題例をいくつか挙げることにする…