[AtCoder Daily Training ALL 2024/06/04 17:30start] 参加記録

AtCoder Daily Training ALL 2024/06/04 17:30start に参加しました。
A ~ G の7完でした。
H 問題に24分残しておけましたが、方向性は合っていたものの、違うところを同じ方向に進んでいたため、解けませんでした。
H 問題についてはこの記事にはありません。

残り時間的に、「自分も成長したなあ」と思いましたが、難易度が低いだけだったので精進します。

A - A Recursive Function

もしくは こちら

考え方

再帰的に定義された階上関数です。
定義通りに実装します。

実装例(Python)

def solve(n: int):
    if n == 0:
        return 1
    return n * solve(n - 1)


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

感想

やるだけ。

B - Wrong Answer

もしくは こちら

考え方

答えの範囲が $0 \le ans \le 9$ なので、それぞれに対して $A + B$ と等しいかを調べます。
等しくなければ、それが答えです。
答えが複数ありますが、最初に見つかったもので十分です。

実装例(Python)

def solve(a: int, b: int) -> int:
    for i in range(10):
        if i != a + b:
            return i
    raise ValueError("No solution found")


if __name__ == "__main__":
    A, B = map(int, input().split())
    result = solve(A, B)
    print(result)

感想

ユーザースクリプトの AtCoder Easy Test v2 が使えないため、提出時少し不安でした。
答えが複数あるタイプは、この心理的なプレッシャーが苦手です。

C - 3-smooth Numbers

もしくは こちら

考え方

一見制約が大きいように見えますが、 $2^{60}=1.152921504606846976 * 10^{18}$ なので、 $2$ と $3$ で $N$ が割り切れなくなるまで割っていっても計算量は問題ありません。
よって、 $2$ で割り切れるところまで割って、 $3$ で割り切れるところまで割っていった結果が $1$ になるかどうかを判定します。

実装例(Python)

def solve(n: int) -> bool:
    while n % 2 == 0:
        n //= 2
    while n % 3 == 0:
        n //= 3
    return n == 1


if __name__ == "__main__":
    N: int = int(input())
    result: bool = solve(N)
    print("Yes" if result else "No")

感想

計算量を確かめたら、あとはやるだけ。
指数系はすぐに値が大きくなるので、実は計算量が小さいパターンが多い気がします。

D - At Most 3 (Judge ver.)

もしくは こちら

考え方

$N \le 300$ と小さいので、全探索できそうです。
Python の itertool.combinations を使って、 $3$ つ選ぶ組み合わせを全探索します。
ただし、問題文が 3個以下 なので、 $1$ 個、 $2$ 個、 $3$ 個の組み合わせも考える必要があります。
そのため、今回は重さ $0$ のものを $2$ つ追加して、 $3$ 個選ぶ組み合わせを全探索します。

答えるのは、 $3$ つの組み合わせのうち、重さが $W$ 以下のものの数です。
そのため、選んだ重りの重さの和が $W$ 以下なら set に格納して、最後にその set の長さを出力します。

実装例(Python)

from itertools import combinations


def solve(n: int, w: int, a: list[int]) -> int:
    a.append(0)
    a.append(0)
    sum_set: set[int] = set()
    for s, t, u in combinations(a, 3):
        # print(s, t, u)
        if s + t + u <= w:
            sum_set.add(s + t + u)
    return len(sum_set)


if __name__ == "__main__":
    N, W = map(int, input().split())
    A = list(map(int, input().split()))
    result = solve(N, W, A)
    print(result)

感想

全探索できる問題は、全探索で解くのが一番楽です。
$3$ 個選ぶ組み合わせを全探索するために、 $2$ 個の重りを追加するという工夫を思いついたのは天才だと思いました。

E - Peak

もしくは こちら

考え方

とりあえず、プレゼントが何個目かはどうでもいいので、昇順でソートします。
また、$A_i \le x \lt A_{i+1}$ で条件を満たすプレゼントの数は変わらないので、リストを先頭から順に見ていけば答えを出せそうです。
制約が $N \le 3 \times 10^5$ なので、一つのプレゼントについて $O(logN)$ くらいで答えを出したいです。
そのため、今見ているプレゼントの前からの数と、 $x+M$ が入るべき場所の差がもらえるプレゼントの数となります。
二分探索(同じ値がある場合はもらえないので、左側を返す) で $x+M$ が入るべき場所を探し、その差の最大値を求めれば答えです。

