脳log[20230817]

2023年08月17日 (木) [AtCoder] 精進１。ABC149-F「Surrounded Nodes」(黄 diff)。前前前回の ABC312-G「Avoid Straight Line」(20230729) を思い出させる問題だった。今日の問題のキーワードは「主客転倒」と「余事象」。ひとつひとつの頂点が穴だと数えられる場合の数を数えて最後にその和を全体で割った。提出 #44647884 (AC / 337 Byte / 588 ms)。■精進２。ABC136-F「Enclosed Points」(黄 diff)。シンプルな問題。これもキーワードは「主客転倒」と「余事象」、それと「包除原理」だろうか。ひとつひとつの点について f の値に寄与する集合 T の数を数えたい。裏返して、寄与しない T の数を数える。それは、T が左(、上、右、下)にある点だけからなる場合。T が左上(、右上、右下、左下)にある点だけからなる場合を重複して数えないようにする。左上にある点の数を数えるのに BIT を使った。提出 #44669970 (AC / 687 Byte / 1095 ms)。