AtCoder いろはちゃんコンテスト Day2 B - 河川敷の変態仮面

目次

はじめに

• AtCoderの問題を復習しています．

• 公式解説や上位陣による解説ブログを読んで，自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います．

想定読者

• 筆者と同じくらいのレートの方：失敗談・回り道をみて，共感していただける部分もあるかもしれません．

• コンテストのwriterの方：サンプルではありますが，レート茶色上位～緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません．

記事の狙い

• 丁寧でわかりやすい解説記事がたくさん公開されているため，解法そのものについての記述は少ないと思います．

• ACに至るまでにどうしてそのような発想に至ったのか，考察や実装で試行錯誤した過程（=失敗談や回り道）を重視しています．

• また，得られた前提知識や着眼点について，今後応用できるように抽象化・言語化していきます．

• 間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．

  • 連絡先：@k_hiro1818

問題のリンク

B - 河川敷の変態仮面 (300点)

ACに至るまでの考察・実装のコツなど

考察

• 2本の直線が交差しない条件を考える．
  • 一本の直線（川）を固定してみる．
  • もう一方の直線（ある人）の始点と終点のy座標が，いずれも川の上側にある場合．もしくは，川の下側にある場合．
• 制約条件から，ある人は川の真上にいることはない．

実装で工夫した点

• y座標に着目して，ある人の始点/終点と川の距離d1, d2をそれぞれ計算する（計算誤差に注意）．
• 交差の判定自体は，計算した距離d1とd2の積が正なら交差せず，負なら交差するというように場合分け．

提出コード

試行錯誤した過程

• 川とある人の動線を直線として扱い，2本の直線が交差する座標を計算しようとした．
  • 定式化を途中まで進めたものの，実装が大変になりそうな気がしたため断念．
    
    

得られた知識・知見

• 問題分や制約条件などから得られる情報を図として書いてみる．
• どこか固定できる条件がないかを探す．
• 解法がすぐに思いつかなくても慌てない．

感想

• 提出した解法は，PythonだからACできただけかもしれないです．誤差が発生する可能性があるため．
• 想定解法が複数あるところが，競技プログラミングの面白さだと思います．
• 前提となる数学の基礎的な知識があれば楽に解けた問題かも．

課題

• 2次元ベクトルの外積について復習する．

参考

• 公式解説

• サムネイル画像

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが，@k_hiro1818までご一報ください．

関連リンク

hiro-kato.hatenablog.jp