裏紙

ほぼ競プロ、たまに日記

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

2018/8 solved(2)

8/17

8/18

辞書順最小→貪欲(submission)。

同じグループにできるのは、正負が一致かつ素因数の個数の偶奇が一致するものが同じグループにすることができる。ただし、0だけは特別扱いする必要があり(0はどのグループに入っても差し支えないので)、それ以外のグループがいくつできるかを全部の部分列に対してO(n^2)で試す(始点iを決めて、そこから右に動かしながら要素を追加していく)。この全探索部分に余計なlogなどを載せたくないので、前計算として素因数分解したものをmapでID化しておくと計算量がちゃんとO(n^2)で抑えられる(submission)。

残す人数を最大化したいと考えると、nから降順に貪欲に残していいかを考えることで、残す頂点n-k個を選ぶことができる。なぜなら、2^i2^0 + 2^1 + \ldots + 2^{i-1}よりも大きいことを考慮すると、とにかく大きい方を残すほうが得になるからである。そして、残すと決めたときには、nまでのパス上の頂点を全部残さないといけないことになる。よって、nを根としてみなし、ダブリングで親を計算しておくことで、すでに残すうことを決めた頂点までの距離がO(logn)でわかる。これによって上から貪欲に残す頂点を決定できるので、自ずと消す頂点が決まる(submission)。

8/19

KUPC 2013 Virtual

8/20

まず桁数が違った場合は、できるだけ大きくすれば良いので簡単。同じ場合を考えると、先頭何文字までを一致させるかを全探索することにすると、各場合について貪欲に構成することができる(submission)。

8/21

まず、1つ閉路を見つける。するとその閉路の長さはn以下なので、そのどれかを削除して、そのグラフに対して閉路がないことを逐一チェックすればO(nm)で間に合う(submission)。

8/22

non-working dayの区間をsetで管理することにする。追加するクエリの時は、その間の区間をマージしないといけないので、lower_boundでその区間のスタート地点を見つけて、全部eraseしてから新しい区間を追加する。削除するクエリの時は、同様にスタート地点を見つけて、逐次削除していく。ただ、端は残るかもしれないのでそこを全部消してしまわないように気をつける。このようなことをやると、1回のクエリ処理でたくさんアクセスしてヤバいんじゃないかと思えるが、クエリ全体を通して見ると、このような区間の追加や削除の回数はO(Q)で抑えられているので、余計なところにアクセスしないように気をつけて実装すればO(QlogQ)になっている。実装の部分で結構悩んだが、やっぱり半開区間で管理するのが実装の見通しが良い。区間を併合するのが楽なように感じる(submission)。

8/23

その星で布教すると決めたら、その星の期間が終わるまでい続けても最適性は失われないのでそういう動きしかとらないことにすると、区間を終端でソートして、O(n^2)の配るdpができる(submission)。

8/24

8/25

RUPC 2016 day1 Virtual

Summer Festival Contest 2018 (Division 1)に参加

8/26

8/27

8/28

8/29

計算すべき値はペアに対して設定されているが、最小値と最大値に分離して考える。すると、各頂点に対して、この頂点が最大値/最小値になるようなパスはいくつあるか、を各頂点に対して数え上げていくことになる。最小値も最大値も同様に計算できるので、ここでは最大値について考えることにする。頂点にかかれている値が小さい方から順に数えていくことにすると、その頂点から順番に、サイズを管理できるUnionFindを利用しながら、そのパスを通過するようなパスの個数を数えていくことができる。具体的には、小さい方から順に処理するので、いま注目している頂点uに対して隣接する頂点vが、すでに処理済みだった場合はuのほうが最大値になるので、まず、そのvの連結成分とuのパスはuが最大値になる。また、隣接していてすでに処理済みである別の頂点wがあった場合は、vを経由してwの連結成分へ伸びるようなパスもuで最大値を取るので、そのようなパスを全部考慮するには和を取って2乗してから2乗の和を引いて重複を除去すればよい。このようにしてO(nlogn)で数え上げることができる。最小値も同様に、逆に大きい方から数えれば良い(submission)。

各a[i]について、それをxに選んだときに適切なyがいくつあるかを数える。yに選ぶ数の桁次第で、xの位置がずれるので、桁ごとに分類して考える。すると、10のべき乗を計算しておくことで、xが来る位置と合わせてkでの剰余がわかるので、yに来るべき値が決まる。このyに来る候補を、事前にmapなどで数えておけば、入力の数列は10桁以下なので、O(nlogn)で十分に間に合う(submission)。

8/30

8/31