裏紙

ほぼ競プロ、たまに日記

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

2018/8 solved(1)

8/1

8/2

まず、lcmとgcdの関係から、xy = abが成り立ってないといけないが、これを満たすようなaの個数は約数の個数で抑えられており、それはlogで抑えられていると考えれば、xとyを素因数分解して、それぞれがもつ素因数をマージした情報を持っておき、あとはdfsで因数をどちらにどれくらい配るかの全探索をし、それが条件にあっているかどうかをチェックすれば良い(submission)。

Cの方が簡単じゃないか...?繰り返し二乗法と逆元がわかってれば解ける(submission)。

8/3

もし1が無かった時のことを考えると、積の方がすごいスピードで大きくなっていき、区間の長さがlognより大きいとこは見る意味がなくなってくるのが分かる。なので、連続している1をまとめて処理するようにすると、区間の左端を固定したときに試すべき右端がO(logn)個に抑えられるので、O(nlogn)で計算できる(submission)。

8/4

あり得る操作の有向グラフを作って、dfsしながら、全部訪れられるところを始点にすれば良い(submission)。

8/5

連結成分ごとにチェックしていく。cycleであるかの判定は、各頂点の次数が2であることを確かめれば十分(このとき、cycle以外作れないので)(submission)。

値が小さい方から埋めていくDPをする。復元も必要なので、親のindexも持っておくと良い。遷移に関しては、隣接している値に注目して、尺取りっぽく更新していくことができる(submission)。

sを使ったかどうかのフラグでdpしたくなるが、それだとsを使わずに自然発生したものと重複して数え上げてしまうので、それを避けて1文字ずつ決めていく方針にする。そうすると、今sと何文字目まで一致しているかという状態が更に必要になる。こうすると状態数がO(n^3)になる。遷移に関しては、2通りであり、前計算でこの先頭何文字が一致するかを求めておけば、このdpはO(n^3)で計算できる(submission)。

8/6

UAPC2015Day2 Virtual

初心者の2年生も交えて3人チームで。Jは最初からtreapで殴ればよかったー。

8/7

8/8

拡張BFSを頑張る(submission)。

8/9

スタートからとゴールからのダイクストラで距離を求めておき、fsが低い順にクエリを処理していく。和を持つセグ木を用意しておいて、fgの方も条件を満たす頂点数を計算できる(submission)。

コストが低い辺から順に、UFで辺の端点2つをつないでいく。繋ぐ直前のそれぞれの連結成分の大きさの積が、全パスの中でそこがネックとなって現れる回数になる(submission)。

8/10

E1は制約が緩い版なのでまとめて解いた。各マスに対して、4方向にどれくらい伸ばせるかを独立に前計算しておくと、そのマスを中心としておけるstarのサイズは4方向のminになる。ここで、各マスからいちいち伸ばしていると間に合わないので、方向を固定して1つ手前の位置を注目して計算するdpをすることで前計算がO(nm)でできる。おける場所が分かったら、その通りに置いてみて(この試し置きも愚直にやるとTLEする可能性があるので、横棒と縦棒に分けて累積和っぽくとる)、復元できているかをチェックする(submission)。

各数について、含まない部分列の個数を数えることにすると、間がどれくらい空いてるかに注目すればよく、この間は全体でO(N)個しかないので、間に合う(submission)。

両側探索。24回以下が保証されるので、23回以下でできるか探しに行く。メモしておくほうをスタートから11回分、dfsでゴールから12回分を探索する(submission)。

与えられた情報から、dpによって答えを前計算しておく(submission)。

8/11

ABC 105

Cむずかった。プラスとかマイナスを考えるのがややこしいので、マイナスになる項を反対側に持っていくと、下の桁から素直な貪欲ができるようになる。

8/12

dp[i][j] = うまか棒をi本、ふがしをj本を持ってるときのブタメソの個数のmaxを持ちながら1人ずつ順番にどの交換をするかを遷移とするものを考える。このときに、順番にやっていくと後で辻褄を合わせることを考えないといけないが、それは遷移の途中で個数が負になることを許せば良い。最終的に2つのkeyであるiとjが0以上になっていれば、その中からmaxを見つけられる(submission)。

うまく探索する場所を減らしたいので、問題の性質に注目して減らせるとこを考える。まず、回す必要性についてだが、回す軸にスタートとゴールが両方乗っているような回転は無駄なので、考えない。また、ゴールだけが移動するような回転は、相対的に見ればスタートだけが移動するような回転と同じにみなせるので、ゴールは固定された位置にあるものだと考える。さて、そうなると回転させるタイミングは、始めにやろうと途中でやろうと基本的に関係ないことが分かるので、回転をスタート直後に済ませてしまい、そこから移動する、みたいな経路だけを考えれば良い。よって、スタート直後のアクションを全探索することを考える。ただし、軸がかぶっていると回せないので、一歩すれるという動作も考慮して、深さ6までのアクションを全探索した(submission)。

8/13

8/14

8/15

だめな方を数えるのが楽。xを根とみなして、各部分木のサイズをdfsで求めておけば、xを通ってから、yを通るようなパターンが何通りあるかは簡単にわかる(submission)。

8/16

タイプ2のクエリ(x,k,s)がややこしいので整理する。GCD(x,v)がkで割り切れる && v <= s-x なるvのなかで、x XOR v が最大となるようなvを既に(タイプ1のクエリによって)追加された値の中から見つける、ということになる。条件を満たすようなvを考えてみると、vはkの倍数であれば良いことがわかる(そもそもxがkの倍数出ない時は何を選んでもだめだが)。よってkの倍数の値だけの出現を管理するトライ木を作り、その木をdfsすることで条件を満たすvを見つけることができる。基本的にはxと反対方向に進むが、そっちに進むと詰んでしまうときは逆に進む。そのために、進んだ方向に関して「こっちに進んだら最低でもこの値を取らないといけなくなる」という値を持っておけば、それとs-xを比較することで判断ができる。約数の個数はだいたいlogで抑えられるので、追加クエリに関してもlogの2乗くらいで対応できる(空間計算量も同様)(submission)。

解説を見た。言われてみればそうだなあという感じのdpだった。組み合わせを前計算しておくことでオーダーを落とす(submission)。

こういうの嫌い...