3匹の猫

みみねこの競プロ精進メモ

ZONeエナジー プログラミングコンテスト “HELLO SPACE”参加記(~D問題)

ABC級のコンテスト。ストーリーの関係でCとDの配点が逆転していた。

A - UFO Invasion

文字列中に含まれるZONeの数をカウントする。大文字小文字の区別や、文字配列の範囲外参照などに気を付けて実装する。
計算量はO(|S|)

B - Sign of Friendship

それぞれの遮蔽物ごとに分けて考える。その遮蔽物しかないと仮定すると、その遮蔽物の頂点とUFOの座標を結んだ直線とタワーの交点が最適解(最小値)となる。これは、三角関数などを用いてO(1)で求めることができる。
よって、すべての遮蔽物について考えたときの最適解の最大値が答え。全体の計算量はO(N)

ちなみに、解となる高さを二分探索しても解が求まる。この解法の計算量はO(N\log D)

C - MAD TEAM

3人の各パラメータの最大値の最小値の最大値を求める。(????)
一気に考えると混乱するので、ひとつずつ考察を詰めていく。愚直解はO(N^3)でダメ。

まず、最終的になにかの最小値の最大化をしたい。これは今話題の典型90問でも取り上げられていたが、「解の二分探索」が有効である場合がある。今回も解の二分探索をする方針で考察を進める。
解の二分探索を適用すると「3人の各パラメータの最大値の最小値をk以上にできるか?」という簡単な問題になる。しかしこのままだと結局この小問題を解くのにO(N^3)かかるので、もう一工夫必要。
選ばれる3人のうち、誰かのあるパラメータがk以上なら、そのパラメータについては必ず条件を満たす。あるパラメータの数値がk以上(必ず条件を満たせるライン)なら1、そうでないなら0とすることで、選ばれた3人の各パラメータの論理和がすべて1なら条件を満たしているということができる。さらに、各人の各パラメータの数値は2通りなので、N個ある選択肢を2^5個に圧縮することができる。これなら全探索しても{2^5}^3 = 32768通りの組合せしかないため、十分高速である。

計算量は…公式解説に倣って、パラメータの個数をM、選ぶ人数をK、二分探索の上限値をX = \max{A_i, B_i, C_i, D_i, E_i}としてO((NM+2^{MK})\log X)である。

D - Message from Aliens

操作を「文字の追加」「文字対の削除」の2つのフェーズに分ける。

(1) 文字の追加
愚直に操作を実行すると、文字列を反転するたびにO(|T|)の計算量がかかってしまうため、全体の最悪計算量はO(|S|^2)となる。反転しても文字列の並びは変わらないことを利用して、「今文字列が反転しているか?」というフラグを持ち、このフラグがtrueのときTは反転しているとみなして処理を行う。つまり、反転しているときは文字列の先頭に文字を追加する。

(2) 文字対の削除
ある隣接する同じ文字の組(文字対)を削除しても、他の文字対が削除できなくなることはない(状況が悪化しない)ので、文字対を見つけたら貪欲に削除してよい。stackを用いると、この操作をO(|S|)で出来る。

出力するとき、文字列の反転フラグを参照することを忘れない。全体の計算量はO(|S|)

E - Sneaking

(r, c)\to (r, c-1)への移動を使うことはないと考察して動的計画法を書いたがWA。グラフの最短距離を求める問題に帰着できるらしい。

感想