はじめにスコア

２週間ぶりのコンテスト。 A~D までの 4完で、E も大きなずれない方針をたてれて、自分の成長を感じられて嬉しかった。

[f:id:yasuharu519:20240414183638p:plain]

A - Zero Sum Game

まず問題を最初読んだときなんだか難しく感じて、何度も問題を読み返した。要は 1 ~ N 人で ゼロサムゲームをするのだけれど、最終的な 1 ~ N-1 番目の人の得点がわかったときに N 番目の人の得点を答えよというもの。

全員でゼロサムゲームを行っており、全員の得点を合わせると 0 になるはずなので、 1 ~ N-1 番目の人の得点を合わせて 0 から差し引けば回答となる。

#!/usr/bin/env python3
import sys

def solve(N: int, K: int, A: "List[int]"):
    result = [x // K for x in A if x % K == 0]
    print(" ".join(map(str, sorted(result))))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

B - Commencement

良い文字列 とは、すべての文字種の出現回数をとったあと、出現回数ごとに見たときに、0 または 2種類の文字があるものとする。そうしたときに与えられ他文字列が いい文字列 か判定せよというもの。

Python だと Counter があるのでまずそれを使用して、文字のカウントを取る。その後、出現回数ごとに改めて文字種のカウントを行うようにした。解説だと改めて Counter を取る方法も紹介されていて、そちらのほうが簡単にできそう。

#!/usr/bin/env python3
import sys
from collections import Counter, defaultdict

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S: str):
    counter = Counter(S)
    d = defaultdict(int)
    for k, v in counter.items():
        d[v] += 1
    if all([x == 2 for x in d.values()]):
        print(YES)
    else:
        print(NO)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

C - Airport Code

文字列 S, T が与えられる。 T は文字列をあるルールで変換したコードとする。 T が S から得られるコードであるかを判断せよというもの

i, j をそれぞれ S, T の index として、前から条件に合えば index を進めるものとする。どちらかの index が最後まで到達したときに、

• j が最後まで到達しているか
• j が 2まで来ており、T の最後の文字が X であるか

をチェックして回答するようにした

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S: str, T: str):
    i, j = 0, 0
    while i < len(S) and j < len(T):
        if ord(S[i]) - ord('a') == ord(T[j]) - ord('A'):
            j += 1
        i += 1

    if j == 3:
        print(YES)
    elif j == 2 and T[2] == "X":
        print(YES)
    else:
        print(NO)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(S, T)

if __name__ == '__main__':
    main()

D - Divide Interval

S(l,r) を [l, r) で表される数列とする。 また、 $S(2^{i}j,2^{i}(j+1))$ で表される数列をいい数列とする。$S(L, R)$ をできるだけ少ない M 個のいい数列に分けるときの分け方を示せというもの。

最初に考えたのは “L と R の差を2進数で表して、ビットの立っている部分を区間にすれば最小になりそうだな” というもの。幅だけ見ればそうなのかもしれないが、L, R の差が 16 だからといって、常に $(2^{4}\times j,2^{4} \times (j+1))$ で表せるとは限らない。 $j$ は非負整数となっているため、0, 16, 32.. と 決まった区間しか表せないのである。

つまり $L$ が取れる最大の幅は、 $L$ の値、特に2 の約数をいくつ持つかによって決まる。そのため、貪欲法で取れるだけ取り、取った幅で $R$ を超える場合は幅を小さくすれば回答となる。

上記の方法だと、$L$ が 0の場合だけ注意する必要があるのだが、その時の処理をミスしてしまい WA となってしまった。 $L$ が 0 の場合は $R$ を超えない範囲でできるだけ取って、その後は同様の処理をすれば問題ない。

