Uva:11735 Corner the Queens

幾何したいけど解ける問題が無かったので

部内プロコンの解きこぼしをやる

問題↓

http://uva.onlinejudge.org/external/117/11735.html

問題概要

• 正方形の無限に広いグリッドがあります左下末端が(0,0)
• 左・左斜め下・下方向にのみ無限に移動できるチェスのクイーンがいます
• グリッド内に長方形の区間が与えられ、その長方形内のマスにランダムでクイーンがおかれます。
• 長方形の区間(0<=x1<=x2<=1000000,0<=y1<=y2<=1000000)
• 二人のプレイヤーは交互にクイーンを動かしていきクイーンを(0,0)に置いたプレイヤーの勝ちです
• 先行のプレイヤーが勝つ確率を既約分数で答えて

解法

• プレイヤー１が100%負ける場所を列挙
• (0,0)から斜めの線を引き、まずプレイヤー1が100%負ける場所は(2,1)と(1,2)である
• (2,1)の方は上(y)方向に探索、(1,2)のほうは右(x)方向に探索をする
• 各々、自分の置いたX座標、Y座標、にフラグをたてもしフラグが立っていなかったらそこが100%負ける場所になる。
• そうした後にX-Yの差を変更し探索を続ける。これを範囲がはみ出すまで繰り返す。
• 列挙したマスに対し、指定された長方形の内部にあるマスのうち一番右上と一番左下のマスを二分探索で見つける。（列挙したマスの座標は単調増加）
• 差を足し算して、最後に既約分数を__gcdで作っておわり

ソースコード

感想

すごい良問臭がぱないが英語が読めなかった

英語力つけたい