Codeforces Round #402 (Div. 2) - D言語で競プロ

参加しました、３完でした
配点が 500 — 1000 — 1000 — 1500 — 2000 — 2500
だったので３完でもあまり良くないというか妥当な感じの成績ですね
今回は全体的に１問解くのに時間がかかりすぎたかなと思ってます

A.o
B.o
C.xo

http://codeforces.com/contest/779
公式解説
http://codeforces.com/blog/entry/50724

A. Pupils Redistribution

１問目から少し悩んでしまった問題でした。
まずグループAとBの各成績の人数を等しくするためには、成績の人数に差があるところの生徒同士を入れ替えますよね。（成績が同じ生徒同士を交換しても意味が無いので）
これをすると多い方からその成績の人数が-1され、片方の成績の人数が+1されるので、両者の差は2縮まることになります。
なのでまず各成績の人数差を調べて、それが偶数になってないとダメだということが分かりました。
それでお互いのグループの全体人数は等しいので、ある成績で人数差がついてたら別の成績でその人数分の差をつけかえしてないと、つじつまが合わないはずです。
なので各成績の人数差（絶対値）が偶数だとすると、それを１～５の総和を取ると、これは４の倍数になってるはずです。

このとき一番操作回数を少なくするには、ある成績で差があるところの生徒を１人取って、別の成績で差があるところの生徒を１人取って、交換するという操作を繰り返していくのがいいはずで
このとき成績の人数差の総和は４ずつ減っていくことになります。

よって答えは、各成績の人数差の総和を４で割った値、となる……と思いました。
全体的に「～はず」が多いのはあんまり自信が無かったからです。私にとってこの問題はそんなに自明に解ける問題ではありませんでした

def solve():
    n = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    cntA = [0] * 5
    cntB = [0] * 5

    for a in A:
        cntA[a-1] += 1

    for b in B:
        cntB[b-1] += 1

    ans = 0
    for k in range(5):
        if abs(cntA[k] - cntB[k]) % 2:
            print(-1)
            return None
        else:
            ans += abs(cntA[k] - cntB[k])

    ans //= 4
    print(ans)


if __name__ == '__main__':
    solve()

B. Weird Rounding

Problem - B - Codeforces

これは実際にこの操作を所望のものになるまで繰り返していけばいいのではないかと思いました。
実際桁数は高々10桁だし愚直にやっても余裕で間に合いますね。
ただ実装が面倒で、てこずってしまいました

実際に書いたコードもちょっとややこしいです
whileループのとことか何かいろいろごまかしながら書いてますし……
というか今見たら何やってるかぱっと見意味が分かりませんでした
下k桁を見て、0じゃなかったら-1に置き換えておいて、最後にd >= 0でふるいをかけることによってそこを消すということをやってますね
いちいちリストを作り直すことになるのでかなり非効率的ですが高々１０ケタなので何とかなってます

def solve():
    n, k = input().split()
    n = [int(i) for i in n]
    k = int(k)
    cnt = 0

    while n[-k:].count(0) < len(n[-k:]):
        for i in range(max(0, len(n)-k),len(n)):
            if n[i] != 0:
                n[i] = -1
                cnt += 1

        n = [d for d in n if d >= 0]

    if n and n.count(0) == len(n):
        cnt += len(n) - 1

    print(cnt)
    
if __name__ == '__main__':
    solve()

でもこの問題解説にあるように、こんなめんどくさいことせずにnの下の桁から順に見て行って、0じゃなければ答えに+1カウントしていって、0をk個読み込んだ時点でその答えを出力して終了。
もし全て読み終わっても0をk個読み込めなければ0を一個だけ残して他の桁を消すことで10^kの倍数にできますからそれが答え。
ということで以下のようにシンプルに書くことができたようです。

def solve():
    n, k = input().split()
    k = int(k)
    zcnt = 0
    ans = 0

    for d in reversed(n):
        if d == '0':
            zcnt += 1

            if zcnt == k:
                print(ans)
                return
        else:
            ans += 1

    ans = len(n) - 1
    print(ans)

if __name__ == '__main__':
    solve()

競プロで「～～という操作をするとき、目的のものにするためにかかる最小の手数を求めよ」という形式の問題はよく出る気がします
そういうときって、たいていその操作を愚直にやるのは悪手っぽいんですよね（たいていは計算量的に無理とかになる）
今回は計算量的に余裕だったので愚直にやってしまいましたが、その操作を実際にすることなく求める方法を最初に考えるべきだったと思いました

C. Dishonest Sellers

Problem - C - Codeforces