最初なぜこれでうまく解けるのか、取れる幅が広がっていくのかよくわかってなかった。 $(2^{i}j, 2^{i}(j+1))$ という式をよく見ると $j, j+1$ のどちらかは必ず偶数となる。$L=2^{i}j$ としたときに、できるだけ大きい幅を取ろうとすると $j$ は必ず奇数となるため、$j+1$ は偶数となり、次の区間は $2^{i+1}$ の幅を取れるようになる。と、考えると少し理解できた。

解説を見ると結果的にセグメントツリーのような形となり、再帰的に構築する方法だとセグメントツリー構築の方法とほぼ同様になるとのことだったのでそちらも試してみたい。

#!/usr/bin/env python3
import sys
import math

def power2_count(num: int) -> int:
    count = 0
    while num and num % 2 == 0:
        count += 1
        num //= 2
    return count

def solve(L: int, R: int):
    result = []
    current = L

    if current == 0:
        add = 1
        while add <= R:
            add *= 2
        add //= 2
        result.append((current, current+add))
        current += add

    while current < R:
        max_power = power2_count(current)
        add = pow(2, max_power)
        while current + add > R:
            add = add // 2
        result.append((current, current+add))
        current += add

    print(len(result))
    for l, r in result:
        print("{} {}".format(l, r))
    return

def main():
    L, R = list(map(int, input().strip().split()))
    solve(L, R)

if __name__ == '__main__':
    main()

E - Weighted Tic-Tac-Toe

TicTacToe だし、そのままシンプルに mini-max でトライしたものの、時間が間に合わずタイムアップに。minmax ってこれでよかったっけ? と悩みながら書いて時間がかかったので改めてさっと書けるようにしないといけない。

#!/usr/bin/env python3
from typing import List

MAX_VALUE = pow(10, 10) + 1
MIN_VALUE = -1 * pow(10, 10) - 1

def main():
    A = []
    for _ in range(3):
        A.append(list(map(int, input().strip().split())))

    board = [[0] * 3 for _ in range(3)]

    def minmax(cur: List[List[int]], score: int, takahashi: bool) -> int:
        r = wincheck(cur)
        if r != 0:
            return score + (MAX_VALUE if r == 1 else MIN_VALUE)
        if all([all([x != 0 for x in l]) for l in cur]):
            return score

        if takahashi:
            res = MIN_VALUE
            for i in range(3):
                for j in range(3):
                    if cur[i][j] == 0:
                        cur[i][j] = 1
                        res = max(res, minmax(cur, score + A[i][j], not takahashi))
                        cur[i][j] = 0
            return res
        else:
            res = MAX_VALUE
            for i in range(3):
                for j in range(3):
                    if cur[i][j] == 0:
                        cur[i][j] = -1
                        res = min(res, minmax(cur, score - A[i][j], not takahashi))
                        cur[i][j] = 0
            return res

    def wincheck(t: List[List[int]]) -> int:
        for l in t:
            if sum(l) == 3:
                return 1
            elif sum(l) == -3:
                return -1
        for j in range(3):
            total = sum(t[i][j] for i in range(3))
            if total == 3:
                return 1
            elif total == -3:
                return -1

        diag1 = t[0][0] + t[1][1] + t[2][2]
        diag2 = t[2][0] + t[1][1] + t[0][2]
        if diag1 == 3 or diag2 == 3:
            return 1
        elif diag1 == -3 or diag2 == -3:
            return -1
        return 0

    res = minmax(board, 0, True)
    if res > 0:
        print("Takahashi")
    else:
        print("Aoki")
    return


if __name__ == '__main__':
    main()

まとめと最近の練習について

最近は Obsidian を使って、各問題の整理と、問題を解くときに使う基礎的なアルゴリズムをまとめている。 gcd lcm とかも、もちろんライブラリを使えばぱっと出せるのだけど、背景にある計算方法を知っているだけでもだいぶ理解の助けになっている気がする。

あとはアルゴリズムを書いてなるべく言葉で説明できるように心がけるようにしている。自分がどこをちゃんと理解できてないかわかりやすくなった気がしていて、どこの勉強をすればいいか理解するための助けになっている気がしている。