AtCoder Beginner Contest 076

2017年10月28日のAtCoderの記録。言語はpython 3です。

概要

問題：AtCoder Beginner Contest 076
私の回答一覧：自分の結果
制限時間：100分
5分でA、7分でB、28分でCを完答した。
翌時解き直してDを完答。これ、400点の問題にしてはなかなか難しいと思う。

パフォーマンス：なし
レート：1400(レート変動の対象外)

A問題

2*G-Rを出力。

B問題

毎回の操作で、加算と2倍のうち小さい方を選べば良い。

C問題

模範解答どおり。
文字列から部分を取り出すときに、全体の端から指定したいときは単に[:3]や[3:]と書けばよい。これはrubyには無い便利なやり方だな。

「本当は正しいアルゴリズムではないが、テストケースが不十分なためACとして通ってしまう」という現象、俗に言う「嘘解法」が発生したらしい。
「tを配置すると制約が発生するので、その分をaで埋められなくなり辞書順で後ろになってしまう。従って、tを最も後方に配置できるものが正解である」という考え方は、一見正しそうだ。しかし
s' = "z?"
t = "z"
のときに、この解法はtを最後に配置して"zz"を出力してしまう。
正解は"za"である。
したがって、文字列tが配置の方法のうち、辞書順が一番前のものを調べる必要がある。

s0 = (input())
t = (input())

flag = False #解の候補が見つかったか否かのフラグ。

ans = ""
lt = len(t)
for i in range(len(s0)-len(t) + 1):
    flag2= True
    for j in range(lt):
        if s0[i+j] != t[j] and s0[i+j] != "?":
            flag2 = False
            break
    if flag2:
        flag = True
        temp = s0[:i] + t + s0[i+lt:]
        temp = temp.replace('?', 'a')
        if ans == "" or temp < ans: #この行を抜かすと「嘘解法」になる
            ans = temp

if(flag == False):
    print ("UNRESTORABLE")
else:
    print (ans)

D問題

模範解答どおり……だとTLEになって通らなかった。
詳細な説明はカッとなって画像に書いたので参照してほしい。

計算量は高々400万程度で、結構余裕で間に合うはずなのに
浮動小数点の演算を少し削ったり、if文を削除してみたけど処理時間は殆ど変わらなかった。
小手先の変更では制限時間内には終わらないので、計算量をちゃんと落とす必要がありそうだ。

グラフ中で、橙色の点線は区間の先頭で1本増えるが
その後は増えることはあり得ない。
従って、区間の先頭以外では、橙色の点線の最小値は「直前の値+0.5」である。
これにより計算量は半分に減少する。
この変更を入れたら何とか通ってくれた。

C++(のような速い言語)でも通すのに苦労した人も少なくないようだ。

n = int(input())

tt = list(map(int, input().split()))
v = list(map(int, input().split()))

time = sum(tt);
INF = 999999
border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
    temp += tt[i]
    border[i+1] = temp
    start_v[i] = v[i]
    end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0
new_interval = False
limitation_front =0 # 最初の計算に必要

# print (border)
while t < time :
    t += 0.5
    new_interval = False

    #直接制約
    v0 = v[idx]
    if t == border[idx+1]:
        idx += 1
        new_interval = True
#       v0 = min(v0, v[idx])

    if(not new_interval):
        limitation_front += 0.5
        if v0 > limitation_front:
            v0 = limitation_front

    if new_interval: 
        limitation_front = INF
        for j in range(n+1):
            if border[j] <= t:
                #前の時刻からの制約
                temp = end_v[j] + (t - border[j])
                if v0 > temp:
                    v0 = temp
                if limitation_front > temp:
                    limitation_front = temp
            else:
                break
            #print (limitation_front)

    for j in range(n+1):
        if border[j] >= t:
            #後ろの時刻からの制約
            temp = start_v[j] + (border[j] - t)
            if v0 > temp:
                v0 = temp

    #print(v0)
#   ans += 0.5 * (vlast + v0) / 2
    ans += (vlast + v0)
    vlast = v0

ans /= 4.0
print (ans)