アルゴリズム忘備録

競技プログラミングとかデータ分析とか

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

code-festival-2017-qualb.contest.atcoder.jp

 

グラフが与えられる。辺をちょうど3回通ってたどり着ける2点間に新たに辺を引く、という操作をできるだけしたい。ただし、既に辺がある場合は引くことができない。最大で何回操作ができるか?

 

グラフが二部グラフでないとき、頂点間の経路は操作を繰り返していくことで、すべての2点間で3回通って辿り着ける。そのため、完全グラフの辺の数から既に引かれている辺の数を引けばよい。

グラフが二部グラフの場合、最大で完全二部グラフにしかならない(偶奇を考えればよい)。そのため、完全二部グラフの辺の数から現在引かれている辺の数を引けば良い。

計算量は二部グラフの判定が支配項でO(N)。

CS Academy Round 51 - Tree Coloring

csacademy.com

 

ツリーと色数kが与えられる。この時、あるノードに対して、そのノードから距離1のノードと、距離2のノード両方と色が異なるように頂点を彩色したい。彩色の仕方は何通りあるか。

 

あるノードに着目する時、距離1または距離2のノードがすべて異なるということなので、そのノードの隣接ノードの集合を考える。するとその隣接ノード+今見ているノードの集合について、これらは全て距離2以下であるため、その集合の数をmと置くと彩色数は k * (k - 1) * .. * (k - m + 1) となる。ここから次の隣接ノードに移る。すると、同じように考えられるが、既にカウント済みのノードがあるため、そのカウント済みのノードをlとおくと、それらのノードの色は既にカウント済みであり、かつ全て色が異なる。したがって今見ている集合の彩色数は  (k - l) * (k - l - 1) * .. * (k - m + 1) となる。

これらをdfsで辿っていき、子ノードの彩色数の積に今見ているノードの彩色数の積、という値を返してどんどん根まで計算すると答え。O(N)。

CS Academy Round 51 - Manhattan Distances

csacademy.com

 

整数d1, d2, d3が与えられる。2次元格子点座標の3点であって、各点のマンハッタン距離がd1, d2, d3のいずれかになるような3点を構成せよ。できない場合は-1を出力せよ。

 

マンハッタン距離は距離と名付けてあるだけあって、距離公理を満たす。その為、三角不等式の成立条件が構成できる第一条件である。次に格子点座標にある場合、それらのマンハッタン距離はその三点を囲う最小の長方形の周囲の長さに等しくなる。(図を書いてみるとすぐわかる。そのため、d1+d2+d3が偶数であることも必要であり、かつ十分である。

 

そこで、単純な例として、長方形の一片が構成する3点のうちの2点でかつd1~d3の中で最大のもの(例えばd1とする)であり、その片方が原点であるようなものを考える。すると(0, 0), (0, d1) と座標が決まる。すると、残りの1点は((d2 + d3 - d1) / 2, (d2 + d1 - d3) / 2)などとなる。O(1)。

CS Academy Round 52 - Race Qualifying

csacademy.com

 

レースを行い、1~N位までの仮順位をつけた。ただし、それぞれの順位の人はa[i]回違反をしており、ペナルティを受ける。x位の人がk回違反をした場合、x+k位になる。最終順位を求めよ。

 

仮順位+ペナルティ回数でソートする。ただし、仮順位+ペナルティ回数が同じ物については、仮順位の降順ソートをする。これは例えば1位が2回ペナで3位になるのと、元の3位について、元の3位が繰り上がるからである。O(NlogN)。

CS Academy Round 51 - Poisoned Food

csacademy.com

 

a[i], b[i] のN個のリストが与えられる。それぞれ、食料iに対して、a[i]個のポーションが原料として使われており、その中でb[i]個が毒ポーションであるという意味である。最も毒の割合が少ない食料を答えよ。同じ割合の食料がある場合は、一番インデックスの小さい食料を答えよ。

 

b[i] / a[i] の最小値をもって全探索する。EPSを忘れずに。O(N)。

D: Four Coloring - CODE FESTIVAL 2017 qual A

code-festival-2017-quala.contest.atcoder.jp

 

距離dが与えられる。マンハッタン距離がdの点同士は異なる色で塗られるように格子点を塗り分けたい。塗り分けを一つ構成せよ。

 

マンハッタン距離を考えるときは、必ず45度回転を考える。そうすると、x軸またはy軸方向の差のうち、小さいほうがdという条件になる。

これを考えると、まずd=1の場合は、一列ごとにRGRGRGRG...とBYBYBYBY...という塗り分けをすればいいことがわかる。d>=2のときは、R 1個が2*2行列になっているようなイメージである。(p, q)を45度回転済みの座標とすると、

 

x = (p % (d*2)) / d

y = (q % (d*2)) / d

c = (x * 2 + y) % 4

 

とすることで、cが0~3が決まる。このインデックスに応じて、RGBYを塗り分ければ良い。O(HW)。

C: Palindromic Matrix - CODE FESTIVAL 2017 qual A

code-festival-2017-quala.contest.atcoder.jp

 

要素がアルファベットの行列が与えられる。各行及び各列が回文になるように要素を並び替えたい。可能かどうか判定せよ。

 

まずすべての要素について、a~zの登場回数をmod4でカウントしておく。

そして行及び列の偶数奇数で場合分けする。両方共奇数の場合はmod4 = 1 or 3の文字がちょうど1個必要。また、真ん中の文字を覗いたカウントで、mod4 = 2の文字はそれぞれ真ん中の列及び真ん中の行で使われ、ちょうどh+w-2個必要である。残りはすべてmod4 = 0にっている必要がある。偶数の場合はすべてがmod 4 = 0になるなど、場合分けがあるがあとは同様に可能。O(HW)。