roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder SRM 644 Div2

10度目のSRM。残念ながらサーバー側の問題でノーコンテストとなってしまった。調子が良かっただけに残念。

正の整数のリストが与えられる。リストから2つの数字を選んだ時、値の差がK以下ならば有効であるとしたとき、有効な組はいくつあるかを答える問題。

リストのサイズが最大50なので単純に2重ループを回してすべての組み合わせについて調べればよい。

Easy 250

def count(self, osize, K):
    ans = 0
    for i in range(len(osize)):
        for j in range(i+1,len(osize)):
            if abs(osize[i]-osize[j]) <= K:
                ans += 1
    return ans

Medium 500

文字列リストLが渡される。文字列の中には”?”が含まれている場合があり、それぞれある英小文字に置き換えなければならない。文字の置き換えを行った後、それぞれの文字列の辞書順位のありうるもっとも小さい値を答える問題。

ここで知りたいのはある文字列のありうるもっとも小さい辞書順であることに注目する。i 番目の文字列に含まれる”?”を”a”に、それ以外の”?”を”z”に置き換えて辞書順位を調べればi番目の文字列の最低辞書順を知ることができる。

def getmins(self, str):
    ans = [100]*len(str)
    for i in range(len(str)):
        nstr = list(str)
        nstr[i] = nstr[i].replace("?","a")
        nstr = [ele.replace("?","z") for ele in nstr]
        snstr = sorted(nstr)
        for j in range(len(nstr)):
            ans[j] = min(ans[j],snstr.index(nstr[j]))
    return ans

Hard

まだ解いてない

広告を非表示にする