わざわざ"at least"と太字で強調して書いてくれているにも関わらず、k個ちょうどじゃないとダメだと思っててサンプル間違ってない？　ってずっと思ってました。アホですね。
ともかく、まずn個全部を１週間後に買ったとすると、このときの答えは簡単にsum(B)で求められます。
でも条件により、少なくともk個以上はAのほうから買わなきゃいけません。代わりにk個買ったときの値段を出来るだけ少なくしたいのでa_i - b_iの差を取っておいて、その差を昇順にソートして
まずk個は先頭k個を取るようにします。
全部＋だったらこれ以上買うと高くつくだけなのでそこで終わればいいんですが、ーになってる場合もあるので、そのときはーになるところを出来るだけ多く取ったほうが安上がりになります。
っていう感じで見て行って、＋になったらもういいやってやってそこまでをAで買って後はBで買う、とすればいい感じです。

っていうのが今改めて整理して考えた答えです。

def solve():
    n, k = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]

    dif = [a - b for a, b in zip(A, B)]
    dif.sort()
    dc = sum(dif[:k])

    for i in range(k, n):
        if dif[i] < 0:
            dc += dif[i]
        else:
            break

    ans = sum(B) + dc

    print(ans)

if __name__ == '__main__':
    solve()

実際に本番中に書いた答えは下の方で、こっちは累積和を使って求めてますね。
計算量的にはどっちも変わらないんですが演算回数は上の方が少ないし、スマートなやり方じゃないかなと思います。

from itertools import accumulate

def solve():
    n, k = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    sumB = sum(B)
    dif = [a - b for a, b in zip(A, B)]
    dif.sort()
    dif = [0] + list(accumulate(dif))

    ans = float('inf')

    for i in range(k, n + 1):
        ans = min(ans, sumB + dif[i])

    print(ans)
    
if __name__ == '__main__':
    solve()

D. String Game

Problem - D - Codeforces

Twitterとか見ると、「ワードtからワードpを得るためには、tの中にpが連続した文字列として含まれてなければならない」と解釈した人が何人かいて、私もその１人でした……
確かに文中に"consecutive"とか"continuous"とか書いてないと言えば書いてないから、勘違いしたほうが悪いと言えばそうかもしれないですが、でもワードtからワードpが得られるとはどういう状態を意味するのか？
をもっと明確に定義しておいてくれればいいのに、と思いました。なので私は問題文が悪いのではないかと思っています。

それは置いといて、順番に文字を取っていくといつかワードtの中にワードpが部分文字列として含まれない状態になってしまい、それ以降はずっと取れない状態になってしまいます。
逆にそこまではいくら文字を取ってもずっとワードtの中にワードpは部分文字列として含まれているはずです。
このことから「いくつかの文字をワードtから取り除いた文字列からワードpが取れるか？」の真偽をT, Fで表すと

T, T, T, T, ..., T, T | F, F, ..., F, F

となっていることが想像できます。どっかに境界があって、こっから左は全部真、こっから右は全部偽という状況です。
こういう境界を効率よく求める方法というと、二分探索ですね。二分探索はO(N)をO(logN)にしてくれる優秀なアルゴリズムで、かつ記述も簡単なので、私の好きなアルゴリズムです。
結局この問題は二分探索しながら文字を実際に消してみて、その文字列にpが部分文字列として存在するかを愚直に確かめればいいのでO(|t|log|t|)で実行可能です。

コードはこんな感じですかね
部分文字列判定はもっとスマートに書けそうな気がします

def solve():
    t = input()
    p = input()
    A = [int(i) - 1 for i in input().split()]

    ans = nibutan(t, p, A)

    print(ans)

def nibutan(t, p, A):
    top = len(A)
    btm = 0

    while top - btm > 1:
        mid = (top + btm) // 2

        if ex_subs(t, p, A, mid):
            btm = mid
        else:
            top = mid

    return btm

def ex_subs(t, p, A, mid):
    tc = list(t)
    p = list(p)

    for i in range(mid):
        tc[A[i]] = '#'

    k = 0
    cnt = 0

    for c in p:
        if k == len(tc):
            return False

        for j in range(k, len(tc)):
            k += 1
            if c == tc[j]:
                cnt += 1
                break
    
    return cnt == len(p)

if __name__ == '__main__':
    solve()

これでもpythonではTLEする(2 * 10^6 を超えるともうやばい）のでpypyに頼りました。
そろそろpythonだけではキツくなって来た感があります……、重い実装用に今はD言語を覚えようとしています。
実行速度はC++並に速いしpython-likeに書けるし標準ライブラリも割と充実してるし、と個人的には好感触です。