実装例(Python)

from bisect import bisect_left


def solve(n: int, m: int, a: list[int]) -> int:
    a.sort()
    ans: int = 0
    for i, a_i in enumerate(a):
        index = bisect_left(a, a_i + m, i + 1)
        ans = max(ans, index - i)
    return ans


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    result = solve(N, M, A)
    print(result)

感想

計算量から方法を推測するというのが身についてきた気がします。
二分探索で左か右かというのもすぐに判断できたのはいいと思います。
やけに簡単だなと思ったら案の定 diff 299 でした。

F - Counting 2

もしくは こちら

考え方

まず、昇順にソートすることで、インデックスがそのまま背の低い順になります。
あとは各 $x_j$ について $O(logN)$ 程度で、その $x_j$ が入るべき場所を求めればいいので、二分探索を使います。
左を返す二分探索であれば、身長が $x_j$ 未満の人数がわかるので、全体 $N$ から引けば答えです。

降順で右を返す二分探索をすれば一発でもとまるので、そちらの方が楽です。

実装例(Python)

from bisect import bisect_left


def solve(n: int, q: int, a: list[int], x: list[int]) -> list[int]:
    a.sort()
    ans: list[int] = []
    for x_i in x:
        index = bisect_left(a, x_i)
        ans.append(n - index)
    return ans


if __name__ == "__main__":
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    X = [int(input()) for _ in range(Q)]
    result = solve(N, Q, A, X)
    print("\n".join(map(str, result)))

感想

2回連続二分探索？と思いました。
気分は3回連続アが解答欄に並んだ感じです。
しかし、二分探索で十分解けるなと思ったので、やってみたら案の定できました。
こちらも簡単だなと思ったら diff 194 とだいぶ低めでした。

降順にソートすればいいと気がついたのは、この記事を書いている今です。
文字量的にはこっちの方が少ないですが、ほぼ誤差ですね。

G - Loong and Takahashi

もしくは こちら

考え方

問題文の意味が分かりづらいのでサンプルケースからヒントを得ます。
すると、 "T" を中心にして、外側から数字を並べれば求めるべき解が得られることが分かります。
よって、とりあえず中心に "T" を置いて、左上から中心に向かって数字を並べていきます。

なお、実装例は変数名に釣られて、 Direction のメンバが明らかにおかしいですが、結局は題意を満たすので問題ありません。

実装例(Python)

from enum import Enum
from typing import Literal, Self


class Direction(Enum):
    UP = (0, -1)
    DOWN = (0, 1)
    RIGHT = (1, 0)
    LEFT = (-1, 0)

    def next(self) -> Self:
        match self:
            case Direction.UP:
                return Direction.RIGHT
            case Direction.RIGHT:
                return Direction.DOWN
            case Direction.DOWN:
                return Direction.LEFT
            case Direction.LEFT:
                return Direction.UP

    def move(self, x: int, y: int) -> tuple[int, int]:
        dx, dy = self.value
        return x + dx, y + dy


def solve(n: int) -> list[list[Literal["T"] | int]]:
    ans: list[list[Literal["T"] | int]] = [[""] * n for _ in range(n)]

    ans[n // 2][n // 2] = "T"
    x: int = 0
    y: int = 0
    direction: Direction = Direction.RIGHT
    for i in range(1, n**2):
        ans[x][y] = i
        next_x, next_y = direction.move(x, y)
        if (
            next_x < 0
            or next_x >= n
            or next_y < 0
            or next_y >= n
            or ans[next_x][next_y] != ""
        ):
            direction = direction.next()
            next_x, next_y = direction.move(x, y)
        x, y = next_x, next_y
    return ans


if __name__ == "__main__":
    N: int = int(input())
    result: list[int] = solve(N)
    for res in result:
        print(*res)

感想

サンプルケースにヒントがあることはよくあります。
問題文の理解に戸惑ったら、サンプルケースが詳しいパターンが多いので、よく見ることをおすすめします。

Direction のメンバがおかしいのは x と y が高さと幅を表しているためです。
そのため、 UP で y を減らして上に移動するつもりが、実際には左に移動してしまっています。
以降もメンテナンスするコードなら絶対直しますが、この問題は一発で通ったのでそのままにしました。
一回でも WA が出たら直そうとは思ってました。