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

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

ABC#002

2日目です。頑張って続けていきたいです。
D問題を最初Union-Findかと思って実装までしたところで間違いに気づき書き直しました。こういう時間ロスがもったいない。

- A問題「正直者」

(http://abc002.contest.atcoder.jp/tasks/abc002_1)

問題概要:
神にお小遣いをもらう問題。最大10億円もらえるとかとってもうらやまC。

解法:
#includeのmaxを利用。max関数はたくさんオーバーロードされてて様々な型に応用きくからすごい便利。

ソースコード:
http://abc002.contest.atcoder.jp/submissions/338302


- B問題「罠」

(http://abc002.contest.atcoder.jp/tasks/abc002_2)

問題概要:
神からお小遣いをもらったと思ったら代償に母音を盗まれたというお話。与えられた文字列Wから母音を抜き取って出力する。

解法:
入力の文字列をchar型の配列に格納し1文字ずつ母音でないか確認し出力。最後の改行を忘れないように。

ソースコード:
http://abc002.contest.atcoder.jp/submissions/338354


- C問題「直訴」

(http://abc002.contest.atcoder.jp/tasks/abc002_3)

問題概要:
奪われた母音を返してもらうために神のもとで三角形の面積を求めます。人質をとって労働させる神とは。

解法:
(x,y),(a,b),(c,d)と与えられるとき、(x,y)=(0,0)ならば面積は|ad-bc|/2で求められるので(x,y)が原点にくるように座標変換を行います。行列計算の自作ライブラリとかがあるならそれを使って解いてもいいかもです。絶対値を忘れないように。
ソースコード:
http://abc002.contest.atcoder.jp/submissions/338484
小数点は.5までしか出ないし大丈夫だと思って出力をcoutにしたらWA食らいました。printfでフォーマットを.1fにしたらちゃんとAC。なぜだ、、、


- D問題「派閥」

(http://abc002.contest.atcoder.jp/tasks/abc002_4)

問題概要:
知り合い同士を集めて派閥を形成し首相になる問題。主人公の高橋君がその派閥に含まれている必要はないのだろうか。
最大クリーク問題というNP困難(計算時間が指数時間)に含まれる部類の問題らしいです。nの最大が12なので気にする必要はないです。

解法:
入力されたN人のうちn人の組み合わせをもってきて、そのn人が互いに知り合い同士かどうか調べる。互いに知り合い同士である組み合わせの最大人数を出力。
知り合いかどうかの判定にビット演算を用いています。
1.入力処理
隣接リストと同じ要領で配列adjに知り合いを登録。
iとjが知り合いならadj[i]のjビット目を1にする。
知り合いでないときは0のまま(i=jのとき1にしておく)
2.組み合わせを全探索
1~N人の組み合わせを全て作成する。組み合わせの数は二項定理から2^N通り
組み合わせの表現方法もビットを使う。
(例)議員6人のうち議員1,2,4の組み合わせ:001011
3.派閥ができるかの判定
2で作成したビット組み合わせに対して隣接関係が成立しているか判定する。001011のときはadj[1],adj[2],adj[4]が全て001011を含む(001011とアンドをとると001011となる)とき派閥が成立する。

ソースコード:
http://abc002.contest.atcoder.jp/submissions/338888
ビット演算を使うと早くなることがあるけどソースが見づらくなるのが玉に瑕ですね