茶色コーダーがパナソニックコンテスト2020A~C解いてみた

はじめに

パナソニックプログラミングコンテスト2020　3完(Python3 95:30 8WA)できたのでA~Cの解法を投稿します。

パナソニックプログラミングコンテスト2020のリンクはこちら
https://atcoder.jp/contests/panasonic2020

目次

• A-Kth Term
• B-Bishop
• C-Sqrt Inequality

A-Kth Term

問題文

次の長さ32の数列のK番目の項を出力してください。

1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51

https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_a

この数列をリストにいれてしまって入力されたK番目を出力すれば良いと考えます。

提出コード

main.py

k = int(input())
x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(x[k-1])

B-Bishop

問題文

縦Hマス、横Wマスの盤面があります。この盤面の左上隅のマスに角行の駒が置かれています。コマが0回以上の好きな回数の移動が繰り返して到達できるマス目は何個あるでしょうか
例えば、コマが図のところにある時、1回で移動できる場所は赤くなっているマスです。

https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_b

問題文をぱっと見てもさっぱりわかりません。
そこで、入力例1、入力例2の図を眺めると、色のついたマスはマスの数hw/2を切り上げた数であることに気づきます。

しかし、下記の図のようなh=1もしくはw=1の場合必ず色がつくマスは1です。

提出コード

main.py

import math
h,w = map(int, input().split(' '))
if h == 1 or w == 1:
    print(1)
else:
    res = math.ceil(h*w / 2)
    print(res)

C-Sqrt Inequality

問題文

$\sqrt{a}+\sqrt{b}<\sqrt{c}$　ですか？
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c

問題文を安直にそのままコードを書くとこう。

main.py

import math

a,b,c = map(int, input().split(' '))
if math.sqrt(a) + math.sqrt(b) < math.sqrt(c):
    print('Yes')
else:
    print('No')

これだと、WA出ます。そこで
$\sqrt{a} + \sqrt{b} > 0 $かつ$\sqrt{c}>0$から
$\sqrt{a}+\sqrt{b}<\sqrt{c}$
$\Rightarrow a+2\sqrt{ab}+b<c$
$\Rightarrow 4ab < (c-a-b)^2$
と式変形して、無限小数にならないようにします。こうすることで桁落ちがなくなるようにします。
違いを確かめたコードが下記。確かにWAが出てしまいますね。

追記：下記のコードが間違っていたため修正しました。(2020/3/16)

check.py

from math import sqrt as sq
a = 250000000
b = 250000000
c = 10**9
while sq(a) + sq(b) >= sq(c):
    a += 1
    b -= 1
    print(a,b)
    print(4*a*b, (c-a-b)**2)
    print(sq(a)+sq(b)<sq(c))
    print(4*a*b < (c-a-b)**2)

250000001 249999999
249999999999999996 250000000000000000
False
True
250000002 249999998
249999999999999984 250000000000000000
False
True
250000003 249999997
249999999999999964 250000000000000000
False
True
250000004 249999996
249999999999999936 250000000000000000
False
True
250000005 249999995
249999999999999900 250000000000000000
False
True
250000006 249999994
249999999999999856 250000000000000000
False
True
250000007 249999993
249999999999999804 250000000000000000
True
True

提出コード

main.py

import math

a,b,c = map(int, input().split(' '))
x = 4 * a * b
y = c - a -b
if y <= 0:
    print('No')
elif  x < y**2:
    print('Yes')
else:
    print('No')

c-a-b<0となることもあります。