})();「dwangoプログラミングコンテスト」予選問題解説2015年1月24日に開催された、dwangoプログラミングコンテスト「dwangoからの挑戦状」予選問題の解説です。問題Cが、ドワンゴエンジニアからの出題でした。ご参加いただいた皆さま、ありがとうございました。頂点iに遷移し、そこから期待値E(i)回で頂点1に遷移する。これを全ての頂点について足し合わせる。個の都市があり、各都市ごとに本選出場者とその都市の会場に入る本選出場者数が与えられる。会場に入る人数の合計は、出場者数の合計と一致。うまく移動させることで本選出場者数と会場に入る人数が一致するようにしたときの移動距離の合計として考えられる最小値を求めよ。最初に、都市同士の移動を、隣り合う都市同士の移動を複数回繰り返したものとして考えます。各都市にいる人数を数列で表すことにします。いう形に変換する問題となります。コストは両都市の距離。コストは両都市の距離。組み合わせとなります。間の移動を無効にした場合)を考えます。人)のように左から順に決定していくことができます。この決め方で行われる移動が、直線の場合の最適解になります。※途中で人数が負の数になる場合がありますが、動かす順番をうまく決めることでこの状態を回避できます。間の移動量を定めることで、直線の場合に帰着することができます。移動量として考えられるすべての値を試すことを考えます。[13,1,2,-­‐6]→[4,10,2,-­‐6]→[4,1,11,-­‐6]→[4,1,0,5]という移動よりも多くコストが掛かります。すべて右に数を送っていて、送る量が後者のほうが少ないことから分かります。動量を固定して、直線の場合を解くという方針で解を求めることができます。計算量で解くことができます。さらなる得点を取るために、最初の数列にひと工夫加えます。