アルゴリズム忘備録

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

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)。

C: Fountain Walk - AtCoder Grand Contest 019

agc019.contest.atcoder.jp

 

格子マップ及びいくつかの頂点が与えられる。格子の辺は100m、与えられた頂点にはN個の噴水があり、半径10mの外周を通ることが可能である。格子点は同一水平線上または同一垂直線上にたかだか1個である。

スタートとゴールが与えられたときに、最短経路を答えよ。

 

まず分かることは角を曲がる時噴水を通ると、普通に格子点で曲がったときよりも距離が短くなり、噴水を縦または横に通り過ぎると格子点を直進するときよりも距離が長くなる。なので、なるべく格子点を曲がるときに通るのがよい。ここで、同一直線状に噴水はたかだか1個しかないことから、ゴールとスタートの間のマス目のサイズををH*Wとすると、min(H, W) + 1個しか存在しないことになる。まずはこの区間にある噴水をできるだけ通ることを考える。そこで区間内の噴水をx方向にソートする。その上で、噴水のy座標の最長増加列を計算すると、その列に含まれる噴水はゴールまでに通ることが可能である。この最長増加列の個数をkと置く。

 

k < min(H, W) + 1 のとき、全て曲がり角として噴水を通ることが可能なので、その差分を通常の格子点の最短経路(w + h)*100から引けばよい。

 

k = min(H, W) + 1のとき、最低でも1個は噴水を横切ってしまう。なのでその差分を足しておく。

 

全体でO(N)。

B: Reverse and Compare - AtCoder Grand Contest 019

agc019.contest.atcoder.jp

 

文字列Aが与えられる。任意の添字i, jを選び、連続部分文字列A[i]..A[j]を反転させる。(i=jならなにもしないのと同値)。この操作を1回だけしたときに得られる文字列は何通りあるか?

 

左の文字から順に数えていく。今見ている文字がcのとき、そこより右の文字がすべてc以外なら右にある文字数だけ、反転したら別の文字列が構成できる。もし、cがk>0 個あるとき、その反転は両脇のcを除いた反転と同じなので、現時点ではカウントしないこととする。こうやって和をとっていけば全部の組み合わせがカウントできる。

 

アルファベットはa-zなので、これらの文字のカウントの累積和を作っておくことで、あるインデックスより左にある特定の文字、と言うものをO(1)でカウントできる。合わせて計算量はO(N)。

 

 

A: Ice Tea Store - AtCoder Grand Contest 019

agc019.contest.atcoder.jp

 

アイスティーの単価がQ, H, S, D円でそれぞれ0.25l, 0.5l, 1l, 2l買える。在庫はいくらでもある。Nリットルのアイスティーを買いたいとき、必要な金額はいくらか?

 

要は2lのものをいくら買うか、ということである。まずリットル単価別にソート、もし2l以外でより安いものがあればそれで全部買う、2lが一番安い場合は2lのものを買えるだけ買い、もし1l分だけ他に欲しい場合は次に単価の安いものを買う。O(1)。

F - Sandglass - AtCoder Regular Contest 082

F - Sandglass

 

容量Xで一秒間に1砂がおちる砂時計がある。時刻集合r[i]が与えられて、各時刻に砂時計をひっくり返すことがスケジュールされている。時刻0で砂時計の上半分をAという。

このとき、q個のクエリ「初期のAにある砂の量がaのとき、時刻tのAの砂の量はいくらか」に答えよ。

 

初期の砂の量をx, 現在の時刻をtとする時、時刻tでの砂の量を返す関数を f(x, t) とおく。この関数をtを固定してシミュレートしてみると、ある時刻(※1)までは一定で、そこから傾き1の直線になり、更に別の時刻(※2)から一定になる、という関数になる。つまり(※1)の時刻と値、(※2)の時刻の3個の数値がtによって変化しているだけである。

 

この3個の値を更にtを変えてシミュレートしてみると、時刻が進むたびに全体にグラフが下に移動し、0を下限として(※1)が潰れていく、その後ひっくり返して全体に上にグラフが移動し、Xを上限として(※2)以降が潰れていくというのを繰り返し、状況によっては最終的に潰れて常にxによらない固定関数に近づく。これをシミュレートしてやればよい。O(Q)。