B - 同一円周上 arc047_b 解となる候補点は高々4つだろうか？

Quiz

https://atcoder.jp/contests/arc047/tasks/arc047_b

Submit

https://atcoder.jp/contests/arc047/submissions/4230646

Note

• editorialのように候補点4つを求める
• 最後にマンハッタン距離が等しいことを確認してprint
• 候補の4つともチェックは通っていた
  • 通らないケースもあるのだろうか？

解となる候補点は高々4つだろうか？

• テストケース2のように、無限にある場合もある
• 下図のような例を考えると、候補点は5つ
  • 元々の座標系で答えは(5, 3)
  • 変換後の座標系で答えは(8, 2)
  • editorialの解法ではPxの候補は 6, 10しか求まらない (8も求まるべき)
  • Xmax, Xminの点に正方形の角を合わせようとするとeditorialのようになる
• 今回の解答は、たくさんの解の中の4点を見つける方法ということだろう

コメント

• 私が何か考え間違いをしていれば、コメント頂けると幸いです！

C - エックスオア多橋君 arc045_c

Quiz

https://atcoder.jp/contests/arc045/tasks/arc045_c

Submit

https://atcoder.jp/contests/arc045/submissions/4227512

解法

• 任意の点からdfsしてxorを求めれば、xからyまで辿ったときのxor和はx -> root -> y から一瞬で求まる
• 任意の点からdfsしてxor和を求め、mapでカウントする
• カウントを使って「この点からこの点に行けばxor和＝Xになる」数を求めれば答え

Notebook

Notebook 2 (コーナーケース)

B - ドキドキデート大作戦高橋君 arc045_b

Quiz

https://atcoder.jp/contests/arc045/tasks/arc045_b

Submit

https://atcoder.jp/contests/arc045/submissions/4225127

Note

• Bにしては難しい？
• 解き方はeditorialの通り
• 範囲の判定にフラグと累積和を使うのは汎用性がありそう
• その範囲を削っても大丈夫かの判定に、始点の1つ前を見る必要があるのがポイントだろう

B - アリの高橋くん arc042_b 「線分と点の距離」を複素数で (二次元)

Quiz

https://atcoder.jp/contests/arc042/tasks/arc042_b

Submit

https://atcoder.jp/contests/arc042/submissions/4201752

Note

• (追記：この記事には考慮漏れがあります）
• 各線分と点の距離を求めればいい
• 複素平面上で考える
• editorialの通り、c2 - c1からなるベクトルの偏角を0にするようにPを回転する
• 複素数において、
  • かけ算は反時計回り
  • よって時計回りにしたいときは割り算をすればいい
• スケールは変えたくないので単位ベクトルで割る
• Pを回転させたあとのy (imag) が点と線分の距離 d である

• 回転のイメージは画像の左側に描いてある
• しかし、画像右のような場合はどうだろう、上記方法では間違った距離が求まってしまう
• 赤線で描いた距離を返すのが正しい

typedef complex<double> cd;
 
double distance(cd p0, cd c1, cd c2){
    // c1原点に移動
    p0 -= c1;
    c2 -= c1;
 
    // 回転
    auto u = c2 / abs(c2);
    p0 /= u;
 
    return p0.imag();
}

B - 直線塗り(arc040_b)

Quiz

https://atcoder.jp/contests/arc040/tasks/arc040_b

Submit

https://atcoder.jp/contests/arc040/submissions/4193926

Other's Submit

https://atcoder.jp/contests/arc040/submissions/3967511

Note

• 長々と書いてしまった
• うまく書けなかった時は通った後でも他の人の提出を参考にする

真似したいポイント

• 答えは print(pos + shot_num)
• 私は移動したときもカウントを進めていたが、最終位置＝移動数なので発射のみカウントすればいい