競プロ典型90問めも
★2
004, 010, 022, 024, 027, 067, 078：特になし
033：整数値の切り上げについて、
$ \lceil \frac{a}{b} \rceil = \lfloor \frac{a-1}{b} \rfloor + 1 $
055：定数倍の見積もりはちゃんとしよう。
061：dequeはランダムアクセスも$O(1)$でできる←これどういう仕組なんだ？←リングバッファでできるが、C++のSTLの実装は違うらしい(何？)
★3
007, 014, 016, 020, 046, 048, 050, 052, 064, 069, 075, 079, 084：特になし
002：制約を見て一番楽な方法を考えるべき。
018：誤差はよくわからないけど、とりあえず定数の値は細かくしておいて良くのがベター。
032：INFはオーバーフローするかもしれないので、安易に大きい数を突っ込まない。最大値を見積もって、なるべく小さい数を使う(intに収まるならint)。
038：整数$ a,b,M $を扱うとき、
$ ab \leq M \Leftrightarrow a \leq \lfloor \frac{M}{b} \rfloor $
が成り立つ。
044：負数の剰余は((a % p)+p) % p
076：円環を列にして二倍にすると便利。
082：modをとるときの割り算には御用心。
★4
001, 003, 012, 026, 028, 042, 058, 063, 070, 072, 085：特になし
008：アルファベット順に並んでいないが、アルファベットたちにある順番を決めたい場合は、その順番通りに並べた文字列を作ると楽。
043：特にないんだけど、条件式ミスって沼った。想定解は01BFSらしいけどよくわからんBFSして通してしまった。
058：やたら多い操作のときは天才$O(1)$かダブリング？(要検証)
★5
006, 013, 021, 029, 030, 051, 086, 087：特になし
036：マンハッタン距離の性質いろいろ調べたら知見得られた。これは知らないと解けなそう。参考：最近の 45 度回転事情 - Lilliput Steps
037：スライド最小値？
039：解けはしたけど、無駄な考察+実装をした。主客転倒を心に刻め。
056：解けはした。無駄に再帰関数作って時間かけた。FORでいけるならFORを使おう(あるいは再帰を速く書けるようにしよう)
060：LISをセグ木でゴリ押した。おそらく空間計算量がひどいことになってる。dpの実装について、dp[i]:=(最初からi個について~)と統一すると良いかも。
068：クエリ先読み。問題を分割するのはまず考えるべき。この問題の場合は、Ambigousかどうかと、求値するのとで分けれる。簡単にわかる方は別で実装することもできるから、とりあえずどかしておくべき。
073：さっぱりわからなかったし、解説理解に時間かかった。どういう情報がわかればよいのか、最終的にほしい結果の情報だけでなく、それを知るための情報を考えてまとめるべき。
081：解けた。二次元累積和を無思考でかけるようになりたい。参考： 累積和を何も考えずに書けるようにする！ - Qiita
★6
015, 054, 074：特になし
006：解けなかった。３つのうちの真ん中固定は典型らしい。２点を固定して、残りの１点をどう選ぶのが最適か、で考えていたのと、単純な偏角での角度の計算の仕方を思いつかなかったのが敗因。１点固定(N通り)、残りのN-1点の固定した点を基準とした偏角を調べる+ソート+最大値調査で$O(N log N)->O(N^{2} log N)$。実装でも沼った。
011：解説チラ見してしまった。区間スケジューリング問題忘れていた。この問題に限らず、2N通りが考えられる場合、「ある組み合わせについて、その組み合わせは条件を満たすか？」という小問題を考えてから、その手法を応用するのは大切かも。参考になるかも： O(2^n)から計算量を減らす問題 - けんちょんの競プロ精進記録
031：実装バグらせまくったけど、これが解けたのは嬉しい。参考： Grundy数（Nim数, Nimber）の理論
045：部分集合の部分集合全体の個数は3N。これは賢い実装を知らないと解けないかも。参考：O(3^N)で部分集合の列挙をする実装 - 宇宙ツイッタラーXの憂鬱
049：解説をガン見して通した。難しい。
区間の操作をする問題は、隣りとの要素との差などを見れば、区間の端だけを考えればよくなる。今回の場合は区間bit反転なので、区間内ではbitの違いは変わらない......。と連想すれば思いついたかも？(自信ない)
057：いろいろな記事を漁って解けた。xorはmod 2の世界での足し算であることに気をつけて、連立１次方程式を解く。参考： Gauss-Jordan の掃き出し法と、連立一次方程式の解き方 - けんちょんの競プロ精進記録
062：解説AC。全然頭が動いていないのに解説チラ見してしまった。反省。
080：解けた。桁DPのような$O(ND 2^{N})$解法を通してしまったが、どうも想定解ではないらしい。桁DPを書く際、メモ化再帰を実装しようと思ったが詰まってしまった。再帰関数自体に慣れていない節があるため要練習。
083：難しい。スターグラフのようなときにTLEすることは想像がついたが、それを深堀りしていくとは思わなかった。
想定解の平方分割ゴリ押しなら、次数の大小でわけて小さい問題にする、クエリ平方分割なら、答えを出すフェーズと更新するフェーズで分けて考えるように、小さい問題に分けて最後に組み合わせることを意識するのは大事。だが、この問題で最初からこのことをを意識しても想定解が思いついたとは思えない。
分けて考えるということについて、平方分割についてのこの記事が参考になった：セグメント木をあきらめた人のための平方分割 - くじらにっき++
088：鳩の巣原理。実装はこたつがめさんの提出を参考にした。( Submission #24070087 - 競プロ典型 90 問 )
