Zenn
😎

[AtCoder Daily Training HARD 2024/05/08 18:00start] 参加記録

に公開
Python
AtCoder
tech

AtCoder Daily Training HARD 2024/05/08 18:00start に参加しました。
2冠です。

E - RANDOM

もしくは こちら

考え方

S も T も転置してしまいます。
あとはそれぞれの中身のカウントをとって比較すればいいです。
ソートすればもっと簡単に比較ができますね。

転置を求めるのが一番計算量がかかり、O(HW) ですが、制約より HW\le4\times10^4 なので十分間に合います。

実装例(Python)

from typing import Counter


def solve(h: int, w: int, s: list[str], t: list[str]) -> bool:
    s_t: list[str] = [[] for _ in range(w)]
    t_t: list[str] = [[] for _ in range(w)]
    for i in range(h):
        for j in range(w):
            s_t[j].append(s[i][j])
            t_t[j].append(t[i][j])
    for i in range(w):
        s_t[i] = "".join(s_t[i])
        t_t[i] = "".join(t_t[i])

    def _show(s: list[str]) -> None:
        print("show")
        for s_i in s:
            print(s_i)
        print()

    # _show(s_t)
    # _show(t_t)
    t_t_cnt = Counter(t_t)
    for s_t_i in s_t:
        t_t_cnt[s_t_i] -= 1
    return all(v == 0 for v in t_t_cnt.values())


if __name__ == "__main__":
    H: int
    W: int
    H, W = map(int, input().split())
    S: list[str] = [input() for _ in range(H)]
    T: list[str] = [input() for _ in range(H)]
    result: bool = solve(H, W, S, T)
    print("Yes" if result else "No")

感想

カウントを取らずに、集合を用いて存在の確認をしたため、同じ種類の個数違いの文字列に対応できず、WA。
文字列の加算が遅いことを忘れていて、愚直に実装したため、TLE。
基礎的な部分のミスがありました。
特に文字列の加算は何度もやってるはずなんですけどね。

F - Previous Permutation

もしくは こちら

考え方

K を求めて、K-1 番目の順列を求めました。
P_i の k 番目の要素を見た時、j\lt i となる P_j の k 番目が同じものはそれぞれ残りの桁数の階上個あるはずです。

具体例

(1,2,3)
(1,3,2)
(2,1,3)
(2,3,1)
(3,1,2)
(3,2,1)

例えば、(3,2,1) において 3 をみると、それより前には先頭が 1 であるものと 2 であるものがそれぞれ2通りずつあることがわかります。
次に、2 をみると、それより前には先頭が 1 であるものが1通りあることがわかります。
よってこれらを全て足してあげると5通り辞書人の前にあるとわかり、0-index においてはそのまま5番目です。

これで K を求めることができるので、あとは K-1 番目の順列を求めるだけです。
やっていることは K を求めるのの逆の処理です。
計算量は O(N^2) ですが、N\le100 なので十分間に合います。

実装例(Python)

from functools import lru_cache


@lru_cache(maxsize=None)
def fractional(n: int) -> int:
    if n == 0:
        return 1
    return n * fractional(n - 1)


def get_index(p: list[int]) -> int:
    index: int = 0
    n: int = len(p)
    used: list[bool] = [False] * n
    for i in range(n):
        for j in range(p[i] - 1):
            if used[j]:
                continue
            index += fractional(n - i - 1)
        used[p[i] - 1] = True
    return index


def from_index(index: int, n: int) -> list[int]:
    p: list[int] = [0] * n
    used: list[bool] = [False] * n
    for i in range(n):
        for j in range(n):
            if used[j]:
                continue
            tmp = fractional(n - i - 1)
            if index < tmp:
                p[i] = j + 1
                used[j] = True
                break
            index -= tmp
    return p


def solve(n: int, p: list[int]) -> list[int]:

    index: int = get_index(p)
    # print(index)
    rtn: list[int] = from_index(index - 1, n)
    return rtn


if __name__ == "__main__":
    N: int = int(input())
    P: list[int] = list(map(int, input().split()))
    result: list[int] = solve(N, P)
    print(*result)

感想

fractional の計算に時間がかかるのはわかっていたので、メモ化しました。
正直普通に、階上のリストを作っておいた方がわかりやすかったかもしれません。

G 問題

(検索除けのために題名は入れません)

感想

解けませんでした。
解説を元に実装しましたが、サンプルケースさえ通りません。
なんで？

def solve(s: str, n: int) -> int:
    n_2: str = f"{n:0{len(s)}b}"

    i_star: int = -1
    for i, (s_i, n_i) in enumerate(zip(s, n_2)):
        if s_i in "?0" and n_i != "1":
            i_star = i

    # print(f"i*: {i_star}")

    if i_star == -1:
        return -1

    ans: list[str] = []
    for j, (s_j, n_j) in enumerate(zip(s, n_2)):
        if s_j == "?":
            if j < i_star:
                ans.append("1")
            elif j == i_star:
                ans.append("0")
            else:
                ans.append(n_j)
        else:
            ans.append(s_j)

    # print(ans)
    return int("".join(ans), 2)


if __name__ == "__main__":
    S: str = input()
    N: int = input()
    result: int = solve(S, int(N))
    print(result)

Discussion