[AtCoder 参加感想] 2019/06/16:ABC 130

  A B C D E F
問題文
自分の提出
結果 AC AC AC AC AC AC

スポンサーリンク

全体感想

79分で6完、2ペナルティ。44位でした。

Fが個人的には直近のABCコンテストの中で最難だった。というか割と変な解き方してしまったかもしれないw 解けている人はたくさん居るので、多分考察が甘いんでしょうね…。

問題C – Rectangle Cutting

必ず、長方形の面積の半分が実現できます。長方形の中心を通る直線で切ればよいです。

・それ以外にないこと
中心の片側に切断線が出来てしまっているとする。平行移動して中心まで動かすことを考える。

わざわざ最大値きくの…易しすぎて不安になって検証に時間をかけてしまうやつ。
こういうのはテストケースでは現象を隠していることもあるけれど、今回はテストケースも露骨。

問題D – Enough Array

左端か右端を決めてあげて、もう片方の境界を探索するゲーム。
尺取り法の練習問題という想定でしょうか。

大量の値に対して境界値の一覧を取得するには、np.searchsortedを利用することができます。
pythonでループ回して尺取法するよりも高速です。不慣れでしたが、今回はこれを使って実装してみました。いずれにせよ左端・右端の処理周りとか注意点が多くて、ひとつひとつ確認しながらのろのろ実装。この辺はまだ経験値不足な感じが。

問題E – Common Subsequence

A, Bの片方の最終値を固定して漸化式みたいなのを立てようとする。
全然分からないなーと思って制限確認したら、$O(N^2)$ でも許されることが分かる。
$(n,m)$を最後にとるとすると、
\[
dp[n,m] = \sum_{0\leq i < n}\sum_{0\leq j < m}dp[i,j]
\] という種類の漸化式が得られる。これ昨日も見たやつだ。累積和と同時に更新していくdpだ。(ただし2次元版)。
$A[n] \neq B[m]$のときはdpの値は更新はしないが、dpの累積和は更新をかける。これを忘れていてバグ取りに時間がかかった。

問題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できました →  
凸関数の積で、微分係数も巨大にならないので、問題特化な方法をコーディングするまでもなかったということですね。

コメント

  1. You made some decent factors there. I regarded on the internet for the difficulty and found most individuals will associate with together with your website.

  2. […] 6/16:レーティング2039。黄に到達する。 […]

タイトルとURLをコピーしました