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問題解けませんでした。。。
復習
とまぁ、嘆いていてもしょうがないので、復習
今回も参考記事はうにさんの記事です。
引用
共通部分を持つかの判定:反対を考えよう
『共通部分を持つか?』を直接判定するのは面倒です。しかし、反対の『共通部分を持たないか?』を判定するのは比較的容易です。
閉区間 [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問題は解けそうだったのに!!
次回こそは!がんばります!!
この記事が気に入ったらサポートをしてみませんか?