2025-01-04 ABC007 - hard_sinkerのブログ

はじめに

1月4日っていつも仕事はじめなので、なんか延長戦を満喫している感がすごい。

AtCoder Beginner Contest 007

A - 植木算

# 入力された整数 n から 1 を引いた値を出力する
input_number = int(input())
print(input_number - 1)

1引いた数を出力するだけなので、こんなものでしょうか。

B - 辞書式順序

# 入力を取得
# 入力された文字列が "a" なら -1 を、それ以外なら "a" を出力する
input_string = input()
print("a" if input_string != "a" else -1)

"a"が辞書順最速なので、だいたい"a"を出しておけばOK。
ただし、入力が"a"だとそれより強いものがないので"-1"を出力する必要があります。
そのとおりの実装なので特に言うことはない。

C - 幅優先探索

# 入力を取得
from collections import deque

# 入力の取得
rows, cols = map(int, input().split())
start_y, start_x = map(int, input().split())
goal_y, goal_x = map(int, input().split())
maze = [input() for _ in range(rows)]

# 初期設定
steps = [[-1 for _ in range(cols)] for _ in range(rows)]
steps[start_y - 1][start_x - 1] = 0  # スタート地点の歩数を 0 に設定
queue = deque([(start_y - 1, start_x - 1)])  # BFS キュー

# 移動方向の定義 (上下左右)
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

# 幅優先探索 (BFS)
while queue:
    y, x = queue.popleft()
    # ゴール地点に到達したら終了
    if (y, x) == (goal_y - 1, goal_x - 1):
        break
    # 上下左右への移動を試す
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        # 移動可能かのチェック
        if 0 <= ny < rows and 0 <= nx < cols and steps[ny][nx] == -1 and maze[ny][nx] == ".":
            steps[ny][nx] = steps[y][x] + 1
            queue.append((ny, nx))

# ゴール地点の歩数を出力
print(steps[goal_y - 1][goal_x - 1])

ド定番問題のためか、めちゃくちゃ破壊的にリフォームが行われました。
もとは「deque」など導入せずリストで管理したり、上下左右への移動も4方向に場合分けしたりとかなり原始的なつくりをしていました。
移動方向の定義はお上手ですね。これなら確かにfor文で綺麗に書けるのか。

D - 禁止された数字

def adjust_digit(digit):
    """
    桁の値を調整する:
    - 4 または 9 を含まない場合の有効な桁数に変換。
    """
    if digit <= 3:
        return digit + 1
    elif digit <= 8:
        return digit
    else:
        return digit - 1

def count_valid_numbers(num_str):
    """
    数字の文字列を受け取り、その範囲内で「4」または「9」を含まない
    有効な数字の総数を計算。
    """
    digits = list(map(int, num_str))
    valid_count = 0
    for idx, current_digit in enumerate(digits):
        if current_digit == 0:
            continue
        # 有効な数字を加算
        valid_count += adjust_digit(current_digit - 1) * (8 ** (len(digits) - idx - 1))
        # 現在の桁が「4」または「9」の場合、以降の計算を終了
        if current_digit == 4 or current_digit == 9:
            break
    # 総数から有効な数字を引く
    return int(num_str) - valid_count

# 入力と範囲内の有効な数字を計算
x, y = map(int, input().split())
result = count_valid_numbers(str(y + 1)) - count_valid_numbers(str(x))
print(result)

場合の数の問題なので、机上でガリガリ解き方を考えたものを実装したのであまり競技プログラミングって感じがしてない……。
「count_valid_numbers」関数の中身をwhile文からfor文に書き換えてくれました。
見てる桁の番目「idx」とその数字「current_digit」の両方を保持しなきゃいけないので書くときに結構頭を悩ませましたが、
enumerate関数などというものがあるのですねぇ。初めて知りました。

おわりに

今日までABC001から順番に全問見ていきましたがこのあたりでストックが尽きたので、
次回からはだいぶ飛び飛びになります。また、解けたもののみの掲載になっていきます。