More Related Content
What's hot (20)
More from AtCoder Inc. (20)
Recently uploaded (8)
AtCoder Beginner Contest 016 解説
- 2. 问题础12月6日
- 4. 解法 月と日を標準入力から受け取る 割り切れる？ YESを出力 NOを出力 NO YES 入出力?条件分岐が必要 練習問題や他の人の解答を参考にして学んでください
- 6. 問題概要 入出力が与えられるので ?A+Bだとわかる ?A-Bだとわかる ?どちらの可能性もある ?どちらでもない を判定する
- 7. 解法 A+B＝CかつA-B≠C → A+Bだとわかる A+B≠CかつA-B＝C → A-Bだとわかる A+B＝CかつA-B＝C → どちらの可能性もある A+B≠CかつA-B≠C→ どちらでもない 場合分けを正確に漏れ無くやりましょう
- 8. 問題C 友達の友達
- 9. 問題概要 SNSの友達関係が与えられるので、 各ユーザの友達の友達の人数を求めよ 要するに、 無向グラフが与えられるので、 各頂点から距離２の頂点がいくつあるか求めよ ユーザ1 ユーザ2 ユーザ3 入力例1のグラフ 頂点 辺
- 11. 解法２ ?頂点を２つ選んで友達の友達か調べる →共通の友達がいる （かつ、自分自身または友達ではない） 共通の友達
- 12. 解法３ ?全頂点間の最短経路を求め、 各頂点から距離２の頂点を数える →ワーシャル-フロイド法や ダイクストラ法などを使いましょう （類題）ABC#012 D問題
- 13. 問題D 一刀両断
- 16. 考察 分割された多角形の数 ＝切っている線分（青）の本数＋１ もうちょっと考えると…
- 17. 考察 分割された多角形の数 ＝多角形と線分の交点（紫）の数÷２＋１ ＝線分と交差する多角形の辺の本数÷２＋１ これなら数えられそう
- 18. 解法 辺と線分が交差 →線分同士の交差判定を使う 片方の線分から見て もう一方の線分の端点が左右にある 右 右 左 左
- 19. 解法 線分から見た左右の判定方法は？ →符号付き面積を使いましょう 公式：?=(?1?2??2?1)/2 + -
- 20. 解法 まとめると、 分割された多角形の数 ＝切っている線分の本数＋１ ＝多角形と線分の交点の数÷２＋１ ＝線分と交差する多角形の辺の本数÷２＋１ 線分同士の交差判定は符号付き面積を使う