寺.py

フリーランスでソフトウェア開発してます。適当にプログラミングとかスタートアップとかについて書き垂らします

AtCoderエクサウィザーズコンテスト参加録/一応緑になった話

どうもーーー


昨日はエクサコンに参加しました。

結果から言うとAB2完でした。
ただクッソ早く解いたので、(ABだけの速度なら80位だったのを確認した)、レートはめちゃ上がりました。


ようやく念願の緑。
これで当分気持ちよく寝ることができそうです。

そして解けなかったものの、Cもそこまで悪くはなかったかなと。
ちゃんと左端に落ちるやつで一番右にいるやつと、右端に落ちるやつで一番左にいるやつを求めればというところまでは
考察できましたが、二分法を使えば良いというのが湧いてきませんでした。
これは普通に精進不足。でも次からは二分法の問題出たら絶対解けると思う。
整数でsortされてたものにはいつもbisectを使ってたのですが、自分で書くとなるとなかなかできないですね。


ちゃんと翌日Cを解きました。
別解である逆順で見ていく方法も、他の方のコードを眺めて理解だけはしました。賢い。

一応書き直したつもりの提出
なかなかひどいコードですが、二分法、慣れていこうと思います。

https://atcoder.jp/contests/exawizards2019/submissions/4786891

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
s = input()
TD = []
T, D = [], []
for i in range(Q):
    t,d = LS()
    TD.append([t,d])

def get_mid(lb, ub):
    if lb + ub < 0:
        return 0
    else:
        return (lb + ub) // 2
# 左から落ちるものの探索
# 2回midが同じならやめる
def find_left_dropped():
    lb, ub = -1, N
    while True:
        if lb + ub < 0:
            mid = 0
        else:
            mid = (lb + ub) // 2
        original_mid = mid
        for td in TD:
            if td[0] == s[mid]:
                if td[1] == "L":
                    mid -= 1
                else:
                    mid += 1

                if mid == -1:
                    # 左に落ちた
                    lb = original_mid
                    if get_mid(lb, ub) == original_mid:
                        return original_mid+1
                    break
                
                if mid == N:
                    # 右に落ちた
                    ub = original_mid
                    if get_mid(lb, ub) == original_mid:
                        return original_mid
                    break
        else:
            # 落ちなかった
            ub = original_mid
            if get_mid(lb, ub) == original_mid:
                return original_mid

def find_right_dropped():
    lb, ub = -1, N
    while True:
        if lb + ub < 0:
            mid = 0
        else:
            mid = (lb + ub) // 2
        original_mid = mid
        for td in TD:
            if td[0] != s[mid]:
                continue

            if td[1] == "L":
                mid -= 1
            else:
                mid += 1

            if mid == -1:
                # 左に落ちた
                lb = original_mid
                if get_mid(lb, ub) == original_mid:
                    return original_mid+1
            
            if mid == N:
                # 右に落ちた
                ub = original_mid
                if get_mid(lb, ub) == original_mid:
                    return original_mid
                break
        else:
            # 落ちなかった
            lb = original_mid
            if get_mid(lb, ub) == original_mid:
                return original_mid + 1

left_survived = find_left_dropped()
#  print(left_survived)
right_survived = find_right_dropped()
#  print(right_survived)

result = right_survived - left_survived
print(result)


初めてのコンテスト参加が1/13で、約2ヶ月半で緑になれたのは良かった!


一応歴代成績はこんな感じ。
f:id:mktrdbg:20190401000912p:plain
最初のレーティング4ですw

精進はこんな感じでCばっかやってます。
f:id:mktrdbg:20190401000954p:plain
疲れるのでストリークとかは一切気にせずやってます。

純粋なABCのCだけで言えば36問解いてるので、そろそろD問題もちょいちょいやっていこうと思ってます!

あとtwitterでもちょこっと書きましたが、メキシコ人の彼女が日本に来ます。
なのでコンテストあんま参加できなくなるかもーという懸念があるのですが、それとは別に
緩募な感じで、獣医のニーズがあるか知りたいです!

スペック
日本にもうすぐ住む予定
メキシコ国立自治大学で獣医資格持ち
日本語は割と知ってるけど、これからもっと勉強
英語はまあいけます
(スペ語ネイティブ)
26歳

私としては、スタートアップとかで動物系があればアツいなーと思ってるのですが、、、
まあとにかく今後仕事探すことになるので、何か知ってれば教えてほしいです!