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

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

東京大学プログラミングコンテスト(UTPC)2014 A,B,C問題

以下本番中に解けた問題です。
1時間遅れで参加して3問とFの部分点で83位でした。
4問+部分点はいけるようになりたいです。

- A問題「二重否定除去法則」

(http://utpc2014.contest.atcoder.jp/tasks/utpc2014_a)

問題概要:
not not 何か という文字列の並びがあるときはnot notを削除せよという問題です。

解法:
前から派の方と後ろから派の方がいらっしゃいますが私は前から派です。
入力を文字列の配列で管理し、i-2,i-1,i番目の文字列がnot not (not以外)の順であったらi番目をi-2番目に持ってくるという処理をしてやればよいです。
ただしnot not not not yesのような形も存在するのでif文でなくwhile文で処理しましょう。

ソースコード:
http://utpc2014.contest.atcoder.jp/submissions/371944

- B問題「交点」

(http://utpc2014.contest.atcoder.jp/tasks/utpc2014_b)

問題概要:
2次元平面上の点(x,y)が与えられます。
その点を通る2本の異なる直線の通る2点をそれぞれ列挙せよ。
ただし出力は整数、入力は小数点第三位までという制約が存在する。
また、入力で与えられる値の絶対値は1000以下、出力の整数の絶対値は10000以下という制約が存在します。

解法:
入力は小数で出力は整数であるという制約が厄介です。
しかし、入力の小数は小数点第三位までということで、1000倍すると整数になるということがポイントです。
したがって、入力を浮動小数点として受け取らずに整数部、小数部と分けて整数として管理することが必要です。浮動小数点のままだと誤差が怖い。
例として、(12.345,23.456)を通る直線について考えます
xを-12,yを-23平行移動した座標は(0.345,0.456)です。
この状態ならば、(0,0)と(345,456)を結んだ直線がこの座標を通ることがわかると思います。
したがってこの直線のxを12,yを23平行移動した直線が元の座標を通ります。
同様にして、xを-13,yを-23平行移動した座標は(-0.655,0.456)です。
あとは同じ方法でもう一本直線を列挙できます。
((int)x+1,0)を通る直線と((int)x+1,(int)y+1)を通る直線を選べば二つの直線が一致することがないのでお勧めです。

ソースコード:
http://utpc2014.contest.atcoder.jp/submissions/372958

- C問題「最小カットと最大カット」

(http://utpc2014.contest.atcoder.jp/tasks/utpc2014_c)
問題文に惑わされてはいけない(戒め)

問題概要:
与えられたグラフの最大カットと最小カットを求める問題です。

解法:
そもそも最大カットは多項式時間で解くアルゴリズムがありません。
Nがそこそこ大きいので愚直に最小カットを求めてもアウトです。
ここで、辺の個数がN個であることに着目します。
木の辺の数がN-1個なので木に辺を一個追加したもの、すなわちループが一つのみ存在するグラフです。
最小カットはグラフが輪の形になっているとき2,それ以外のときは辺がつながっている個数が1のみの頂点が存在するので1となります。
最大カットですが、木を実際にDFSで塗り分けしていけば必ず最大になります。

ソースコード:
https://utpc2014.contest.atcoder.jp/submissions/373239