裏紙

ほぼ競プロ、たまに日記

CERC 2016 D - Dancing Disks

問題

gym

問題文

問題概要

ハノイの塔のような、いくつかの棒と、それに積み重なった輪っかを考える。

棒は6行、6列の36本の棒が立っている(上からr行目、左からc行目の列の棒を棒(r,c)と呼ぶことにする)。 輪っかは全部でn個あり、大きさはすべて異なる。輪っかには小さい方から順に1,2,3,...,nと番号をつける。

次のようなパズルを考える:

はじめ、n個の輪っかは棒(1,1)に任意の順番で積み重なっている(下からi番目には輪っかd_iがある)。これらを棒(6,6)に大きさがソートされた状態(大きいのが一番下、小さいのが一番上、つまり上から1,2,3,...,nの順)になるように移動させたい。1回の操作で出来るのは、ある棒を選び、上からk個をとりだして、そのまま下の棒か右の棒に移動する(棒(i,j)からは棒(i+1,j)または棒(i,j+1)に移動できる)ということである。

nとはじめの状態dが与えられるので、このパズルを解く操作列を出力せよ。解は存在すると仮定して良い。

  •  1 \le n \le 40000
  •  1 \le d_i \le n
  •  d_iはすべて異なる(つまり順列)

イデア

簡単な例を考えてみる。nが少なかったらどうかを考えてみると、4*4の棒があったときに、15個の輪っかを運びたいとする。

f:id:imulan:20181019054312p:plain

そして、空いている15マスのところに1箇所ずつ輪っかを運ぶ場所を指定して、(手間ですが)山の上から順番に1つずつ指定された場所に運ぶ。

f:id:imulan:20181019054542p:plain

あとは、これをいい感じの順番に右下に回収していけばソート完了になるのが想像できる。

ということで、こんな感じで棒がいっぱいあればソートは出来ることがわかる。ただ、1つの棒を1つの輪っか専用にするのが明らかに無駄な感じがする。

そこで、次のように同じ場所を2つの輪っかで共有するような方法を考えてみる。 今度は輪っかが22個ある。

f:id:imulan:20181019055137p:plain

そして、ごちゃごちゃのままではあるが、この山を輪っかの大小を基準に小さい方を右へ、大きい方を下へ運ぶ。

f:id:imulan:20181019055338p:plain

2つの山に分けたあとに先程のような割当てを行い、順番に回収していくことを考える。

f:id:imulan:20181019055606p:plain

そうすると、2つの輪っかに割り当てられるマスが発生して、先程より効率よく使えていることがわかる。この方法に限って言えば、青い山の方を先に処理して、12から22を先に右下に集めてしまえば、赤い山は青い山に影響されることなくソートを行うことが出来る事がわかる。

このように、操作の前に既に下に何かあったとしても、その上の処理が終わるまでは一旦床とみなしてしまうことができ、その先の処理に何も影響がなさそうだ、ということが想像できる。

あとは、この例のような分配を再帰的に行ってソートをすることを考えたい。そこで、今回nの上限が40000なので、6*6マスで実現できるかを確かめよう。そこでf(R,C)を残りRC列残っているときに、任意の並びの山をソート済みにできる最大の個数とすると、

再帰的に右下全部のマスで処理させることを考えると、処理可能な個数は \displaystyle f(R,C) = \sum_{r \le R, c \le C, (r,c) \neq (R,C)} f(r,c)である。初期値はf(1,1) = 1で計算すると、fの値は以下のテーブルの通りになる。

f:id:imulan:20181019060706p:plain

これでは、40000個を処理できない。もう少し工夫することを考える。

そこで、 f(1,2) = 1となっていることに注目すると、これはもっと良くなる。具体的には、2にできる。なぜなら、2個ということはソート済みか、ひっくり返ってるかのどちらかしか無いが、ソート済みならそのまま一気に2個運んでしまえば良いし、ひっくり返ってるなら1個ずつ移動させればソート済みにできる。

ということで、新たに初期値f(1,1) = 1, f(1,2) = 2, f(2,1) = 2としてテーブルを埋めると以下のようになる。

f:id:imulan:20181019082521p:plain

よって、このアルゴリズムに従ってあとは操作列を出力すれば良いことになり、出力の行数も輪っか1つに対して10回が限度なので400000行ぐらいで、間に合う。

実装(C++)

続きを読む

2018/9 solved(1)

9/1

まず、全体が長方形にならないといけないので面積がa+bの長方形ができる必要があり、その全パターンは約数の個数に一致するので、まずa+bの約数を列挙し、それらが実現可能かをそれぞれチェックする。以下、h*wの長方形に注目しているとすると、赤か青が長方形になればいいので、これもいま同様に面積がa、またはbの長方形を内側にもつ必要があるというように考えれば、aの約数を列挙しておいて、hを超えない最大の値のみをチェックすれば良い(wがはみでないかどうか)。これはlower_boundなどで高速に求められる(submission)。

9/2

9/3

