読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#010

ABC

- A問題「ハンドルネーム」

(http://abc010.contest.atcoder.jp/tasks/abc010_1)

問題概要:
文字列に"pp"を付け足して出力する問題です。ていうかこれが解法です。
Atcoder社長の方はC#使いなのに秘書はC++好きなのですね。

解法:
stringクラスで+演算子が文字列を連結するように定義されているのでそれを利用すればコードが簡潔になります。

ソースコード:



- B問題「花占い」

(http://abc010.contest.atcoder.jp/tasks/abc010_2)

問題概要:
n枚の花の花びらをうまくちぎってどの花をとっても花占いがうまくいくようにします。
ちぎる枚数の最小化問題です。

解法:
2パターンの占いは2枚、3枚ごとにループをするので、6枚ごとに占い結果がループすることになります。6で割った余りをとってその余りに対して何枚ちぎるべきか事前に計算しておくと解が求められます。
この問題では与えられる花びらの枚数が非常に少ないため各枚数に対する最適解を事前に求めておいてもOKです。
ソースコード:



- C問題「浮気調査」

(http://abc010.contest.atcoder.jp/tasks/abc010_3)

問題概要:
ストーカーをする問題です。
ある時間にGPS座標を取得したところ座標Aを取得、
そのT分後にGPS座標を取得したところ座標Bを取得。
分速Vで移動できる人がT分間の間に女の子を経由してAからBへの移動が可能かどうかという問題です。

解法:
T分間最高速度Vで動き続けたとき移動できる距離はTVです。
したがってある座標Xについて、AからX,XからBを直線で移動するとすると
|AX|+|XB|\le TVが成り立つときXを経由することが可能です。
全ての女の子の家の座標Xについて上記の式が成り立つかどうかを調べればよいので計算量はO(N)です。
本来doubleを使って等号の条件判定をするときはepsを使うべきなのですがこの問題は使わなくても大丈夫でした。

ソースコード:



- D問題「浮気予防」

(http://abc010.contest.atcoder.jp/tasks/abc010_4)

問題概要:
SNSのアカウント操作ができるスーパーハッカーのお話です。
ある二人の友人関係を削除するもしくはある一人のパスワードを書き換えてログインできなくするという恐ろしいもの。
バレないように工作回数を最小にしましょう。

解法:
全てのターゲットのパスワードを書き換えても工作は成功しますが最適解ではありません。
友人関係を解消したほうが少なくなるケースがあるからです。
また、ターゲット以外の人のパスワードを変更しても意味がありません。
人を頂点、友人関係を辺としてグラフ問題に落とします。
そうすると、高橋君とターゲットの間にパスが一つもない状態を作ればいいことがわかります。
一つ目の工作は辺を削除するだけでよいのですが二つ目の工作は頂点を削除すればいいという問題ではないので厄介です。
そこでターゲットの集合を表す頂点Uを新たに一つ作成し、全てのターゲットとの間に辺をつなげます。
これで高橋君とUの間にパスがあるかどうか調べればよいことになりました。
すると2つめの工作はE(U,T)の間の辺を削除することと同等になるのでこれで問題は解けそうです。
辺を削除して高橋君とUの間のパスを全て切り離し、その上で削除する辺の数を最小にするという最小カット問題になりました。
最小カットは最小カット最大フロー定理を利用して最大フローを解けばいいのでO(EN)で解けます。
注意点として今回の問題では無向グラフを扱っています。
残余グラフの扱いについて、初期値としてE(x,y)=E(y,x)=1としておき、xからyにフローを流すときe(x,y)--、e(y,x)++とすれば問題なく動作します。

ソースコード: