みんなのプロコン - D言語で競プロ

参加しました、結果は３完でした
自分の実力からすると妥当なところだと思いますが、Cをミスすることなくしっかり通せたのは良かったと思います

A.o
B.o
C.o
D.x

A - Yahoo

与えられた文字列を並び替えて、yahooという文字列を作れるか？ですね。
与えられた文字列の中に、yがちょうど1個、aがちょうど1個、hがちょうど1個、oがちょうど2個あれば作れますし、そうでなければ作れません。
いろんなやり方があると思いますが、手っ取り速いのは与えられた文字列をソートして'ahooy'になるかを見るのが楽そうですかね。
ただ文字列の扱いに慣れてない私は文字列ソートって出来るのか？　文字列ってimmutableだからソートしようと思ったらめんどくさいんじゃ？
って感じて、最初飛ばしてBに行きました。

それで戻ってきて実際書いたコードがこんな感じです

def solve():
    s = sorted([c for c in input()])
    c = 'ahooy'
    
    if ''.join(s) == c:
        ans = 'YES'
    else:
        ans = 'NO'
 
    print(ans)

if __name__ == '__main__':
    solve()

input()を一旦リストにしてそっからソートしてます……
けど今試したら普通にsorted(input())でソートされたリストが返ってきました
比較するところもいちいちjoinしてやってるのでなんだかなあ、という感じです
そもそも頭のなかで「yahooって並び替えるとahooyだな」とかやってたのもヒューマンエラーの元であんまりよくないです
というわけでもうちょっとマシ？なコード

def solve():
    s = sorted(input())
    sy = sorted('yahoo')

    ans = 'YES' if s == sy else 'NO'

    print(ans)

if __name__ == '__main__':
    solve()

他のやり方としては、出てきたアルファベットをカウントして個数を見る方法ですね
ちょっとめんどくさくなりますがソートしなくていいのでO(|S|)になりますね

def solve():
    s = input()
    a = [0] * 26

    for c in s:
        a[ord(c) - ord('a')] += 1

    for c in 'yahoo':
        a[ord(c) - ord('a')] -= 1

    ans = 'YES' if a == [0] * 26 else 'NO'

    print(ans)

if __name__ == '__main__':
    solve()

B - オークション

この問題は入力をソートして一番安いのからK個買っていくのが一番安く済みますね
どれを買っても他の商品が全て１円だけ値上がりするので、何をどの順番でK個買っても値上がりで余分に払う分は K * (K - 1) // 2 円です
初日に値上がりは発生しないので K * (K + 1) // 2 ではなく K * (K - 1) // 2 であることがちょっと気を付けるべきことですかね

実際に書いたコード、計算量はO(NlogN)ですね

def solve():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort()
 
    ans = sum(A[:K]) + (K - 1) * K // 2
 
    print(ans)
 
if __name__ == '__main__':
    solve()

C - 検索

まずAに属する文字列全てが先頭から数えて最大何文字目まで一致するかを見ます。これは高々O(sum|S_i|)で出来ます。
次にその先頭から最大～文字目まで一致した文字列でAに属しないワードに検索をかけてみて、そこでもしAに属しないワードがひっかかったら、Aに属するワードのみを検索することは不可能なので-1を出力します。これも高々O(sum|S_i|)で出来ます。
最後に二分探索でその先頭から最大～文字目をどこまで削れるかを調べます。これにはO(sum|S_i| * logmax|S_i|)程度かかります。
全体のアルゴリズムの計算量はO(sum|S_i| * logmax|S_i|)となるので、間に合いそうです。というわけでこれを実装しました。
何か実装が下手なのかかなり長くなってしまいました。競プロでコメントつけながら実装したのはマラソンを除くと初めてかもしれません……

ちなみにこの「Aに属する文字列全てが先頭から～文字目まで一致する文字列」を共通接頭辞という便利な言葉で表現できることを知りました。
英語でいうとcommon prefixですか。なるほどなるほど。というか接頭辞って言う言葉もあんまり使わないので知らなかったですが、競プロではたまにでてくるんでしょうかね。
pythonにはこのcommon prefixの最長のもの、Longest Common Prefixを作って返してくれる便利な関数があるそうです。twitterでフォローしている人が呟いているのを見て初めて知りました。
これを使えばちょっとは短くなりましたかね……、それでも長いんですが

11.2. os.path — 共通のパス名操作 — Python 3.6.0 ドキュメント

def solve():
    N, K = map(int, sys.stdin.readline().split())
    A = [int(i) - 1 for i in sys.stdin.readline().split()]
    S = [sys.stdin.readline().rstrip() for i in range(N)]
 
    if len(A) == N:
        print()
        return
 
    Ain = [False] * N
    for a in A:
        Ain[a] = True
 
    # A に属さないものたち
    B = [i for i in range(N) if not Ain[i]]
 
    # Aに属する長さ最小の文字列を求める
 
    sm = ''
    lenm = 10**5 + 1
    for i, a in enumerate(A):
        if i == 0:
            sm = S[a]
            lenm = len(S[a])
        else:
            if len(S[a]) < lenm:
                sm = S[a]
                lenm = len(sm)
 
    # debug(sm, locals())
    # debug(lenm, locals())
 
    # 何文字目まで一致するかを見る
 
    itti = 0
    for i in range(1, lenm):
        flag = False
 
        for a in A:
            if S[a][i] != sm[i]:
                flag = True
                break
 
        if flag:
            break
 
        itti = i + 1
 
    # debug(itti, locals())
 
    smm = sm[:itti]
 
    # 最大一致で指定しても他がひっかかるならダメ
 
    for i in range(N):
        if Ain[i]:
            continue
 
        if S[i][:itti] == smm:
            print(-1)
            return
 
    # 最小を求めるため二分探索する
 
    top = lenm
    btm = 0
 
    while top - btm > 1:
        mid = (top + btm) // 2
 
        if findsm(S, B, sm, mid):
            btm = mid
        else:
            top = mid
 
    ans = sm[:top]
    print(ans)
 
def findsm(S, B, sm, mid):
    smm = sm[:mid]
 
    for b in B:
        if S[b][:mid] == smm:
            return True
 
    return False
 
if __name__ == '__main__':
    solve()

そもそもこの問題は二分探索とか使わなくても以下のようなシンプルなアルゴリズムでO(sum|S_i|)で解けるみたいです
Aに属する文字列を1つ選んで、まずAの全ての文字列と比較していき、最小で何文字目まで一致してるか(m)、を更新していく
次にAに属さない全ての文字列と比較していき、最大で何文字目まで一致しているか(M)を更新していく。
もし、M < m なら最初に選んだ文字列のM + 1文字目まで切り出せばよく、M >= mなら不可能、という感じですね。
こんなに簡単にできるとは……でも言われてみると確かに、という感じです。

def solve():
    N, K = map(int, sys.stdin.readline().split())
    A = [int(i) - 1 for i in sys.stdin.readline().split()]
    S = [sys.stdin.readline().rstrip() for i in range(N)]
 
    if K == N:
        print()
        return
 
    Ain = [False] * N
    for a in A:
        Ain[a] = True
 
    sr = S[A[0]]
 
    M = 0
    m = 10**5 + 1
 
    for i in range(N):
        tmp = 0
 
        for j in range(min(len(sr), len(S[i]))):
            if sr[j] != S[i][j]:
                break
 
            tmp = j + 1
 
        if Ain[i]:
            m = min(m, tmp)
        else:
            M = max(M, tmp)
 
    if M < m:
        ans = sr[:M + 1]
        print(ans)
    else:
        print(-1)
 
if __name__ == '__main__':
    solve()

D - 工場

これは何とか部分点だけでも、と思って考えてたのですが結局上手くやる方法が分かりませんでした。
解説を読むとセグメント木と座標圧縮を使うといけるそうです。セグメント木は全然勉強してないので解説を読んでも理解できませんでした。
今まで解説でセグメント木とかBITとか出てくると「難しそうだし、これはまだ覚えなくていいかな……」とか思って避けてたのですが、そろそろ勉強したほうがいいのかもしれません。
初等的な武器で戦うのも楽しいですが、もう一つ上のステップに行こうと思ったらやっぱり高等的な武器も必要ですよね。