AtCoder ABC207
ABC207参加しました。
A - Repression
3枚から二枚選ぶときの方法は(A,B), (B,C), (C,A)の3通りだけなので、それぞれの和を出して最大となるものを取ります。
解説 - AtCoder Beginner Contest 207
B - Hydrate
公式解答にもある通り、O(1)の解法が存在します。A,B,C,Dの関係性を文字式で表すとわかりやすいでしょう。
解説 - AtCoder Beginner Contest 207
C - Many Segments
"(", ")"のときは、ぴったりの値よりちょっとだけ大きく/小さくしてあげることで、判定が楽になります。
自分は"("のときは、+0.1, ")"のときは-0.1だけ値を小さくしてあげました。
なお、定数倍することで、全て整数演算で解けるようになるようです。
解説 - AtCoder Beginner Contest 207
D - Congruence Points
公式解説動画にもある通り、すべての点が整数になるという制約から、90度ずつ回せばいい、という考えにハマると、この問題は解けません。
例えば(5,0)という点は(3,4)という点に、約53度程度回すことで一致させることができます。 3:4:5の長さの比の直角三角形を思い描きましょう。
よって、ちゃんと回す角度を考えないといけません。
以下の解説を読んでACをとったコードを解説してみます。
解説 - AtCoder Beginner Contest 207
コードはこちら。計算量はかなりギリギリ。
提出 #23849264 - AtCoder Beginner Contest 207
方針としては、まずSの1点を選び$S_1$とします。これを原点に持っていきます。 他のSの点もそれに合わせて平行移動させます。
次にTから1点選んで($T_i$とします)原点に移動させます。他のTの点も平行移動させます。
これで、$S_1$,$T_i$を原点で一致させることができました。 他の点を一致させることができるでしょうか?
ここでは、他の点を回転のみで一致させることができるかを考えます。もし一致させられたら、もちろん答えを出力できますし、できない場合は、$T_i$を別の点で試して同じことを繰り返します。
肝心の回転角度は、$S_1$以外の点$S_j$を1点選び取り、ベクトル$ \overrightarrow{ S_1S_j }$を計算します。これとX軸との偏角をatan2()で計算した結果をradSとします。次に同様にTから$T_i$以外の点$T_k$を1点選び取り、ベクトル$\overrightarrow{ T_iT_k }$を計算します。これとX軸との偏角をatan2()で計算した結果をradTとします。ここから偏角同士の差radT-radSを出すことで、$S_j$を$T_k$に回して一致させる角度を計算できます。atan2(y,x)は言語によっては、atan2(x,y)の場合もあるので注意しましょう。
※そもそも回転して一致できる場合は、それぞれの点の原点からの距離が一致している必要があるため、予めチェックしておくと、余計な回転角度でのチェックを省けます。
後は、Sを回転させた点群がTと一致するか(Sの中での登場順序は問わないことに注意)を見てあげればいいです。
解説 - AtCoder Beginner Contest 207
まとめ
D問題は幾何ライブラリを持っていない人は大変そうです。2次元の平行移動、拡縮、回転程度ならすぐに作れると思うので、持っておくと何かと楽かもしれません。というか、幾何ライブラリがないと、コードがかなり見にくくなりそうです。
