今日は包除原理について少し勉強したよ
昨日やったABC003-dの問題の解説で包除原理を使うという事を目にしたので、今日は包除原理について少し勉強しました。といっても記事にできる事は何もないのですが( ;∀;)
個人的なメモです。
これのD問題のラスト1点部分について
求めたいもの(灰色)は
|U|-白色の部分
なんですけど、白色の部分が、
それぞれ円の和 - 2つの円の共通部分の和 + 3つの円の共通部分の和 - 4つの円の共通部分の和
これで求められるらしいんですよね。記号で表すと、
|T| + |R| + |B| + |L| //それぞれの円の和 -(|T∩R| + |R∩B| + |B∩L| + |L∩T|) //2つの円の共通部分 +(|T∩R∩B| + |R∩B∩L| + |B∩L∩T| + |L∩T∩R|) //3つの円の共通部分 - |T∩R∩B∩L| //4つの円の共通部分
です。多分。
この理論でプログラムを実装してみたんですけど、一向に正答しないんですよね。
プログラムの実装の仕方でミスしてるのか、そもそもこの考えが間違っているのかわからなくて悩んでます。
しばらく棚上げですかね。
終わりに
ここまで読んでくださってありがとうございます!
今日はAtCoderのコンテストがあるため記事は簡略で早めに終わろうと思います。
機能やった問題を完答させることはできませんでしたが、しばらく寝かしておきます。もしかしたら、未来の成長した私が見事解いてくれるかも?(*'ω'*)
スター、ブックマーク、読者登録ありがとうございます!ものすごく励みになっています!そういえば豊田議員書類送検されたようですね
またね('ω')ノ