[AtCoder 参加感想] 2019/11/16:ABC 145

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

スポンサーリンク

全体感想

45分6完1ペナルティで31位でした。

PAST検定というものがあるようです。サンプル問題を見る限り、ちょうど「ABCコンテスト3回を300分」という想定をしておけばよさそうです。最上位ランクではABCコンテストでいかに満点付近を安定させるかが問われるということで、日々のコンテストでもしっかり頑張っていきましょう。

今回のセットは、Eまでが易しめ、Fが一歩抜けて難しい感じがしました。全体的に設定がすっきりしていて、好きセットでした。

Fを最初に取り組んで26分。上を見るとキリがないですが、主観的には、このレベル帯の問題をきちんと短時間でまとめあげられることが増えてきている実感があり、とても良い感じです。

おまけ:コンテスト中のノートの実物

今回はいつもよりページ数少なめにおさまったこともあり、撮影してみました。
dpテーブルを手作業で埋めていますが、理解も整理できますし、計算が合わないときのデバッグにおいてこれと照合すればよいので、割とアリだと思います。総合的に見て、正解時間の期待値を下げてもいないのではないかと。

問題C – Average Length

「パスごとに色んな線分の和を求めて、合計してください」という問題です。いや、正確には平均ですので、合計したあとパスの個数で割り算します。

素直に解釈すれば、たくさんのの和を

・パスに含まれる線分に対して、長さの和を計算する
・すべてのパスについて足す

という2段階に分けて計算しています。総和の対象を別の切り口でとらえてみます。

・各線分に対して、その寄与を考える:自分の長さ × それを含むパスの個数
・すべての線分について足す

記号的に書けば、$P$ をパス、$S$ を線分として、

\[\sum_{P}\Bigl(\sum_{S\in P}(Sの長さ)\Bigr) = \sum_{S}\Bigl(\sum_{P\ni S}(Sの長さ)\Bigr)\] という変形をしているとも解釈できます。2つのものに紐づく量についての集計の、集計順序を変更してみる感じですね。

各線分に対して、それを含むパスの個数は簡単に計算できるので、あとは容易です。$N$ が大きくなったり、適当な制約条件がついた(例えば「$x$ 番目は頂点 $y$ を通る」など)場合にも計算しやすそうですね。

この、和の順序の変更を使う問題は、ABCコンテスト上位~の問題でしばしば登場します。私は割と得意のような…数学寄りの人は得意な印象があります。逆に苦手な人は、意識して選択肢に入れていくとよいでしょう。

※ 今回の問題では、確率・期待値の目線で「すべての線分が等確率で登場する」と思ってあげるとより分かりやすいです。より汎用性のある和の形での解説を記述してみました。

※ 全探索でもOKです。pythonだと、XY = [(0,0), (1,0), (0,1)] のような点のリストを用意して、

for p in itertools.permutation(XY):
    # p は、点の順列
    path_length = 0
    for (x1,y1), (x2,y2) in zip(p, p[1:]):
        path_length += ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** .5
    # path_length が求まった。経路長計算後の必要な処理をここに

といった要領で、順列に対する全探索を行うとよいでしょう。

問題D – Knight

平面上の線形独立な2ベクトルに沿った移動なので、移動可能ならば、それぞれの使用回数は一意に定まります。

・使用回数が負のときは答が $0$ → やらかしました、悲しい。

問題E – All-you-can-eat

注文順序は、ラストオーダー以外関係ないことはすぐに分かります。それでもラストオーダー以前の注文方法の数が指数オーダーで、とても厳しそうな気がします。

・最適解をとってみる
・最適解に仮定できる構造を探す
・探索空間が小さくなったら、既知の手法に当てはまる(dpなど)
という考察手順を経ました。この考察手順自体はかなり重要度の高い典型の1つで、多くの問題で扱われています。

今回の場合、

・食事順は、満足度には関係ない。
・食事順は、ラストオーダーに間に合うかのみに関係している。
・したがって、食事対象を固定したとき、食事順は、食事時間の短い方からとしてよい。

ということが分かります。したがって、結局、

・全ての食事を食事時間でソートしておく。
・ある食事 $k$ がラストオーダー前最後の食事であるとする。ラストオーダーでは、食事 $k+1,k+2,\ldots$ から最適なものを選ぶ。

というような注文方法のみを考察対象とすればよいです(私の解法)。

より良くは、「ラストオーダー後の食事$k$」を軸に分析した方がスマートで、

・食事 $0, 1, \ldots, k-1$ で、ラストオーダーまでになるべく満足度を稼ぐ
・食事 $k$ をラストオーダー後に食べる。

と見るとよりすっきりします。前者の課題は典型的なナップサック問題です。

問題F – Laminate

まずは、
・最小の操作回数
・$H_i$ を書き換えるということ
についての理解を深めないといけません。
最小の操作回数は簡単で、行ごとに見ると、いくつの塊が生存しているかを見るだけです。ただ、行がたくさん ($10^9$ 個)あるのでもう少しよく分かりたいです。なるべく列ごとの情報に切り分けたいと思った結果、次のように理解できました。
列ごとの塊を数える(図の赤線)ためには、その左端(図の緑)を数えればよいです。したがって、ある列が左の列からはみ出している部分の長さを足し合わせることで計算できます。
次に、列の高さの変更ですが、これも実は簡単です。変更が1手しか行えないならば、例えば左右列どちらかと一致させてます。ある列 $x$ を、列 $x+1$ の高さとそろえた場合、今後列 $x+1$ の高さをいじりたくなったら同時に列 $x$ も変更しなおすようにします。これは結局、「列 $x$ と列 $x+1$ がまとめて 1 つの列と扱えている」状態です。さらに言い換えると、「列 $x$ が無き物であるとして扱っている」ことになります。つまり:
高さを変更する列 = 完全に削除する列
としてあげても良いことになります。だいぶ問題がスッキリしてきました。
課題:
・K個以下の列を削除して、「左の列からはみ出している部分」の総和(以下コスト)を最小化せよ。
最小化の対象が、どのようなデータから計算できるかを考えると、
・直前の生き残っている列(の高さ)、および、その列を立てた時点での総コスト
が分かれば計算できそうです。あとは、削除している列の個数も必要そうなので、それも含めて dp します。
実装の際(あるいは考察の際)には、「削除している列の個数」よりも、「生き残している列の個数」を持った方が扱いやすかったです。

dp[n,k] = (生存させた列の合計個数が $k$, 最後に列 $n$ とした場合の最小コスト)
として、自然にdp更新していけば、$O(N^3)$ で解くことができます。

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