43分で4完と調子は悪くなかったものの、変にイキった実装をしたり考察がやや甘かったりでA問題・C問題で1WAずつ食らったため反省点が多かった。E問題もあと5歩くらいで本番中のAC獲得にこぎ着けられそうなところまで考えが及んだこと、本番終了後には緑diffという判定結果になっていたこと、解説には読んで理解できることしか書かれていなかったこともありこの回で本番中の5完に失敗したのは頗る悔しい。引き続き勉強をして是非とも今年中には5完を達成したい・・・。
※特に断らない限り、本記事の記載は0-indexedを前提とする。
＜A問題＞
↓問題のページ↓
またしても「A問題にしては難しくない？」と思わされる（ABC371のA - Jiroより確実にマシではあるがそれでも難しい寄りと感じる）一問だった。入力される各\(T_i\)は、直前からの経過時間ではなく初期状態からの累積経過時間である点に注意して、問題文通りに実装してAC獲得。最後に飴を受け取った時点における初期状態からの経過時間を\(L\)として、\begin{align}i=0 \lor T_i - L \ge C\end{align}である場合に答えを1つ数え上げ、\(L\)の値を\(T_i\)で更新していく。
＜B問題＞
↓問題のページ↓
円環上を移動させていくという個人的にはあまり経験のない状況設定のためやや手間取った（同じような人が多かったのかB問題にして既に灰色の相当上位に来ている）。それでも結局は\(N, Q\)ともに最大で\(100\)しかないため問題文通り愚直に手を動かせばそれだけでAC獲得。動かせる方の手を時計回り・反時計回りに動かすのを両方試し、より手数が少ない方を採用して、その手数を合計していけば正解。
＜C問題＞
↓問題のページ↓
例として、大きさがそれぞれ\(3,30000\)である2つのおもちゃと大きさが\(40000\)である1つの箱がある状況を考えてみる。この状況において、大きさが\(3\)のおもちゃを箱に入れるという選択をする意味は全くない（結局は追加で買う箱が無駄に大きくなるだけである）。というわけで、それぞれのおもちゃに対し、それよりも大きいまたは等しい大きさを持つ箱のうち、大きさが最小であるものを割り当てるのが最も効率が良くなる。\(A\)を予め昇順に並べておき、追加で買う箱の大きさが\(x\)であるとして、\(B\)も昇順に並べる。\(B\)の要素数が\(N\)となっている状況において、\(i=0, 1, \dotsc , N - 1\)について、\(A_i \gt B_i\)なる\(i\)が1つも存在しない場合、\(x\)は追加で買う箱の大きさとして適切であり、存在するのならば不適切である。このような\(x\)はいくらでも小さくして良いわけではないため、ある\(x_{th}\)以上の大きさならば適切だが、\(x_{th} - 1\)以下ならば不適切であるような境界値\(x_{th}\)が存在すると言える。したがって二分探索を使って片付く問題とわかったのでこれを実装してAC獲得。二分探索の上限値\(U\)を適当に\(2 ^ {60}\)などで初期化しておき、\(U\)が初期値から動いていなければ\(-1\)を出力すれば良い。
＜D問題＞
↓問題のページ↓
有向グラフ・閉路検出という個人的には経験値が少ない2つの要素をどちらも絡めている問題ではあるが、見た目ほど難しくはなかった。頂点\(0\)から有向辺のみを辿って行き着くことができる頂点のうち1つを\(v\)とし、\(v\)が頂点\(0\)へと伸びている有向辺を持つのならば、与えられるのは重みのないグラフであるから、\((\)頂点\(0\)から\(v\)への最短距離\() + 1\)こそが、頂点\(v\)を使う場合の最短閉路長となる。以上より、入力で与えられるグラフについて、特定の頂点を出発地点とした場合における各頂点への最短距離が必要な情報となるため、頂点\(0\)を出発地点とした幅優先探索を行えばその結果を使うだけで答えが分かる。頂点\(0\)へと伸びている有向辺を持つような頂点\(v\)が初めて現れたら\((\)頂点\(0\)から\(v\)への最短距離\() + 1\)を出力して終わりで、一度も現れなければ\(-1\)を出力させてAC獲得。頂点数、辺の数がそれぞれ\(N, M\)のグラフに対して幅優先探索を行うので計算量は\(\mathcal{O}(N + M)\)となる。
＜E問題＞
↓問題のページ↓
もし\(A\)の各要素が昇順に並んでくれていれば、\(p = K - 1, K, \dotsc , N - 1\)として、\(S\)に含まれる値のうち最大であるものを\(p\)と決めると\begin{align}\max_{i \in S} A_i\end{align}の値は\(A_p\)と定まるため、\(p\)よりも小さな\(q\)を\(K - 1\)個上手く選び出す（これらの\(q\)を\begin{align}q_0 , q_1 , \dotsc , q_{K - 2}\end{align}とする）ことによって、\begin{align}\sum_{i \in S} B_i = B_p + \sum_{j = 0} ^ {K - 2} B_{q_{j}} \tag{1}\end{align}の値を最小化できれば、全ての\(p\)に対して\begin{align} \left( \max_{i \in S} A_i \right) \times \left( \sum_{i \in S} B_i \right) = A_p(B_p + \sum_{j = 0} ^ {K - 2} B_{q_j} ) \tag{2}\end{align}をそれぞれ計算していき、それらの最小値こそが各テストケースに対する答えとなるというところまでは自力で考え付くことができたのだが、その先がどうなるのか見出すことができず無念の撃沈となった。
まず、\(A\)の各要素が無秩序な並びになっている場合にどうすればいいのかが分からなかった（本問で問われている値を求めるためには元の\(A, B\)から添字の対応関係を崩してはならず、こういった状況設定に対しての経験値が足らなかった）。これに対する答えはとんでもなく単純で、\(i = 0, 1, \dotsc , N - 1\)について、\((A_i , B_i)\)の組を一塊として、この塊を1つの要素とするリストを昇順に並べ直すだけである。こうすれば、元の\(A, B\)から添字の対応関係が崩れることなく\(A\)を昇順に並べることができる。
続いて分からなかったのは、式\((1)\)の値を効率良く最小化する方法である。こちらもまた一度理解してしまえば呆れ返るほどに明快であり、\(B_0 , B_1 , \dotsc , B_{p - 1}\)の中から小さい値を優先して\(K - 1\)個取り出すだけである。これら\(K - 1\)個の値および\(B_p\)を持っているようなデータ構造\(X\)を用意し、\(K\)個の合計値を別の変数に確保しておこう。また、\(p\)の値を\(1\)だけ大きくした際には、既に\(K\)個の値を保持している\(X\)から、含まれる最大値を効率良く捨て去ることができる性質を持っていることが望ましい。したがって、\(X\)として最も適切なのは優先度付きキューであることが分かる。本問のように、最上位・最下位の\(K\)個を合計した値を効率良く計算するために優先度付きキューを用いるという発想はどうやら典型らしいので次は絶対に本番で通したい。具体的な実装は以下のようになる（以下では\(A,B\)を、添字の対応関係を保ったまま\(A\)が昇順になるよう並べ直しているものとする）。
1)優先度付きキュー\(Q\)および式\((1)\)計算用の変数\(U\)を用意し、\(B_0 , B_1 , \dotsc , B_{K - 2}\)を\(Q\)に突っ込み、これらの合計値を\(U\)とする。
2)テストケースに対する答え\(ans\)を\(\infty\)で初期化し、\(p = K - 1, K, \dotsc , N - 1\)に対して＜2)反復部分＞の処理を行う。
＜2)反復部分＞
\(B_p\)を\(Q\)に突っ込み、\(U\)に加算する。この状況で式\((2)\)の右辺を計算し、結果が\(ans\)よりも小さければ\(ans\)をその値で更新する。その後、\(Q\)から最大値を取り出して捨て去り、その値を\(U\)から減算する。
＜2)反復部分終わり＞
3)この状態における\(ans\)がテストケースに対しての答えとなる。
計算量を雑に見積もると、各テストケースについて、\(A,B\)を適切に並べ直すことおよび\(Q\)に要素を追加または\(Q\)から要素を削除することに\(\mathcal{O}(N \log N)\)くらいの時間がかかり、全テストケースに対する\(N\)の合計値が\(2 \times 10 ^5\)以下であることが保証されているという制約なので十分間に合う。
