5完。ゴミ。めちゃくちゃ嫌な気分になり声を上げた。
A - Tomorrow
3桁の整数みたいなものだと思って頑張って繰り上がりをやる。
B - Buy One Carton of Milk
難しそうに見えるが、最小金額を達成するときどの種類も買うのはNパック以下なのでO(N^3)で全探索できる。久しぶりに王道のB問題来たな。
C - Sum of Numbers Greater Than Me
0から10^6までの各整数について、その整数と等しいA_iたちの和を求める。次に後ろから累積和を作る。これで、その整数以上のAの要素の和がわかるようになり、解けた(便宜上長さ10^6+2のvectorを使う)。ソートで解こうとすると、インデックスを持つ必要があったり同じ数の扱いを考える必要があったりするが、値毎に考えれば楽だ。
D - Tile Pattern
飛ばすべきだった。そもそもコンテスト前に配点を見たときからこういう展開は想定していたし、やってることがコンテスト中にやりたいような実装ではなかった。なんか余裕ぶって実装してしまった。飛ばせばいいんだよ。その必要がなかったとしてあとで解けばいいだけだし、今回のように気力を振り絞って実装して時間が減り疲れた状態でEFに臨むのはデメリットが大きい(Eでは(これが原因かはわからないが)不注意でREを出したし、Fを考える時間が減った)。結果的に、今回飛ばさなかったことは結果に大した影響を与えなかったと思うが、そういうことじゃない。さっき言ったデメリットがある可能性がそれなりにあるなら飛ばすべきだった。
N*Nのパターンが繰り返されている。N*Nの大きいタイルに区切って見て、クエリに対しては真ん中の大きいタイルたちと4辺と4隅を足して答えればいい。ここで、整数に対し指定方向で最も近いNの倍数を求めるライブラリが役に立つ。2次元累積和を求め、指定長方形内の黒マスの個数がわかるようにしておく。クエリに対しては、大きいタイルを切り出す。あとは9個に分かれた領域それぞれの黒マスの個数を求める。ここまでは簡単だったが、ここから相異なる9行を書かなくてはならないのが嫌すぎる。サンプルが合わず、しばらくデバッグしてEへ。このとき、Cの提出から32分が経っていた。
大きいタイルの左上の計算が間違っていた。大きいタイルからの距離ではなく、大きいタイルの左上隅の位置をNとしたときの自分の位置を求める必要があった。符号反転してNを足す。これでサンプルが通ってAC。
解説を見て。あー累積和を任意の位置の長方形に対応させるのではなく、答えを足し引きで求めればさっきの9行は4行に減らせるのか。典型だけど思いつく余裕がなかったね。完全に力不足(その典型を全然わかってなかったし、今回の実装を楽に書く力もない)。いつも言ってるけど、結果には納得できて、問題は貴重なコンテスト中の時間の使い方だ。これを思いつかないなら飛ばすべきだった(Fがどうしてもわからなくて戻ってくるならそれでもよし)。嫌な気分になるのは結果が悪いことによるところが大きいと思うので、そこは分けて考える必要がある。嫌な気分になるなら、ちゃんとした立ち回りをした上でなれ。
E - Set Meal
ソートされていれば考えやすいのでそうやって考えるけど、実際はソートされてない列のインデックスを使う必要があり、悩ましい(最悪、c,dをソートされた順に付け替えればいいが、できればその手間は避けたい)。Lの小ささを使うことを考えると、主菜を全探索することを思いつく。副菜側がmexみたいになって難しいかと思うが、単に(インデックス付きで)ソートして大きい順に見るだけでよさそうだ(一見N*Mだが高々L回しか失敗しないのでO(N+L)回のチェックで済む)。禁止されたペアは主菜毎にunordered_setで持つ。
F - Palindrome Query
ここで、Manacherを知らないことによる弱さが出る。この問題でManacherやその考え方が使えるのかはわからないが、どちらにせよ時間を使ってしまう。わからないから。しばらくして、ローリングハッシュで解けそうだと気づく。ライブラリを持ってくるが、更新ができない。セグ木を使えばできそうだが、自分のライブラリが理解できない。その後も繰り返しここに書いた同じようなことを考えていたが、あと30分あっても話にならないような感触だった。終わってみると、1時間あってもダメそう。ローリングハッシュでわからなかったところは、どうやって逆数を求めることを回避しているかということだったが、ハッシュを 0, 1, 12, 123, 1234 のように持ち、23が欲しいなら123から1の100倍を引くという処理をしていた。そう書いてあったけど理解できなかった。となると、単純にセグ木ではできない。遅延セグ木を使うか、ハッシュの持ち方を変えるか、というところ。それで本当にできるかはまだわからないが。
(追記)解説見たらローリングハッシュが想定でやや意外。セグ木を使う場合、やはり逆元(昨日逆数じゃない言葉を使いたいと思ったけどわかんなかった)は要らない。幅(何文字分か)の情報を持つ必要があり、これを持たずに済ます方法を考えていたが煩雑になるのであきらめた。結局丸一日だらだらとやっていた(やっていなかった)。解説のように逆向きも持つようにすれば定数倍改善になるが、汎用性を重視して普通の更新できるローリングハッシュを2本持つことにした。コンテスト中に考えたのは、5文字の区間なら最初の2文字と最後の2文字を比較するものだったが、解説にあるように5文字と5文字を比較すればよかった(無駄に(本当に無駄に)複雑な方針へ行ってしまうのほんと弱い)。方針が決まれば実装は簡単。時間はかかったけど楽に書き上げた。