そらの競プロ記

pythonを使った競プロ関連のことをゆるく書いていきたい AtcoderID: Sorasky

パナソニックプログラミングコンテスト2020に参加したよ

コンテストの振り返り

f:id:Sorasky:20200315020930p:plainABC相当のコンテストだったので、パナソニックプログラミングコンテスト2020に参加しました。
問題を振り返っていきます。

目次

A - Kth Term

数列をコピペしてあげてK番目(インデックスはK-1)を出力するだけですね。

ACコード
k = int(input())
a = [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(a[k-1])

B - Bishop

基本的には全体の半分のマス目に移動できることがわかります。(マス目の数が奇数のときは切り上げ)
今回注意したいのはHかWのどちらかが1のとき、駒は一切動けなくなるということです。この一点に注意してあげると後はコードを書くだけになります。
(私はこれに気付かず1ペナしてしまいました…)

ACコード
h, w = map(int, input().split())
if h == 1 or w == 1:
    print(1)
else:
    print(-(-h*w // 2))

C - Sqrt Inequality

問題文が異様に短いですね。今回のC問題は簡単だと思って素直にコードを書くと罠にはめられます。(私はここで5ペナくらいました)

WAコード
a, b, c = map(int, input().split())
if a**(1/2) + b**(1/2) < c**(1/2):
    print('Yes')
else:
    print('No')

これは浮動小数を扱うときの精度の問題で、本当は{\sqrt{a}} + {\sqrt{b}} < {\sqrt{c}}となるのに、誤差により{\sqrt{a}} + {\sqrt{b}} = {\sqrt{c}}とみなしてしまうことがあるためです。
では、どのようにしたら解けるのでしょうか。方法は2つあります。
1.単純に演算の精度を上げてしまう
2.浮動小数を避けて整数だけで解く
というものです。
それぞれのACコードを紹介しておきます。

ACコード1
import decimal
a, b, c = map(int, input().split())
if decimal.Decimal(a).sqrt() + decimal.Decimal(b).sqrt() < decimal.Decimal(c).sqrt():
    print('Yes')
else:
    print('No')

上のコードでは、decimalモジュールを用いて有効数字を指定しています。詳しくはpython公式ドキュメントをご覧になってみてください。

ACコード2
a, b, c = map(int, input().split())
if (c - a - b) ** 2 > 4 * a * b and c - a - b > 0:
    print('Yes')
else:
    print('No')

こちらのコードでは、{\sqrt{a}} + {\sqrt{b}} < {\sqrt{c}}を式変形することで整数だけの形に直して比較をしています。{\sqrt{a}} + {\sqrt{b}}, {\sqrt{c}}はそれぞれ正の数であることが保証されているので、両辺を2乗しても大小関係が変わることはありませんが、2乗して式を整理するとでてくる 2{\sqrt{ab}} < c - a - b という不等式は左辺が正の数であることは分かりますが、右辺が正であることが保証されていないので、 c - a - b > 0 という条件を忘れずに条件式をたてましょう。

D - String Equivalence


よくわからず条件分岐で書き出していっている途中にコンテストが終わりました。解法が浮かばなかったので解説のコードをpythonでそのまま書いてACです。

ACコード
#解説AC
n = int(input())

def dfs(s, mx):
    if len(s) == n:
        print(s)
    else:
        for i in range(ord('a'), ord(mx)+1):

            dfs(s + chr(i), chr(ord(mx) + 1) if i == ord(mx) else mx)
dfs('', 'a')

深さ優先探索で解けるみたいです。どうやら他にも解法はあるみたいですが、まずは何も見ずにこの方法で解けるように復習したいと思います。

最後に

前回参加したコンテストに引き続き、思ったように解くことができずに3完6ペナと惨敗でした。しかし、コーナーケースへの注意や演算の精度など、学ぶことの多いコンテストだったと思います。D問題では勉強不足が露見したので精進するしかありませんね。

f:id:Sorasky:20200315014905p:plain

蛇足

D問題を条件分岐で列挙したコードをコンテスト後に完成させましたが、サイズが大きすぎたため提出しませんでした。
少し寂しいので最初と最後の写真を載せておきます。
f:id:Sorasky:20200315020209p:plain
こんな感じで1行に10個ずつ並べていって
f:id:Sorasky:20200315020255p:plain
14259行目に終わりました！n=10のときの個数を数えてみたら115975個でした。すごいですね。