簡単な問題だが、ハマった
問題はこれ。
AtCoder Problemsをやっていて序盤でハマった。
簡単に見えて意外と通らず、しかも通ったあともめちゃくちゃ無駄に気付いたので考察過程を投稿しておく。
コーナーケースの考慮漏れ
少し考えると、チェッカーボードのごとく塗られるのがわかる。
しかし、1行または1列の場合は移動が不能なので回答すべきは\(1\)となる。
この考慮もれをした人は本番でも多かった模様。
無駄に複雑化してしまった解答
自分が当初書いたのがこれ。
h,w=map(int,input().split())
print(int(((h*w/2,w*(h//2)+(w+1)//2)[h&1],1)[h==1 or w==1]))これだと場合分けをタプル化していてちょっと読みにくいので、通常の場合分けに戻す。
h,w=map(int,input().split())
if h==1 or w==1: # コーナーケース
res = 1
elif h%2==0: # 行数の偶奇で場合分け
res = int(h&w/2)
else:
res = int(w*(h//2) + (w+1)//2)
print(res)どう考えたか
2行ごとに注目すると、塗られる数がちょうどwとなる。
つまり、hが偶数行なら\(\displaystyle \frac{wh}{2}\)で求まる。
奇数なら、w*(h-1)/2にwを切り上げ除算した値を加えればよいと考えた。
もっと単純化できた
上記のような小賢しい場合分けなどせずとも、チェッカーボードなのだからすべてのマスの数を切り上げ除算するだけで事足りた。
つまり、コードはhの場合分けをせず(w*h+1)//2のみでよかった。
悩んだこと
(h*w/2,w*(h//2)+(w+1)//2)[h&1]と(w*h+1)//2は本質的には同じことをやっているはずだが、切り捨て除算を含んだ場合にどう整式しうるかがパッとわからなかった。
被除数が偶数の場合
被除数に1足してから切り捨て除算行っても結果は同じ。これは言われてみれば当たり前。
if x%2==0:
res = x/2 == (x+1)//2 # -~x//2とも書ける
print(res)
# True被除数が奇数の場合
奇数の場合はint(w*(h//2) + (w+1)//2)という式なので、これを簡単にすることを考える。
偶数の場合と逆で、被除数から1を引いて通常除算するのと同じことになる。
if x%2!=0:
res = x//2 == (x-1)/2 # ~-x/2とも書ける
print(res)
# Trueしかし、wに関する切り捨て除算もあるので、この場合分けも考慮すると以下となる。
if w%2==0: # (w+1)%2!=0でもよい
res = w*(h-1)/2 + w/2
else:
res = w*(h-1)/2 + (w+1)/2こうするとすべて通常除算に戻るので、自由に整式が可能である。
if w%2==0:
res = w*h/2
else:
res = (w*h+1)/2ここまでくると、なるほど納得である。なぜなら、そもそも切り捨て除算は以下の挙動だからである。
if x%y==0:
res = (x//y == x/y)
elif:
res = (x//y == (x-1)/y)
print(res) #True 結局、wの偶奇によらず(w*h+1)//2と等価であることがわかった。
まとめ
偶奇と2除算が絡む場合は、切り上げ除算や切り捨て除算で場合分けを吸収できないかよく検討するとよい。
まとめられるなら、もっと一般化・単純化した問題の捉え方があるはず。
コメント