Atcoder ABC259 振り返り - hirohirohirohirosのブログ

A - Growth Record【AC】

　X歳後は身長は伸びないのでX<=Mなら身長はそのままT，X歳前は毎年Dcm伸びますが逆に言うと1歳減るごとにDcm縮むということなのでX-M回-Dすれば良いです．

N, M, X, T, D = map(int, input().split())
if X <= M:
    print(T)
else:
    for i in range(X-M):
        T -= D
    print(T)

B - Counterclockwise Rotation【AC】

　(a, b)をd度回転させた点(a', b')を求めます．d度回転させるだけなので，原点と(a, b)の距離と原点と(a', b')は同じです．そのため，まず原点と(a, b)の距離disを求めます．
　次に原点と(a, b)との角度θを求めます．三角関数を思い出すと，この角度は $tanθ = \frac{b}{a}$ と表せます．このθを求めるにはtanの逆関数 arctanを使えば良いです．
　mathモジュールではmath.atan2を使います．math.atan関数もありますが，こちらは引数が1つでmath.atan(b/a)とします．しかしこれではa=0の時にエラーとなってしまうため，そのようなエラーを回避するために引数を2つとるmath.atan2(b, a)を使います．
　この返り値は弧度法であることに注意します．dは度数法なのでmath.degreesを使って度数法に変換します．
　度数法で原点と(a, b)の角度が分かったら，dを出す事で回転後の角度を求めます．
　最後にこの角度から先ほど求めたdis分だけ離れた点を求めます．単位円を想像すると，x座標を求めるにはcos，y座標を求めるにはsinを使えば良いです．単位円なので距離は1です．よってdisだけ掛けてやれば答えを得られます．

import math
a, b, d = map(int, input().split())
dis = (a**2+b**2)**(1/2)
deg = math.degrees(math.atan2(b, a))
deg += d
deg %= 360
aa = dis*math.cos(math.radians(deg))
bb = dis*math.sin(math.radians(deg))
print(aa, bb)

C - XX to XXX【解説AC】

　WA2つ取れませんでした……
　ランレングス圧縮はitertoolsモジュールのgroupby関数を使います．
　itertools.groupby([1,1,2,2,2,3])は1, [1, 1, [2, [2, 2 ,2]], [3, [3]]]が返ってきます．型はリストではないため扱いには注意します．
　ここで，WAと引っかかっていたのはaa aabのようなパターンです．コンテスト時はfor文でzip(grS, grT)としていましたが，これだとgrSとgrTの長さが異なるとき，長い方は最後までループされずに抜けてしまいます．この例で言うとgrS = a, [a, a], grT = a, [a, a, [b, [b]]]となりますが，普通のzipだとs=[a, [a, a]], t=[a, [a, a]]でgrSが尽きてしまうのでgrTの[b, [b]]が使われる事なくループを抜けてしまいます．そして，これはNoのはずなのにYesとなってしまいます．
　grSとgrTの長さが異なれば必ずNoなのでそのような条件分岐を用意します．今回はitertools.zip_longestという関数を使います．これはその名の通り長さの長い方までループさせる関数です．短い方はNoneになります．よって，sかtのどちらかがNoneになればそれはgrSとgrTの長さが異なると言うことなのでNoとします．

import itertools
S = list(input())
T = list(input())

grS = itertools.groupby(S)
grT = itertools.groupby(T)
for s, t in itertools.zip_longest(grS, grT):
    if s is None or t is None:
        print("No")
        break
    ss = len(list(s[1]))
    tt = len(list(t[1]))
    if s[0] != t[0]:
        print("No")
        break
    if not(ss == tt or (ss<tt and ss>=2)):
        print("No")
        break
else:
    print("Yes")

D - Circumferences【AC】

　問題をパッと見てunionfindだと分かったのは良かったです．
hirohirohirohiros.hatenablog.com
　まず，始点と終点がどの円周上にあるかを調べます．円の方程式は(x-a)^2+(y-b)^2=r^2です．つまりこの方程式が成り立っているならば点が円周上にある事が分かります．
　次に2つの円があった時に交わっているかを判定します．円が交わっているならその交点を使ってお互いの円周に移動する事が出来ます．一点で接していようが2点で交わっていようがお互いの円周に移動出来るので接しているか交わっているかは区別する必要ありません．
　判定方法は円の中心同士の距離dと円の半径の和を使います．
　円が外側で交わっていない場合，この図の通りd>r1+r2が成り立ちます．

　これは円の衝突判定でもよく使われますが，今回の問題の場合内側に含まれている場合も互いの円周に移動出来ないので交わっていない判定する必要があります．この場合は図の通りdr2)

　このとき, 正しいdを求めるために $\sqrt {(x-a)^2+(x-b)^2}$ としてはいけません．なぜなら，d=r1+r2やd=r1-r2の時も接しているため交わっている判定にしなくてはいけません．しかし，dにルートを取ってしまってはr1+r2と等しくなることはありません．そのため，dにルートを取るのでは無く，r1+r2やr1-r2を2乗することで判定させます(1WA).
　これで2つの円が交わっているかどうか判定できました．
　2つの円が交わっていればどちらの円周にも自由に移動出来るので実質1つのグループとして扱うことが出来ます．グループに含まれている1つの円が他のグループのどれかの円に交わっていた場合，2つのグループ間も自由に移動出来ることになるので，グループを結合して1つのグループとして扱うことが出来ます．
　この処理はまさにunionfindです．円が交わっていたらunion.uniteで結合します．
　最後に始点と終点にある円が同じグループかをunion.sameで判定します．同じグループなら円を伝って終点の円周まで辿り着けます．同じグループでなかったら辿り着けません．これで判定出来ました．

class Unionfind:
...

N = int(input())
sx, sy, tx, ty = map(int, input().split())
circle_list = []
un = Unionfind(N)

for i in range(N):
    xyz = [int(i) for i in input().split()]
    circle_list.append(xyz)
    if (sx - xyz[0])**2 + (sy - xyz[1])**2 == xyz[2]**2:
        s = i
    if (tx - xyz[0])**2 + (ty - xyz[1])**2 == xyz[2]**2:
        t = i

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        ci = circle_list[i]
        cj = circle_list[j]

        dis = ((ci[0] - cj[0])**2 + (ci[1] - cj[1])**2)
        if (ci[2] - cj[2])**2 <= dis <= (ci[2] + cj[2])**2:
            un.unite(i, j)

if un.same(s, t):
    print("Yes")
else:
    print("No")