9/1

CF 1029 F - Multicolored Markers

まず、全体が長方形にならないといけないので面積が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)。

CF 1027 D - Mouse Hunt

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

CF 1027 E - Inverse Coloring

問題では隣り合う行同士も列同士も条件を満たさないといけない(完全に色が反転しているか、同じかじゃないといけない)というふうに書いてあるが、実は片方を満たすように置けばもう片方は勝手に満たされるので行ごとに決めていくと考える。すると、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

AOJ 1324 - Round Trip

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

AOJ 2604 - Pattern Language

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