Python AtCoder 問題の意図と事象の逆を考える

今回は、Atcoder207の振り返りをしながら、

「この考え方は大事だな」と思ったところをまとめた今日プロ備忘録です。みなさんのお力になれたら幸いです。

今回のC問題

207のC問題はこちら

高校数学の「不等号と境界線」の範囲ですね。

今回はNが小さかったので、二重for分くらいなら回せそう。

これなら解けそう！

哀川ははじめに境界線の種類について考えた。

（　のときは、　liに＋0.5

）　のときは、　liに-0.5　　をして、超過と未満を表現

↑ここまでは合ってました。

そこから、lとrをべつのlistに入れてそれぞれをfor文で比べれば解ける！と思い、実際のコード

n = int(input())
from_table = []
to_table = []
for i in range(n):
   D, a, b = map(int, input().split())
   if D == 2:
       b -= 0.5
       from_table.append(a)
       to_table.append(b)
   elif D == 3:
       a += 0.5
       from_table.append(a)
       to_table.append(b)
   elif D == 4:
       a += 0.5
       b -= 0.5
       from_table.append(a)
       to_table.append(b)
   else:
       from_table.append(a)
       to_table.append(b)

ans = 0
for i in from_table:
   for j in to_table:
       if i >= j:
           ans += 1
print(ans)

ですが、これだとすべての事象を網羅できてないっぽい・・（なぜだ！！）

ということで、今回は時間切れでC問題解けませんでした。。。

復習

とまぁ、嘆いていてもしょうがないので、復習

今回も参考記事はうにさんの記事です。

【AtCoder解説】PythonでABC207のA,B,C問題を制する！ - Qiita

引用

共通部分を持つかの判定：反対を考えよう
『共通部分を持つか？』を直接判定するのは面倒です。しかし、反対の『共通部分を持たないか？』を判定するのは比較的容易です。

閉区間 [A,B][A,B] と、閉区間 [C,D][C,D] が共通部分を持たないのは以下の2パターンあります。（画像参照、[A,B][A,B] を固定して考えてみましょう）
閉区間[A,B][A,B] の右端 BB よりも、閉区間 [C,D][C,D] の左端 CC が右側にある
閉区間[A,B][A,B] の左端 AA よりも、閉区間 [C,D][C,D] の右端 DD が左側にある
条件式で表すと
B<CB<C または D<AD<A
となります。この条件式をnotで反転すれば、『共通部分を持つか？』を判定できます。

つまり、特定の事象を求めるのではなく、全事象からnotA(特定の要素)について考えるのが大事。確率の発想に近いかも。

例えば今回は、図表で表すとわかりやすかった。

図

こーゆー風に手を動かしながらわかることもある。特に図表書くと明示的で自分の理解が深まる。

あーーー！今回のC問題は解けそうだったのに！！

次回こそは！がんばります！！