AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の33問目である「033 – Not Too Bright（★2）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【033 – Not Too Bright（★2）】
入力
H,W : LEDの個数(縦),LEDの個数(横)
考察
はじめに H ==1 or W == 1のとき
「イルミネーション全体に完全に含まれる 縦2 × 横 2 の、4 つの LED を含む領域であって、点灯している LED が領域内に 2 つ以上あるものが存在する。」
と言われているので、H or Wが1のときは上記の条件を考える必要がありません。
なので、H ==1 or W == 1のときは、すべてのLEDを点灯させることができます
H >= 2 and W >= 2の場合
今回H,W <100なので、素直に全探索します。
例えば1を点灯,0を消灯とした場合
[1,0,1,0,1
0, 0,0,0,0
1,0,1,0,1]のとき条件を満たします。このように点灯させた場合以下のような規則性があることに気づきます
・H%2==0行目かつW%2==0の場所にのみ点灯
そのため、上記の条件を満たすコードを書けば良いです。
コード
import math
H,W =map(int, input().split())
if H ==1 or W == 1:#2 x 2じゃないとき
print(H*W)#すべてのLEDを点灯
exit()
w_max = math.ceil(W/2)#2で割って切り上げ
h_max = math.ceil(H/2)#2で割って切り上げ
print(w_max*h_max)まとめ
前の問題【032 – AtCoder Ekiden（★3）】
次の問題【034 – There are few types of elements（★4）】
コメント