贖罪
A 問題
始めに最大値ではなく総和と誤読する。サンプルが合わなくて気付いたが実装にほぼほぼ変化がなかったのですぐ修正して AC(05:28)
B 問題
始めから距離の条件を満たしていない場合のみ考える。$ S,Tからの距離を計算しておくと$ N個の pair が生えて$ \min(a+d,b+c) + L \le Kを満たすものの個数を数えることとなる。ここまで出来たので何も考えず 2 次元セグ木を持ち出して AC(20:18)
C 問題
問題文を読み、かなり多項式で解けなさそうな見た目をしているので大胆予想「折り返しが発生するのは$ S,G,\min x,\max x
のみであると考えて全通り移動を試すを実装する。提出するもなかなか合わず bit dp を書き 14 点を取る。(1:03:16)
デバッグをしても合わないのでここで一度置いておいて D を見ることにする。
D 問題
とりあえず 50 点を考える。「適当に貪欲をするが、もし次の人が自分のプレゼントしか取れないような状況が生まれるなら調整をする」を書くと通る。(1:54:51)
一度 C に戻って考えるも解法が嘘であることに気付く。なので再度 D を考える。次に小課題 5 を考えると自分だけ孤立している人がいると駄目そうだということが分かる。端の処理を間違えるもすぐ気付き 8 点を取る。(2:32:35)
ここまでやって一度 E を見ることにする。
E 問題
問題を見るが、よくわからない見た目をしている。小課題 1 すら面倒そうな割に時間を取りそうだったのでコスパが悪いと判断して D 問題をやることとする。
D 問題
先程の人が孤立しているを詰めると、$ \lbrack B_i,A_i \rbrackがどの人とも共通部分を持っていない人がいると駄目そうとなる。実際これが正しいことを提出して確認。
よって、それぞれの$ iに対してどこまで左、もしくは右に行けば自分と共通部分を持つ人に出会えるかを二分探索しようとする。この時点で C が解けておらずかなり焦っていたので wavelet matrix を持ち出そうとする。そしてクエリパートでは$ L_i \le j \le R_jかつ求めた区間がクエリの区間を含むものの個数を求める。ここで 2 次元セグ木を持ち出してなんとか対処する。しかし定数倍で落ちてしまった。なんとか気合で定数倍を軽くして 88 点を取る。(3:41:41)
ここでも落ち着けば wavelet matrix や 2 次元セグ木を持ち出さずに済むのだが...
C 問題
残りの時間で C 問題の貪欲を適当に改善したものの提出を繰り返すも最後まで通ることはなかった。
競技終了後は思い出したくもないくらい気持ちが悪かった。この参加記も書かないつもりだったが贖罪の意を込めて書き残しておくこととする。もう二度とこのような不覚は取らない。