Zenn
🧭

ただの茶コーダーが競技中に考えていたことと振り返り【AtCoder Beginner Contest 361】

2024/07/07に公開
AtCoder
tech

こんにちは。ダイの大冒険ガチ勢のbun913と申します。

皆さんはAtCoderという競技プログラミングに気軽に参加できるサービスをご存知でしょうか？

https://atcoder.jp/

競プロと聞くと一見とっつきにくいですが、普段なかなかプログラミングができないなかでも「あ〜俺今生きてる。プログラミングしてる。二部探索している。」という気持ちになれるので、とてもおすすめです。

まったく参加したことのない方でも、以下のような記事を見るだけで簡単な問題を解けるようになりますので、興味があればぜひ見てください。

https://qiita.com/drken/items/fd4e5e3630d0f5859067

この記事は以下のような1社会人のエンジニアとして、限られたリソースの中でも復習をしつつも、同じレベル帯の方になんらか参考になることがあるかもしれないというモチベーションで書いています。

A - Insert

考えたこと

  • A問題らしく、特に時間計算量も空間計算量もあまり気にしないでも良さそう
  • 素直に配列に要素を挿入すれば良さそう
  • Pythonだと insert というメソッドがあるのでそれを使えば終わりだな

ということで、以下のようなコードを提出しました。

# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""

from sys import setrecursionlimit

setrecursionlimit(10**8)


def solve():
    act()


def act():
    N, K, X = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.insert(K, X)
    print(*A)


solve()

ちなみに、問題文の K 要素目の直後に という記述を見逃していて、 A.insert(K-1, X) としてしまったのは私だけではないのではないでしょうか？

エンジニアは 2番目の要素 と書かれると自然と 配列の添字は1か と脳内変換される仕組みがありますよね。

C - Make Them Narrow

B問題を見て考えてみたのですが、「あっ。これは俺には解けない。 数学どころか算数がわからない。 俺は。」と察してしまい、この問題に取りかかりました。

考えたこと（1回目の提出時: 不正解）

  • 求めるべきことは数列AからK個の要素を取り出した数列Bの最大値と最小値の差であること
  • 頭に湧いてきた考察
    • 結局最小値と最大値しか関係ないわけだから、ソートしとけば良さそうだな
    • Bの最小値と最大値の差 を最小化したいわけだから、極端な話同じ数字が最後に残っておけばベストだよね
    • ソートしといて、できるだけ近い要素だけ残ればいいのか・・・
  • でも具体的な方法が思いつかないなぁ
  • せや、どうせ最小値と最大値だけしか取り出す必要はないから deque 使っておいて、その時最適な要素を選び続ければいいんじゃね？

と、考えて提出したコードが以下の通りです。サンプルと数件のテストケースは通るものの、不正解となりました。

# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""

from sys import setrecursionlimit
from collections import deque

setrecursionlimit(10**8)


def solve():
    act()


def act():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    q = deque(A)
    ans = A[-1] - A[0]
    for _ in range(K):
        cur_min = q.popleft()
        cur_max = q.pop()
        if len(q) <= 0:
            break
        next_min = q[0]
        next_max = q[-1]
        cand1 = cur_max - next_min
        cand2 = next_max - cur_min
        if cand1 < cand2:
            q.appendleft(cur_min)
            ans = min(cand1, ans)
        else:
            q.append(cur_max)
            ans = min(cand2, ans)

    print(ans)


solve()

考えたこと（2回目の提出時: 正解）

  • いや、確かにこの場当たり的な方法では適切に最適解を選び出すことができないよな
  • 頭に湧いてきた考察
    • ていうかC問題だから、「効率よく全探索できるか」っていう思考でいけるんじゃない？（メタぁ！）
    • いや、まてよ。結局「最小値と最大値の差」を取るわけだから、その時選んだ最小値からみて連続した値を見るのが最適だよね
    • 要するに最小値だけ決めれば、自分から近い数を残すようにすればいいわけだ！
    • 最小値の要素だけ全探索して、そこからK個残るような連続した要素を選べばいいんじゃない！？

と、メタ的な視点に立ち返って考え直した結果、以下のコードを提出しました。

# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""

from sys import setrecursionlimit

setrecursionlimit(10**8)


def solve():
    act()


def act():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    ans = float("inf")

    # 最小値だけ全探索
    for i in range(N):
        # 最小値から連続した範囲（K個分）をみていく
        right = N - K - 1
        if i + right >= N:
            break
        # あらかじめソートしているので、min,maxは単に左端・右端から取るだけ O(1)
        cur_min = A[i]
        cur_max = A[i + right]
        ans = min(ans, cur_max - cur_min)
    print(ans)


solve()

この提出により、無事正解することができました。

B - Intersection of Cuboids

考えたこと

実は最初見た時は解ける気がしなかったのですが、C問題を解いている最中に「3次元で考えると意味わからんけど、2次元の矩形の重なり」であれば重なっているか判定ってできるんじゃない？と思いついていました。

ということで提出したコードが以下のようなものです。

# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""

from sys import setrecursionlimit

setrecursionlimit(10**8)


def solve():
    act()


def act():
    a, b, c, d, e, f = map(int, input().split())
    g, h, i, j, k, l = map(int, input().split())
    # x軸方向の重なり判定
    x_overlap = max(a, g) < min(d, j)
    # y軸方向の重なり判定
    y_overlap = max(b, h) < min(e, k)
    # z軸方向の重なり判定
    z_overlap = max(c, i) < min(f, l)

    if x_overlap and y_overlap and z_overlap:
        print("Yes")
    else:
        print("No")


solve()

この提出により、無事正解することができました。

正直この問題を提出できたのはまぐれです。もう少しだけコンディションが悪ければ、絶対に解けなかったと思います。

おまけ: D - Go Stone Puzzle

この問題は解決の糸口も見つけられず解けませんでした。

考えたことといえば「黒石と白石の数がSとTで一致しないと絶対無理だな」ということくらいです。

公式の解説動画を見て、「黒石と白石が並んでいる状態を元に幅優先探索する」という解放を知り、以下のように解説ACをしました。

こういう知っているアルゴリムを思いも寄らない使い方をしていると、とってもワクワクしますね。天才かと思いました。

# -*- coding: utf-8 -*-
"""
解く前のメモ用
"""

from sys import setrecursionlimit
from collections import deque

setrecursionlimit(10**8)


def solve():
    act()


def act():
    N = int(input())
    S = input()
    T = input()
    S = list(S) + [".", "."]
    T = list(T) + [".", "."]
    q = deque([tuple(S)])
    # tupleをキーにできることを初めて知った
    dist = {tuple(S): 0}
    T = tuple(T)
    while q:
        cur = q.popleft()
        if cur == T:
            print(dist[cur])
            return
        # .が並んでいる場所のインデックスを取得
        j = list(cur).index(".")
        for i in range(N+1):
            # 交換する場所が.ならスキップ
            if cur[i] == "." or cur[i+1] == ".":
                continue
            # .が並んでいる場所と交換する
            s2 = list(cur)
            s2[i], s2[i+1], s2[j], s2[j+1] = ".", ".", s2[i], s2[i+1]
            # もう作っている状態であるならばスキップ
            s2 = tuple(s2)
            if s2 in dist:
                continue
            dist[s2] = dist[cur] + 1
            q.append(s2)
    if T in dist:
        print(dist[T])
    else:
        print(-1)


solve()

また、地味に tuple は 辞書のキーに使えるということを知りました。学びです。

まとめ

  • ABC361に参加して、コンテスト中に3問解けた
  • 特定の状態から特定の状態に移行できるかというのを、幅優先探索で解くという考え方を知れた
    • グラフ問題だけでしか、そもそもこの考え方が出てきませんでした
    • なーんか再帰で解けるっぽいよなぁ。くらいのノリでした

復習を通しながら、わからなかった問題を1問だけ解説を見て解くことで、新たな知識を得ることができました。

もし、競技プログラミングに興味を持たれたらぜひ以下のような公式の「はじめかた」を見てください。

https://info.atcoder.jp/overview/contest/intro

以上、bun913でした。ありがとうございました。

GitHubで編集を提案

Discussion