ABC240

6完。難しい問題だと思ってもみんな通してる(DEF辺り)。どうなってんの。

A - Edge Checker

けっこう難しい。結局、差が1か9であるという条件を書いたが、これ必要条件なのは図から明らかだけど十分条件にもなっているかは自信がなかった。本当は、0始まりに直して(直す必要ないね)mod 10で差が1か-1みたいなことをしたかった。

B - Count Distinct Integers

std::setに突っ込む。最近Bでアルゴリズム要求してくるよね。と思ったらa_iは大きくともNが小さいから2乗で行けるのか。a_iがでかい時点でそっち方面は諦めてしまった。

C - Jumping Takahashi

簡単なDP。Cで出されると、いかに短時間で書くかという戦いになるので、やはり考察力をフルに使うことになる。最大で10000までしか行かないので配列はフルに確保して、2つのジャンプをできるだけまとめて扱えるように、配るDPにした。行き先が10000以下であることを使って、行ける場所からだけジャンプすれば配列の範囲内になるからforの範囲をあまり考えなくていい。

(解説を見て)std::bitsetは思いつかなかったな。

D - Strange Balls

歯ごたえのあるD。何が何個連続しているか持ちながらシミュレーションすればいい(削除回数は全体でO(N))と思いきや、削除したあとに何が何個連続しているかを知る必要がある。現在の筒の中のボールの個数毎に記録を残しておくことにした。

(解説を見て)と思ったらスタックにはボールじゃなくてボールの種類と個数を入れるのか。いやー煩雑すぎる実装にしてしまった。実際15分使わされたし、初手ダメなほうへ行ってしまうのなんとかしたい(なんとかなるんか?)。

E - Ranges on Tree

かなり難しそうな見た目だが、意味がわかれば簡単。葉に番号を振っていけばいい。DFSで訪れた順に、葉に長さ1の区間を割り当て、親には子たちの区間をくっつけたものを割り当てる。これで条件を満たすし、葉同士に同じ場所を割り当ててはいけないので最小にもなっている。子たちの区間の合併が連続した区間になりそうだけど確信の持ち方がわからなかった。オイラーツアーを思いつかなかった。

F - Sum Sum Max

かなりしんどい。要するに累積和の累積和。最大値は2*M^2程度に収まるので64bit整数で大丈夫。2回積分して2次関数にまでなるのが厄介。最大値が境界だけとは限らず、上に凸な放物線のてっぺんという可能性もある。まず、境界を頑張って求める。次に、長さy_iの区間でBがどう変化するかは4通りに分類できる(最初が正か最後が正か)。境界は区間の最後だけ見ればよく、区間の最初は見なくていい(必要がありそうなやつは前の区間の最後より小さくなっている(ただし、最初に0がある作りではないので1個目の区間だけ最初も見る))。あとは、Bが正から負に変わるやつだけ。どこで0以下になるかは難しそうだと思ってビビっていたが、割り算するだけだった。しかしきっちりやる余裕もないので、前後3(全部で7箇所)(1以上y_i以下にクリップする)を見て最大値を更新する。提出してACで本当によかった(ミスがあったら直せる気がしない)。

G - Teleporting Takahashi

問題をよく読んで、さすがに簡単すぎないかと思って書いてみたら2乗だった。これを高速化するのか、別のアプローチがあるのか。色々考えたけどわからなかった。基本の復習にはなった。Gを考える時間が残っていてよかった。