ZONeエナジー プログラミングコンテスト “HELLO SPACE”参加記(~D問題)
ABC級のコンテスト。ストーリーの関係でCとDの配点が逆転していた。
A - UFO Invasion
文字列中に含まれるZONe
の数をカウントする。大文字小文字の区別や、文字配列の範囲外参照などに気を付けて実装する。
計算量は。
B - Sign of Friendship
それぞれの遮蔽物ごとに分けて考える。その遮蔽物しかないと仮定すると、その遮蔽物の頂点とUFOの座標を結んだ直線とタワーの交点が最適解(最小値)となる。これは、三角関数などを用いてで求めることができる。
よって、すべての遮蔽物について考えたときの最適解の最大値が答え。全体の計算量は。
ちなみに、解となる高さを二分探索しても解が求まる。この解法の計算量は。
C - MAD TEAM
人の各パラメータの最大値の最小値の最大値を求める。(????)
一気に考えると混乱するので、ひとつずつ考察を詰めていく。愚直解はでダメ。
まず、最終的になにかの最小値の最大化をしたい。これは今話題の典型90問でも取り上げられていたが、「解の二分探索」が有効である場合がある。今回も解の二分探索をする方針で考察を進める。
解の二分探索を適用すると「人の各パラメータの最大値の最小値を以上にできるか?」という簡単な問題になる。しかしこのままだと結局この小問題を解くのにかかるので、もう一工夫必要。
選ばれる人のうち、誰かのあるパラメータが以上なら、そのパラメータについては必ず条件を満たす。あるパラメータの数値が以上(必ず条件を満たせるライン)なら、そうでないならとすることで、選ばれた人の各パラメータの論理和がすべてなら条件を満たしているということができる。さらに、各人の各パラメータの数値は通りなので、個ある選択肢を個に圧縮することができる。これなら全探索しても通りの組合せしかないため、十分高速である。
計算量は…公式解説に倣って、パラメータの個数を、選ぶ人数を、二分探索の上限値をとしてである。
D - Message from Aliens
操作を「文字の追加」「文字対の削除」の2つのフェーズに分ける。
(1) 文字の追加
愚直に操作を実行すると、文字列を反転するたびにの計算量がかかってしまうため、全体の最悪計算量はとなる。反転しても文字列の並びは変わらないことを利用して、「今文字列が反転しているか?」というフラグを持ち、このフラグがtrueのときは反転しているとみなして処理を行う。つまり、反転しているときは文字列の先頭に文字を追加する。
(2) 文字対の削除
ある隣接する同じ文字の組(文字対)を削除しても、他の文字対が削除できなくなることはない(状況が悪化しない)ので、文字対を見つけたら貪欲に削除してよい。stackを用いると、この操作をで出来る。
出力するとき、文字列の反転フラグを参照することを忘れない。全体の計算量は。
E - Sneaking
への移動を使うことはないと考察して動的計画法を書いたがWA。グラフの最短距離を求める問題に帰着できるらしい。
感想
あ