ZONeエナジー プログラミングコンテスト “HELLO SPACE” 参戦記

現在の時刻は2021年5月1日AM7:00、俺はキャンピングカーで娘の習い事の待ち時間に先日のAHC002の復習をしている。
TLに流れてきたDFSでの解法を自分で実装するためだ。
今日の夜は ZONeエナジー プログラミングコンテスト “HELLO SPACE” があるから、コードを書く練習としても、DFSの復習としても最高の題材だ。
AtCoderでのコンテストの開催をしてくれるらしい。
AHC002のDFS解をあまり詰まることなく書けたぞ。
もしかしてこれはZONeエナジー ‘mad_hucker’ のおかげなのか!?

ということで(？)、ZONeエナジー プログラミングコンテスト “HELLO SPACE” に参加したので、その参加記録として本記事を書いていきます。
私は、レート500ちょっとの茶色コーダーです。使用言語はPython3を利用しています。

A – UFO襲来

文字列の取り扱いについて問われる問題。Python3 では、文字列に対して、count() を使用することで部分文字列の個数を数えることができます。

# ZONeエナジー プログラミングコンテスト “HELLO SPACE”
# A - UFO襲来

S=input()

print(S.count("ZONe"))

B – 友好の印

数学的な考察が要求される問題。私は自作の座標に関するライブラリを使用して解きました。
B問題にしては、すごく難しい部類に入ると私は思いますが、入力例の図が優しすぎですね。

入力例の通り、x,y平面で考えて、UFOと各遮蔽物を結んだ直線のy軸との交点の最大値が答えになります。タワーを登る必要がある高さの最小値を求めるので、最初は、タワーの麓とUFOとを直線で結んだ高さなので0を初期値として、各遮蔽物を調べていけば良いですね。
また、制約より、UFOと同じ距離には遮蔽物はないことがわかっているため、x,y平面の直線の傾きが1になることも考えなくて良いことも分かります。

2点を結ぶ直線の傾きを求めてから、y切片を求めればOKですね。

# ZONeエナジー プログラミングコンテスト “HELLO SPACE”
# B - 友好の印

N,D,H=map(int,input().split())

ans=0

for _ in range (N):
    d,h=map(int,input().split())
    a=(H-h)/(D-d)   # 傾きを求める
    b=H-a*D         # y切片を求める
    ans=max(ans,b)

print(ans)

D – 宇宙人からのメッセージ

今回は、C問題とD問題の得点が逆転しており、C問題は解けませんでした。D問題はいつものABCのC問題と同程度の難易度のようで、D問題を解いています。

状態管理とキューの利用を問われる問題。非常によく似た類題はこちら(ABC158-D:String Formation)です。

文字列を反転させる事はPython3では S[::-1] で可能ですが、毎回実行すると処理時間が間に合わなくなります。このため、状態を管理するフラグを持って置き、今が通常の状態なのか、反転している状態なのかをこのフラグで判定します。

また、list は、データを末尾に追加/削除することは高速に実施できますが、先頭に追加するのは処理時間がかかります。
配列(のようなもの？)の両端に高速でアクセスできるデータ構造に deque があるのでこれを利用します。

追加しようとする文字が端の文字と同じならば、追加せずもせず、端の文字を削除するようにします。
deque での要素の追加は、末尾の場合は通常のlistと同様に、append() を利用し、先頭の場合は appendleft() を利用すればOKです。要素の取り出しも同様で、末尾の場合は、pop() を利用し、先頭の場合は popleft() と単純なルールになっているのが嬉しいですね。

最後、反転している状態なら文字列を反転させ、あとは文字列連結で回答を出力すればOKです。

# ZONeエナジー プログラミングコンテスト “HELLO SPACE”
# D - 宇宙人からのメッセージ

from collections import deque

S=input()

q=deque()
nomal=True

for i in range (len(S)):
    if S[i]=="R":
        if nomal==True:
            nomal=False
        else:
            nomal=True
    else:
        if len(q)==0:
            q.append(S[i])
        else:
            if nomal==True:
                ql=q[-1]
                if S[i]==ql:                    
                    q.pop()
                else:
                    q.append(S[i])
            else:
                qr=q[0]
                if S[i]==qr:
                    q.popleft()
                else:
                    q.appendleft(S[i])

if nomal==False:
    q=list(q)[::-1]
else:
    q=list(q)

print("".join(q))

今回のコンテストはちょっとしたストーリーがあったことなども含めてすごく楽しかったです。

AtCoderFindRivals(WebApp)の宣伝

AtCoderでレートや最高レート、参加回数から自分のライバルになると思われるユーザーを探せるAtCoderFindRivalsを公開しています。

使ってもらえると嬉しいです。