そらの競プロ記

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個でした。すごいですね。

ABC158に参加したよ

コンテストの振り返り

ABC158をゆる～く振り返っていきます。

目次

A - Station and Bus

文字列SにA,Bが両方含まれているか否かを判定するだけですね。

ACコード
s = input()
if 'A' in s and 'B' in s:
    print('Yes')
else:
    print('No')

B - Count Balls

先頭から最大10^{18}個のボールを見ていくわけにはいかないので簡単な方法を考えます。
1回の操作で加えられるボールを1セットとし、N個に含まれるセット数とその余りを出せば計算できますね。

ACコード
n, a, b = map(int,input().split())
c = a + b  #1セットのボール
d = n % c  #先頭からN個取った時、セットにならなかったボール(余り)
ans = (n // c) * a
if a <= d:
    ans += a
else:
    ans += d
print(ans)

C - Tax Increase

制約から全探索が見えてきますね。小さい方から探して終わりです。コンテスト中はなぜか上限を110にしてWA、その後焦って999にして2ペナです…。

ACコード
import math

a, b = map(int, input().split())

for i in range(b+1,1010):
    if math.floor(i * 0.08) == a and math.floor(i * 0.1) == b:
        ans = i
        break
else:
    ans = -1
print(ans)

この問題、解説PDFを見ると

課題 : O(1) で答えを求めてください。

との一文が。
ということでやってみました。

O(1)コード
a, b = map(int,input().split())
if b * 10 <= (a * 25 + 24) // 2 and -(-a * 25 // 2) < (b + 1) * 10:
    print(max(-(-a*25//2), b * 10))
else:
    print(-1)

D - String Formation

与えられた手順に従って文字列を操作していく問題です。制約から文字列の反転操作を正直にやっていては間に合わないことがわかるので、文字列が反転しているかという情報だけを保持しておいて文字を追加していき、必要があれば最後に反転させるという手順で解けます。
しかしここで注意したいのは時間計算量です。長さnの文字列の先頭に文字を追加するとき、insert(0, v)としてしまうとO(n)かかるため、TLEになってしまいます。
そこでdequeを使うことにより、この問題を解決することが可能になります。
Python公式ドキュメントでは、以下のように記されています。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

今回の問題では、文字列の先頭末尾への操作しか必要がないため、dequeが適しているのがわかると思います。これを用いたコードが以下になります。

ACコード
from collections import deque

s = input()
q = int(input())
ans = deque(s)
cnt = 0
for i in range(q):
    f = [i for i in input().split()]
    if f[0] == '1':
        cnt += 1
    else:
        if f[1] == '1':
            if cnt % 2 == 0:
                ans.appendleft(f[2])
            else:
                ans.append(f[2])
        else:
            if cnt % 2 == 0:
                ans.append(f[2])
            else:
                ans.appendleft(f[2])
if cnt % 2 != 0:
    ans.reverse()
print(''.join(map(str,ans)))

最後に

今回はdequeや文字列操作の時間計算量を知らず、コンテスト中にD問題をACすることができなかったため3完2ペナ茶パフォと大敗北を喫しました。
コンテスト成績
しっかりと復習や精進をして、次回は今回の分も取り戻したいですね。