5 全探索1 Dif:21 ABC190 B：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/f2bb2fde590bc11e7cfb
次：https://qiita.com/sano192/items/b2b22aa77ad6da118c3e

【目標】
・全探索で間に合うかを判断できるようになる。
・全探索で必要な操作を実装できるようになる。

【概要】
全ての場合を試してみることを「全探索」という。「全探索」は基本のやり方で、ABCのA~C問題まではほとんどこの方法で解ける。どのような場合に「全探索」を行うのか、どうやって実装するのかこの問題で理解しよう。

【方針】
問題文はダメージを与えられない条件が書いているが、1つでもダメージを与えられる呪文があれば「Yes」となるので、逆にダメージを与えられる条件を考えよう。

問題文にあるダメージを与えられない条件は以下。
・詠唱にS秒以上かかる → S<=X
または
・威力がD以下 → Y<=D

これを逆にして、ダメージを与えられる条件を考える。
・詠唱がS秒より小さい → X<S
かつ(しかも)
・威力がDより大きい → D<Y

次に全ての魔法について上記条件を確認して解けるか、つまり「全探索」で解けるかを判断しなければならない。

制約を見よう。　
実行制限時間：2sec(2秒)
呪文の種類：1<=N<=100

よって2秒以内に最大100種類の呪文を試せるか？が判断基準となる。
pythonでは2秒以内にだいたい1000000=10^6回程度の計算ができる。
100回の計算なら余裕で間に合うので、全ての呪文を試してもTLE(実行時間制限超過)しない。
全探索で間に合うか？の目安は計算回数がだいたい10^6回以下と覚えよう。

計算量については解説でよくO(N)という書き方をしている。
厳密に説明すると難しい話なのだが
O(N)=N回くらいの計算が必要
という意味だと覚えよう。
O(N^2)=N^2回くらいの計算が必要
O(logN)=logN回くらいの計算が必要(logの底は2)
と覚えておけば良い。

この問題はN種類の呪文について計算が必要なので、
O(N)で解ける
という言い方をする。

計算量について詳しく知りたい人はWikipediaを参照してほしい。
https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#%E4%B8%80%E8%88%AC%E7%9A%84%E3%81%AA%E3%82%AA%E3%83%BC%E3%83%80%E3%83%BC

【実装】
入力を受け取る。X,Yがいくつもあって戸惑うかもしれないが、for文で一つずつ受け取ればよい。

N,S,D=map(int, input().split())

for i in range(N):
    X,Y=map(int, input().split())

受け取ったX、Yについて以下の条件を満たすか判定する。
・詠唱がS秒より小さい → X<S
かつ(しかも)
・威力がDより大きい → D<Y
もし条件を満たすものが一つでもあれば「Yes」を出力して終わり。
途中で終了する場合は exit()と書く。

for i in range(N):
    X,Y=map(int, input().split())
    if X<S and D<Y:
        print("Yes")
        exit()

ひとつも条件を満たすものがなかった場合、途中で終了することなくループが終わる。
そこで「No」を出力すれば完成だ。

print("No")

【コード全文】

N,S,D=map(int, input().split())

for i in range(N):
    X,Y=map(int, input().split())
    if X<S and D<Y:
        print("Yes")
        exit()

print("No")

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/f2bb2fde590bc11e7cfb
次：https://qiita.com/sano192/items/b2b22aa77ad6da118c3e