まず、ペアとして選べる長さの候補を列挙しておく。そして、二辺の長さをa,bとしたときに、最小化したい値を式変形してみると、(a/b + b/a)を最小化すると同じことになる。これは、aとbが等しいときに最も小さくなり、aとbの値が近いほど小さい値になる。よって、列挙した候補をソートして、隣合うものだけが候補になり、これで候補はO(n)通りに絞れる。あとは有理数同士で比較すれば良い(submission)。

n頂点n有向辺のグラフ(functional graph)は、連結成分ごとに見ると、パスをたどっていくと最終的にはサイクルに入り込むような形になっている。どの場所からスタートしても捕まえられないといけないので、サイクルに入っていない頂点にコストを払うのは無駄だということになる(結局、パス上に安くおいたとしてもサイクル内のケアが1つは必要になる、そして、そのサイクルがケアしてあるということはパス上に置く必要がなくなる)。よって、各連結成分ごとに、サイクルを検出して、その中での最小値を取って足していけば良い(submission)。

問題では隣り合う行同士も列同士も条件を満たさないといけない(完全に色が反転しているか、同じかじゃないといけない)というふうに書いてあるが、実は片方を満たすように置けばもう片方は勝手に満たされるので行ごとに決めていくと考える。すると、1行目のパターンを決めると、以降の行におけるのは1行目と同じパターンか反転したパターンの2通りしかないことになる(これを踏まえると列の方が勝手に条件を満たすのも想像できると思う)。すると、最終的に出来上がるのは、正方形内に適当に縦横に線を入れて、市松模様に塗ったような見た目になる。

1行ごとにパターンを決定していくために前計算を行う。あとで1行ごとにパターンを決めていくのに大事になるのは、1行にできる長方形の中で幅が一番長くなるのがいくつかということになる。これを dp[i][j][k][l] = 今i番目の色に注目, 最大で連続しているパターンの長さはj, 直前には同じパターンがk個連続中, 直前の色はl というdpで、遷移は2通りなのでO(n^3)で計算ができる。この結果をまとめると1行の中で一番長い長方形がwになるような色の塗り方の組み合わせが計算できる(実装ではこれをrow[w]としている)。

そして、 dp[i][j] = 今i行目に注目、直前にはj行同じパターンが続いている時の組み合わせ という数え上げができる。 いま、幅をwで決め打っているので、面積がk未満になるためにはこれ以上連続したパターンを出してはいけないというのが決まるので、その条件に気をつけて数え上げる。wの候補がn通り、このdp自体はO(n^2)で計算できるので、全体でO(n^3)で計算できる(submission)。

9/4

行きと帰りをまとめて処理する。行きは、使える辺をそのままはったグラフ、帰りは、使える辺を逆に張ったグラフ上で考える。d[i][j] = 行きでi、帰りでjにいる時の最短経路を求めることを考える。この問題を難しくしている要因として、通行料は1回しか払わなくていいというところがある。ということで、今、iとjのうち高度が低い方を移動させるという遷移を考える。iとjの高さが同じ時は、同時に移動させることを考える。遷移は、基本的にBFSをして、iを移動させる場所とjを移動させる場所を全探索し、更新できるなら遷移する、ということをする。このBFSをするにあたって、同じ高さでの移動コストを前計算しておく必要がある。行きだけ動かすとき、帰りだけ動かすとき、同時に動かす時の3種類のコストを計算する必要があるので、めんどくさいけど頑張る(submission)。

まず、各変数は1桁か2桁である。このパターンを全探索することにする(2^m通り)。すると、1の位を小文字、10の位を大文字で表したりして文字列を構成すると、どれが一致していないといけないかを、グラフを作って連結成分としてみなす事ができるようになる。この連結成分はすべて同じ値にならないといけない。連結成分同士で影響し合うことはないので、独立に考えてあとで掛け合わせることにする。さて、連結成分を考える前に、更に場合分けをする。2桁使うことにした変数について、10の位を最大まで持っていく(1の位に影響が出る)パターンとそうしないパターン(1の位を自由に選べる)パターンに分ける(2^m通り)。ここまで分けると、線形に連結成分をチェックするだけでどの数字を選んでよいかが確定するので、それを掛けていき、足し合わせればよい。O(2^{2m} n)かと思っていたけど、2桁にしないときは後ろの場合分けは発生しないのでO(3^m n)になっており、十分に速い(submission)。

9/5

9/6

9/7

9/8

SnackDown 2016 Online Elimination Round Virtual

Fで、分数をペアで管理したが、0が入ると挙動がおかしくなるのでそこに十分注意して実装する必要があったらしい(本番中には気づかなかった...)。

ABC 109 参加

Dはジグザグに連鎖するように処理した。もっと良い実装はあるだろうか...

9/9

9/10

9/11

9/12

9/13

9/14

BAPC 2016 Virtual

9/15

Japanese Alumni Group Summer Camp 2018 Day 1

2017年の台湾の国内予選のセット。

AGC 027