AtCoder Regular Contest 069 - D言語で競プロ

参加しました、２完でした。
結果自体は決して悪くないのですが、いろいろミスしたり何なりでいまいちかも。

C.o
D.o

今回もコードとちょっとしたコメントだけ。

C - Scc Puzzle

C: Scc Puzzle - AtCoder Regular Contest 069 | AtCoder

二分探索でやるのが楽そうだと思って二分探索でやりました。
実装は難しくないはずですが、いろいろ書き間違えたりしてもたつきました。
計算量はO(log(M))くらいです。

def solve():
    N, M = map(int, input().split())
 
    if 2*N >= M:
        ans = M // 2
    else:
        top = M // 2
        btm = 0
 
        while top - btm > 1:
            mid = (top + btm)//2
            if check(N + mid, M - 2*mid):
                btm = mid
            else:
                top = mid
 
        ans = N + btm
 
    print(ans)
 
def check(a, b):
    return 2*a <= b
 
if __name__ == '__main__':
    solve()

解説を聞くと今回は二分探索を使わず数学的に解いてました。一応そっちも。
今回の問題こそ、二分探索を使った方が楽だと思うのですがどうなんでしょう。良く分かりません。
数学が得意な人はこっちのほうが楽だと思うのかもしれないですね。

def solve():
    N, M = map(int, input().split())
 
    ans = min(M//2, (2*N + M)//4)
 
    print(ans)
 
if __name__ == '__main__':
    solve()

pdfのほうの解説を見るといずれの方法でもなく、貪欲法でやってますね。ちゃんと考えると確かにそうだなあって感じです。
競プロ始めたての頃の私が解くとしたら、確かにこういう方法で解いてるだろうなあ。
下手に知識をつけてしまったのがかえって悪手になってしまっているのだろうか……
解説にある「４つの'c'を組み合わせて１つの'Scc'を作る」という操作が出来ることに気づかなかったのが敗因ですかね。

D - Menagerie

D: Menagerie - AtCoder Regular Contest 069 | AtCoder

実際に書いたコード

def solve():
    N = int(input())
    S = [True if i == 'o' else False for i in input()]

    for i, j in [(False, False), (False, True), (True, False), (True, True)]:
        pat = [i, j]
        for k in range(2, N):
            if pat[k - 1]:
                if S[k - 1]:
                    pat.append(pat[k - 2])
                else:
                    pat.append(not pat[k - 2])
            else:
                if S[k - 1]:
                    pat.append(not pat[k - 2])
                else:
                    pat.append(pat[k - 2])

        for k in range(N):
            if pat[k]:
                if S[k] != is_same(pat, k, N):
                    break
            else:
                if S[k] == is_same(pat, k, N):
                    break
        else:
            ans = ['S' if pat[k] else 'W' for k in range(N)]
            print(''.join(ans))
            return None

    print(-1)

def is_same(pat, i, N):
    return pat[(i - 1) % N] == pat[(i + 1) % N]

if __name__ == '__main__':
    solve()

「最初の２匹を決めてしまえば、後ろのN - 2匹は自動的に決まってしまう」ということに気づけるかどうかが肝ですね。
それに気づくのにかなりの時間を要しました……
そしてコーディングもスマートではなく、テストケースを入れて弾きだした答えは正しいのになぜか間違っていると勘違いして無いバグを探そうとしていたのが一番の失態です。
この直前にあったこどふぉの出来の悪さを引きづっていたせいもあり、割と精神的に辛かったです。
後、最後に上手く行っているかをチェックするとこ、全部調べなくてもS[0]とS[-1]のとこだけ調べれば十分でした。他のとこは全部それが正しくなるようにpatを作っていっているので。

解説を聞いていると、S[i]は隣接する３つの和 mod 2の答えだと思うと分かりやすいって言ってました。
確かに嘘つきだと答えがひっくり返るってのは、mod 2の世界で+1することと同じですからごちゃごちゃ場合分けせずとももっとスムーズに書けそうです。
ってわけで実際に書いてみたのがこちら。いいですね！

from itertools import product

def solve():
    N = int(input())
    S = [0 if i == 'o' else 1 for i in input()]
    
    for i, j in product(range(2), repeat=2):
        pat = [i, j] + [0]*(N - 2)
        for k in range(2, N):
            pat[k] = (S[k - 1] - (pat[k - 1] + pat[k - 2])) % 2

        if S[-1] != (pat[0] + pat[-1] + pat[-2]) % 2:
            continue
        if S[0] != (pat[1] + pat[0] + pat[-1]) % 2:
            continue

        ans = ['S' if pat[k] == 0 else 'W' for k in range(N)]
        print(''.join(ans))
        return None

    print(-1)

if __name__ == '__main__':
    solve()

Eはそもそも読んですらいないですが、噂によるとそんなに難しくない？とのことなので、余裕があったら取り組んでみたいです。