競プロ日記

C 単調増加

コード
https://atcoder.jp/contests/abc038/submissions/6927104


最初の提出ではいくつかのテストケースでWAをもらった。
なんでだろうと最大値を考えた場合に、10^5と10^4を書き間違えて1～10^4まで合計してもint型でいけるだろ！って思ってしまったせいで少し時間を食った。
本番ではWAはもちろん避けたいところだけど、こういうミスもするだろうなぁと思うと気が重いなぁ。

まぁさくっと解けて良かったのだが、解説を見てみるとどうも少し違う。
確かに計算結果を答えに加えつつ、それとは別にiの増加ごとに答えを+1するのは少し違和感があったが、数式の理解が自分とは違う感じ。

解説では

D プレゼント

コード
BIT
https://atcoder.jp/contests/abc038/submissions/6942401
LIS
https://atcoder.jp/contests/abc038/submissions/6934327


この問題は完全にお手上げだった。
dp使いそうという、ソートしたら計算量減りそう、という予想は合っていたが、添字に持たせる意味を思いつけなかった。
なんとか思いついたのが、添字に入れ子にする箱の(高さ,幅)のpairのvectorを載せて、対象の箱の高さと幅が、vectorの中でソートした場合の高さと幅が同じインデックスになった場合にdpに1追加する！、なんていうのはあまりにも無理そう。
そもそもこれは漸化式(そもそもなってる？)として入れ子にできるかどうかを判別するだけで、dp[vector]になんてしてしまうとそもそも添字が絶対に被らないからただの全列挙である・・・。

BIT

まずは解説にもあるBIT。
解説を見るとそもそも添字に持たせる意味じゃなくてdpに持たせる意味を変えてきた。
i番目までの箱で作れる入れ子の最大数ではなく、i番目を一番外側にした際の入れ個の最大数とは。
i番目まででなく全体の情報を入れてしまうとdpにならなくないか？、と思ったが、なるほどソートすれば実質i-1番目以内の情報のみで更新できるすごい。

これらの情報のみで実装したらきれいにTLE。
なるほどここでついにデータ構造、競技プログラミングらしくなってきたなと結構テンションが上がった。
BITは分かるようで分からないようでな状態でライブラリとしてクラスを作成したが、やはり書いているうちにかなり理解できてくる。
完全な単体の情報を一部しか持っていないため、更新関数・クエリ関数に求められる条件が組み合わせによって異なることはしっかり理解できた。
結局和を保存するBITと最大値を保存するBITを作成し、今回使用したのは最大値を保存するBIT。

ここからはすぐにAC！、と行きたかったがそうはいかず、BITの使いみちの理解に手こずった。
確かに最大値を素早く取り出したいからBITを使ったものの、結局2重ループになりそうだった。
というのも、dpをBITとして実装し、i番目のdpテーブルを更新するために、j番目(0<=j<i)までのdpから最大値を取り出す、という方向性で考えていたからだ。
BITに持たせる情報を、幅ごとの入れ子の最大数にするというのはなかなか理解できなかった。
要するにjループの情報をそのままBITに持たせられている。

確かな理解を持ってACすることができたが、難易度の高さに対する驚きもかなりあった。
ABCでこのレベルが出るのかと少し自信をなくした。
データ構造というものをそもそも使ったことがなかったためなんとも言えないが、このような使い方が一般的なのかどうか分からない。
この使い方の感覚を慣れで養えるなら良いが、そうでないならつらいものがあるなぁ・・・。
dpはかなりバリエーションがあるらしい中で典型的なdpしか知らないし、その上データ構造を使ったことがないときたら仕方がないのかもしれないが。

LIS

次にLIS(最長増加部分列)。
解いたのはLISが先だが文脈的に後に。
解説を見てもいまいちピンと来なかったので、調べてるうちに見つけた解説とは別解。
LISなんて言葉知らなかったし、知っててもこんなのなんのために計算するんだよと思うこと間違いなし。
この問題でLISが使える理由を理解すると、心からなるほどなぁと思えた。
こういう場面において有効に使える、というのが分かったのはかなりの収穫。
解説に乗っていたのは次のBITを使った方法だが、正直それよりもかなり直感的で納得のいく解法だと感じた。



いやー難しかった。
継続してかないとレベル上げられないな。

それと文章見にくいなーと思ったから見出し機能なんてものを見つけて使ってみた。
多少ましになったかな。