160606 簡易解説
連続するjの数、oの数、iの数を求めておきます。j>=o<=iならレベルoのJOI列が生成されます。JOIの順に来ないこともあるのでその場合はちゃんとリセットするように。
英語で驚きますが、やってることは、左足右足を使うゲームで、左足と右足が交差してはいけない(同じ列はOK)というルールを適用した際、何回「同じ足を連続で動かす」ということが発生するか？というのを数えればOKです。再帰関数を作って、「左足始まり」「右足始まり」の両パターンで、ルール違反になる場合は同じ足を連続で動かして値を1足しておく、ということをすれば良さそうですね。
R<=10がヒントです。2^10通りなら間に合うので、それでどの行をひっくり返すかを全探索します。その後、各列についてせんべいを見ていき、その列をひっくり返すべきか否かは分かるので、それで答えを出します。
都市は一直線に並んでいるので、どう訪れるかは1通りです。なので訪れ方でどの路線を何回使うかは一意に求まります。問題は、それを数える方法で、これは累積和、imos法を使うと時間内に求まります。詳しくはググッて。で、数え終わったら、ICを買うべきか否かを不等式使って判別して答えに足せばOK。
状態を3層に分けます。1層目は無料券を使っていない状態、2層目は無料券を使っている途中、3層目は無料券を使った後です。そうすると、1層目、2層目からは次の層の状態へ無償で行けて、また1層目、3層目からはコストを払うことで同じ層の状態へ行けます。また、2層目は無料券を使っている最中なので、2層目でゴールに辿り着いてもゴールしたことにはしません。と考えると、「何層にいて」「どの場所にいる」という情報を持った際の層0場所0から層0場所n-1もしくは層2場所n-1への最短経路問題になります。
ここで出てくるのはグラフ理論と**Dijkstra法(ダイクストラ法)**です。詳しくはググるか蟻本を見た方が理解が深まると思いますが、ここでは簡単に説明します。
グラフとは高校数学でやるグラフではなく、「頂点」「辺」で表された離散構造です。頂点と辺しかありません。辺にはコストが付いていることもあります。
頂点と辺で表せるものはたくさんあります。枝分かれしていく木もグラフに見なせますし、再帰する様子を図示すればそれもグラフに、また現実世界では地図やニューラルネットワークなどもグラフっぽいです。
さて、グラフですが、これはコンピュータがかなり扱いやすいデータ構造となっています。そのため、情報科学における研究対象として何年も研究されています。
そのうちの1つが「最短経路問題」です。地図の例を出しましたが、頂点を街や駅、辺を道や路線と見なして、辺のコストとして長さやかかる時間を振っておけば、最短経路を求める問題が生まれますね。
そこで出てくるのがDijkstra法です。Dijkstra法は「単一始点最短経路問題」を解くアルゴリズムです。基本的な考え方は「未確定の一番近い頂点を見て、その頂点から新しく状態を作って、その頂点を確定済みにしよう」というものです。動的計画法です。
このためにpriority_queueというデータ構造を使ったりします。詳しくはググってください。
今回の問題では、距離はかかるお金、状態(頂点)は「層」「場所」を同時に保持したもの、を使えば、Dijkstra法を用いることで、層0場所0からの最短経路が求まります。
こちらは少しむずかしいです。まず題意を理解しましょう。
問題はこうです。時間が経つと順番に島(頂点)が沈んでいきます(使えなくなります)。
救助したいのですが、どこから救助するか決まってないので、その時点で使える島はすべていくつかの橋で行き来できるようにしておきたいです。
そのために橋を建設するのですが、できるだけコストは抑えたいです。
また、「すべての生きている島を繋げない」と判断した場合は、以降は一切橋の建設をしません。←重要
このようなルールで、どれだけのコストを橋の建設にかけることになるでしょう？最小値を求めよ。
以上が問題です。
さて、用語をいくつか出します。
「すべての頂点が連結である木」を**「全域木」**といいます。木というのはグラフの一種で閉路を持たないグラフのことです。閉路があったら一つ取っ払ってもすべての頂点は連結のままなので、基本的にこの概念を考えるときは全域「木」と呼ぶようです。
さて、この全域木の内、辺のコストの総和が最小のものを**「最小全域木」と呼びます。さらに、この最小全域木を効率よく求めるアルゴリズムはいくつかありますが、私のおすすめはKruskal法**です。
Kruskal法は、Union-Findというデータ構造を用いて行います。まずすべての辺をコスト順にソートしておきます。次に、1つずつ辺を見ていき、それを採用するか否かを判別していきます。ここで、Union-Findを用いて、辺の両端が別の連結成分であれば、その辺を採用し、それらを連結していきます。そうでなければ不採用。こうしてできあがった辺集合が木になっていれば、それが全域木。という具合です。
ここで出てきたUnion-Findは、連結かどうかを管理してくれる超高速データ構造です。これもググるか蟻本で。このデータ構造でできることは「連結集合の連結」「同じ連結集合に属しているか否かの質問」の2つです。
これらを用いて問題を解きます。
まず重要とつけたところを考えておきましょう。これ以降は考えてはいけないからです。
そのためには、沈む順とは逆順で島を追加していって、その島を結ぶ辺をすべて採用していきます。Kruskal法は一旦忘れてください。でもUnion-Findは使います。すると、その時点で全域木が作れるかどうかが判別できます。これを記録しておきます。
次にその記録を前から見ていきます。一番最初に作れないと判断した瞬間からその後はすべて「作れない」としておきます。
最後に全域木を作っていきます。先ほど同様島を逆順で見ていきます。島が追加されたら辺も追加し、「全域木を作れる」ならば、辺集合をソートして、Kruskal法を適用します。なお、Union-Findは順番に島が増えるだけなので使いまわせます。また一度使った辺も使ったままのためリセットしなくて良いです。
こうして、最小全域木を順に作っていくことで、求められている答えが出ます。
