| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
79分で6完、2ペナルティ。44位でした。
Fが個人的には直近のABCコンテストの中で最難だった。というか割と変な解き方してしまったかもしれないｗ 解けている人はたくさん居るので、多分考察が甘いんでしょうね…。
問題C – Rectangle Cutting
必ず、長方形の面積の半分が実現できます。長方形の中心を通る直線で切ればよいです。
・それ以外にないこと
中心の片側に切断線が出来てしまっているとする。平行移動して中心まで動かすことを考える。
わざわざ最大値きくの…易しすぎて不安になって検証に時間をかけてしまうやつ。
こういうのはテストケースでは現象を隠していることもあるけれど、今回はテストケースも露骨。
問題D – Enough Array
左端か右端を決めてあげて、もう片方の境界を探索するゲーム。
尺取り法の練習問題という想定でしょうか。
大量の値に対して境界値の一覧を取得するには、np.searchsortedを利用することができます。
pythonでループ回して尺取法するよりも高速です。不慣れでしたが、今回はこれを使って実装してみました。いずれにせよ左端・右端の処理周りとか注意点が多くて、ひとつひとつ確認しながらのろのろ実装。この辺はまだ経験値不足な感じが。
問題E – Common Subsequence
全然分からないなーと思って制限確認したら、$O(N^2)$ でも許されることが分かる。
\[
dp[n,m] = \sum_{0\leq i < n}\sum_{0\leq j < m}dp[i,j]\] という種類の漸化式が得られる。これ昨日も見たやつだ。累積和と同時に更新していくdpだ。（ただし2次元版）。
問題F – Minimum Bounding Box
最初の考察
x座標、y座標分解して推移を追いたい。x座標だけに注目すると、左移動・不動点・右移動の3種類の点がある。それぞれについて最大値・最小値を計算すればよいので、計算のために持っておくべき$x$ 座標は最大でも$6$ 個までだということが分かる。
そこから先がなかなか進まない。局所的には1次関数になって、$6$ 点の位置関係によって式が変わる感じ。まともに扱おうとすると、めっちゃくっちゃ場合分けが多くなりそうで、死が見える。
仕方がないので、「局所的に1次関数」以上の理解を放棄した方針を考える。
切り替わりのポイントも、$6$点の間の座標の位置関係が入れ替わるところだから、せいぜい$15$箇所程度しかない。$x, y$をあわせても、状況が変わる可能性がある時刻はせいぜい$30$個だ。（実際にはもっと少ない）
結果関数の形が変わるところも変わらないところも含め、変化の可能性がある点を全て書き出す。
あとは、各区間内で局所的な問題を解けばよい。
$x$ の幅が$x_1$ から $x_2$ まで等速で変化し、$y$ の幅が$y_1$ から $y_2$ まで等速で変化するとする。このとき、左端を$t = 0$, 右端を$t = 1$ となるように線形変換すると、面積関数は
\[f(t) = (x_1 + (x_2-x_1)t)\cdot (y_1 + (y_2-y_1)t)\] と書ける。この係数は全て計算可能。ここから先は scipy.optimize を使おうと思ったが、簡単だったのでそのまま解く実装をした。
無計画なコーディングをしたため、コピペ三昧である。案の定、コピペに起因するミスがいくつかあり、2WAを出した。4方向とも点が存在するとは限らないところなども、それなりに実装難だと思う。
（解説を見た後）
面積関数 $f(t) = (at + b)(ct + d)$ の最小化についてですが、$t \in [0,1] \implies at+b, ct+d > 0$ というような条件が保証された2次関数です。この場合、下に凸になる場合も含めて最小値が$t=0$ または $t = 1$で実現されることが分かります。なるほど、だから端点だけ見れば良いだけですか。
あとは、「局所的には1次関数」以上の情報（減少・定数・増加と推移）を見るともうちょっと簡潔になるのかな？
（後日）コードを整理。面積関数が各点に対して $O(1)$ で計算出来るようになってしまいさえすれば、局所的な区間に分けるまでもなく、scipy.optimize を呼ぶ形でACできました → ■
凸関数の積で、微分係数も巨大にならないので、問題特化な方法をコーディングするまでもなかったということですね。
