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

全体感想

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

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

今回の場合、

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

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

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

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

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

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

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

問題F – Laminate