イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

89. 今日解いた問題（2022.03.25）

プログラミング AtCoder

今日解いた問題についてまとめます。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

 

問題一覧

 

自分の解法など

D - 8 Puzzle on Graph

頂点数 9、コマ数 8 で互いに異なる頂点にいるという制約があるため、あり得る状態数は {}_{9}P_{8} = 9! 通りです。これはおよそ 10^5 なので、単純な探索で十分間に合います。最短手数を見つけたいので BFS でよいでしょう。

既に知っている状態は省くのですが、ここで状態の持ち方を工夫してみました。各頂点と 10 進数の桁を対応させて、その頂点に存在するコマの番号を持たせました。これで整数として状態を扱えます。目標状態は 123456780 です。

 

D - An Invisible Hand

入力例からの考察で分かるように、「最大利益を上げられる町」が焦点になります。各町での売買数に制約は無いため、 T は無意味な条件となっており、計算に使いません。

最大利益を上げるには、町 i と町 j（ i \lt j）について A_j - A_i が最大となるようなものを見つけて、町 i で買って町 j で売れば良いです。これを見つければよいのですが、いくつかポイントがあります。

まず、単純な探索では計算量的に間に合わないです。上手くやって O(N) に収めたいです。次に、購入に最適な町・売却に最適な町はそれぞれ複数存在する可能性があります。入力例 2 が分かりやすいですが、この例では最大利益は 10 となり、これは「町2 で買って、町3 で売る」「町4 で買って、町5 で売る」の2通りで達成できます。

なお、 A_i は相異なるという条件があるので、複数の町で買えて1つの町で売れる…というパターンは考えなくてよいです。ちなみに、私はいまこの制約に気付いたので、同じ A_i があっても対応できるアルゴリズムで通してしまいました。

今回の問題は、以下のような方法で O(N) で答えを求められます（厳密なアルゴリズムではなく、方針的なものを書いています）。 A_i を先頭から順に見ていきます。

  1. A_i の最小値 A_{min} を記録する
  2. A_i - A_{min} の最大値 D_{max} を記録する。更新された場合、 ans = 1 とする。 A_i - min = D_{max} であれば ans = ans + 1 とする。
  3. 最終的な ans が求める答え