乙Py先生のプログラミング教室
初学者のためのプログラミング学習サイト

Python

プログラミング未経験の方のための
プログラミング学習講座を作成しました

その名も
「1時間で学べるPythonプログラミング」


講義動画はこちら




この講座は初学者の方が
短時間でPython言語を学ぶことのできる
プログラミング学習用の講座です

プログラミングが分からないない方は
Python言語を通じて
プログラミングの基礎を学習できます

講座は動画に加えてGoogle Colabを用いて
手元でコードを動かすことのできます
コードがどう動くのかを確認をしながら
進めていってください

資料はここ:
Google Colabの資料


00:00 1.はじめに
02:13 2.導入方法
02:55 3.GoogleColaboratoryの操作方法
06:19 4.Pythonの計算の基礎
27:27 5.Pythonの制御文
42:14 6.Pythonのクラス
49:11 7.Pythonのその他構文
64:30 8.まとめ

なおPythonチートシートを作成しています。

コーディングに迷った際に役に立ち

WEB検索する時間を無くして

作業時間を効率化できます。

note
Pythonチートシート


 

今回はドラクエ1・2リメイククリア記念として
ドラクエ4のコインバグについてやっていきたいと思います。


解説動画はこちら



ドラクエ4とは

ドラゴンクエストIV 導かれし者たち
1990年2月11日にエニックス(合併前)から発売された
ファミリーコンピュータ用ロールプレイングゲーム
『ドラゴンクエストシリーズ』の第4作目

5つの章に分かれたシナリオ、AIによる戦闘システムや
5人以上の仲間キャラクターと同時に
冒険できる馬車システムが導入された作品

ゲームの2,3,5章にはミニゲームとしてカジノがあり
そこではコインバグが使える部分がありました




ドラクエ4のカジノシステムと「コインバグ」

ゲーム内の2,3,5章でいける大都市エンドール
この都市にはカジノがあり、コインが買える

1枚の価格
2章 : 10ゴールド
3章 : 200ゴールド
5章 : 20ゴールド

第3章ではコイン83,887枚を184ゴールドで
第5章では838,861枚を4ゴールドで購入できる

これはワークエリアの算術オーバーフローに起因する判定処理のバグが原因

購入金額の計算を3バイトで行っているため、カジノでコインを購入する際
計算金額が16,777,215ゴールドを超えるとオーバーフローが発生
(2 ** 24 = 16777216)

本来のコインの金額と16777216との差が
購入金額となっていたようです



ファミコンの当時のハードウェア情報


CPU:Ricoh 2A03(6502の派生)
メモリ構造:8bit CPU・少ないRAM

参考 : PS5のCPU:64ビット、スーパーファミコンのCPU:16ビット

ソフト開発はアセンブリ言語を使用
数値の表現方法(8bit × n バイトで多バイト値を管理)
多バイト演算が必要(24bit/32bitの値を手動で扱う)

スプライト制限・PPUなど
制約だらけの開発環境だったようです



ファミコン的な多バイト計算のしくみ


当時の 8bit CPU は一度に扱えるのは 0..255(1バイト)だけ
大きな数は複数バイトに分割して管理する

例:24ビット値は
LO(下位8ビット)
MID(中位8ビット)
HI(上位8ビット)という3バイトで保持


「足し算」は常に低位バイト→高位バイトの順に行い
各段で キャリー(繰り上がり) を次の段へ渡す:
LO = LO1 + LO2 → もし >255 なら carry=1 で LO &= 0xFF
MID = MID1 + MID2 + carry → 同様に繰り上げ
HI = HI1 + HI2 + carry → 最終的にさらに繰り上がれば(HI が 8bit を越える)

その上位のバイトが必要になるが、実装次第で捨てられる


乗算」は 8bit CPU で直接1回の命令で出来ないため
一般に次のどちらかで実装:

1.部分積の加算(schoolbook):
各バイトを8bit×8bitで掛けて(最大16bitの部分積)
適切に桁(バイト)シフトして加算する

2.繰り返し加算(加算を price 回繰り返す):
result = 0;
for i in range(count):
    result += price のようにして加える
(実際はより効率的なシフト+加算で実装されることが多い)


オーバーフローが起きる理由

ゲーム側が「結果を格納する領域」を
3 バイト(24ビット)だけ確保していると
数学的に 24 ビットを超える値は
自動的に上位ビットが切り捨てられる
(つまり結果は result mod 2^24)
これがバグの本質



838,861 × 20 がなぜ 4 になるか

1.コイン枚数(24bit)をバイトに分解:
コイン枚数 = 838,861
LO = 205 = 0xCD
MID = 204 = 0xCC
HI = 12  = 0x0C
検算: 12 * 65536 + 204 * 256 + 205
= 786432 + 52224 + 205 = 838861


2.各バイトの部分積を求める(コイン価格 = 20)
p0 = LO * 20 = 205 * 20 = 4,100 → hex 0x1004
  →bytes = [0x04, 0x10, 0x00, 0x00]
p1 = MID * 20 = 204 * 20 = 4,080 → hex 0x0FF0 → shift 1 byte
  → bytes = [0x00, 0xF0, 0x0F, 0x00]
p2 = HI * 20 = 12  * 20 = 240   → hex 0x00F0 → shift 2 bytes
  → bytes = [0x00, 0x00, 0xF0, 0x00]

3.部分積を下位バイトから順に加算(変数 acc は 4 バイトで保持):

初期
acc = [0x00, 0x00, 0x00, 0x00]

加算 p0
acc = [0x04, 0x10, 0x00, 0x00]


加算 p1:
acc[0] += 0x00 → 0x04
acc[1] += 0xF0 → 0x10 + 0xF0 = 0x100 -> acc[1]=0x00, carry=1
acc[2] += 0x0F + carry -> 0x00 + 0x0F + 1 = 0x10
acc[3] += 0x00 -> 0x00
→ acc = [0x04, 0x00, 0x10, 0x00]

加算 p2:
acc[0] += 0x00 -> 0x04
acc[1] += 0x00 -> 0x00
acc[2] += 0xF0 -> 0x10 + 0xF0 = 0x100 -> acc[2]=0x00, carry=1
acc[3] += 0x00 + carry -> 0x00 + 1 = 0x01
→ acc = [0x04, 0x00, 0x00, 0x01]


4.acc を 32bit で読むと 0x01000004
( 0x01000004 = 16,777,220)

ゲームはここで下位3バイトのみ(0x000004)を保存
→ 0x000004 = 4 が実際にストアされる

数学的には 838,861 * 20 = 16,777,220 だが
16,777,220 mod 2^24 = 4 となり
格納領域(24bit)に収めると 4 になる


Pythonで再現する「疑似アセンブリ」計算コード


当時のファミコンで行われていたであろう計算を
Pythonで模したコードが以下です。
# --- ユーティリティ(24bit <-> 3バイト変換) ---
def to_bytes24(n: int):
    """整数 -> (lo, mid, hi) の3バイト"""
    mask24 = (1 << 24) - 1
    n &= mask24 # 24ビットに制限(実機での格納に相当)
    lo = n & 0xFF
    mid = (n >> 8) & 0xFF
    hi = (n >> 16) & 0xFF
    return lo, mid, hi

def from_bytes24(b):
    lo, mid, hi = b
    return lo | (mid << 8) | (hi << 16)

# --- 8bit 加算(キャリーを明示) ---
def add_with_carry(a: int, b: int, carry_in: int = 0):
    """8bitの加算 -> (結果8bit, carry_out)"""
    s = a + b + carry_in
    result8 = s & 0xFF
    carry_out = 1 if s > 0xFF else 0
    return result8, carry_out

# --- 24bit のバイト単位加算(LO->MID->HI の順でキャリーを伝播) ---
def add24(a_bytes, b_bytes):
    al, am, ah = a_bytes
    bl, bm, bh = b_bytes
    rl, c = add_with_carry(al, bl, 0) # LO を足す(6502での ADC 命令相当)
    rm, c = add_with_carry(am, bm, c) # MID に carry を足す
    rh, c = add_with_carry(ah, bh, c) # HI に carry を足す
    return (rl, rm, rh)

# --- 部分積を使った 24bit x 8bit の乗算(8bit CPU の実装を模倣) ---
def mul24_by_8_partial(count_bytes, price8):
    """
    count_bytes は (lo, mid, hi) の3バイト。
    price8 は 0..255 の 8bit 単価。
    実行は:
      1) 各バイト * price を計算(部分積) -> 最大16bit
      2) それらを適切にシフト(バイト単位)して 4 バイト長の accumulator に足す
      3) 最終的に下位3バイトだけを保存
    """
    lo, mid, hi = count_bytes

    # 各バイトの部分積(16bitまで)
    p0 = lo  * price8   # 部分積0, shift 0 bytes
    p1 = mid * price8   # 部分積1, shift 1 byte (<<8)
    p2 = hi  * price8   # 部分積2, shift 2 bytes (<<16)

    # 各部分積をバイト配列(4バイト:下位から)に展開して加算
    def to_4bytes_le(x):
        return (x & 0xFF, (x >> 8) & 0xFF, (x >> 16) & 0xFF, (x >> 24) & 0xFF)

    # shift としてバイト単位で位置をずらす(p1 は 1 バイトシフト、p2 は 2 バイト)
    b0 = to_4bytes_le(p0)        # p0 << 0
    b1 = to_4bytes_le(p1 << 8)   # p1 << 8  -> 実際は p1 の下位を一つ上のバイトにずらす
    b2 = to_4bytes_le(p2 << 16)  # p2 << 16

    # 4バイト幅で逐次加算(8bit CPU の ADC の連鎖を模倣)
    acc = (0,0,0,0)
    for part in (b0, b1, b2):
        acc = add_4bytes_le(acc, part)

    # 実機が保存するのは下位3バイトのみ(= acc の 0..2 バイト)
    stored24 = (acc[0], acc[1], acc[2])
    return stored24

# 補助:4バイト加算(下位からキャリーを伝える)
def add_4bytes_le(a4, b4):
    r0, c = add_with_carry(a4[0], b4[0], 0)
    r1, c = add_with_carry(a4[1], b4[1], c)
    r2, c = add_with_carry(a4[2], b4[2], c)
    r3, c = add_with_carry(a4[3], b4[3], c)
    return (r0, r1, r2, r3)


簡単に計算できるようにしたコードだとこうなります
当時のFCDQ4のコイン価格を計算してみると
# コイン価格のシミュレーションコード
def simulate_24bit_mul(count, price):
    # count を 3 バイトに分解
    lo = count & 0xFF
    mid = (count >> 8) & 0xFF
    hi = (count >> 16) & 0xFF

    # 部分積
    p0 = lo * price  # fits<=0xFFFF
    p1 = mid * price
    p2 = hi * price

    # 32bit accumulator as int
    full = p0 + (p1 << 8) + (p2 << 16)

    # store as 24bit(下位24bitを取り出す)
    stored24 = full & ((1 << 24) - 1)
    return full, stored24

print(simulate_24bit_mul(100, 20))
print(simulate_24bit_mul(838_860, 20))
print(simulate_24bit_mul(838_861, 20))
print(simulate_24bit_mul(838_862, 20))
print(simulate_24bit_mul(999_999, 20))
(2000, 2000)
(16777200, 16777200)
(16777220, 4)
(16777240, 24)
(19999980, 3222764)




まとめ

ドラクエ4当時の性能では仕方ないバグだったろうと思います。

プログラミング的には相当大変な計算をしていたので
ここまでの確認が出来たかったんだろうと思います
(デバッガーや統合開発環境なさそうだし)

今は実機の性能が上がりすぎて、こういうのは無くなってきてるので
おもしろいバグとかは少なくなってますかね。

なお1990年当時
バグの噂は聞いていて知っていたので、めちゃくちゃ助かったです。
ありがとうエニックスの人!!


PS
ドラクエ1・2リメイク最高でした
ドラクエ3・1・2の流れを埋めるサブストーリー
うるさ過ぎるサマルトリア兄弟
クソ弱いローレシア王子
幼い頃にクリアできなかったので感動しました。
ありがとうスクエアエニックスの人!!





今回は投資信託の比較をするための データ抽出についてです。


解説動画はこちら


 

投資信託の成績比較


今回は投資信託の銘柄選定のために
投資信託の比較をしていきたいと思います。

データをお借りする先はこちら

みんかぶ



データを取得する

リンク先から、比較したい銘柄を選択して
「選択したファンドを比較する」ボタンをクリックすると
銘柄比較画面に飛べるので、そこのURLをコピーしておきます。

このコードでそのページのデータが取得できます。

import pandas as pd
from bs4 import BeautifulSoup
import requests
import re

url = "ここにペースト"
res = requests.get(url)


データ化する

そのままでは使いづらいので
読み込みできる形にします。
soup = BeautifulSoup(res.text, "html.parser")
table = soup.find("table",class_=re.compile("w-full border-t border-slate-300"))
trs = table.find_all("tr")
data = []
for tr in trs:
    tds = tr.find_all("td")
    tmp = []
    for td in tds:
        tmp.append(td.text.replace("\n",""))
    data.append(tmp)
   
df = pd.DataFrame(data)
df

これでデータフレームになり見やすくなりました。
ここから、使うデータだけに絞り込み整形していきます。




ファンド名、リターン、シャープレシオのみ取得する


先ほどのまでのコードで
全体のデータが取得できていたら
必要なものののみ整形します。

今回はファンド名、リターン、シャープレシオの値を使用します。

リターン、シャープレシオの値は
1,3,5年ごとの値になっているので
正規表現でうまく抜き出してデータ化します。
fand_name = data[0]
r1,r3,r5 = [],[],[]
for text in data[10]:
    pat = re.compile(
        r'(\d+)年([+-]?\d+(?:\.\d+)?%?|-)'
        r'(?=\d年|$)'
    )
    pairs = re.findall(pat, text)
    result = {int(y): float(v.replace("%","")) if v!="-" else 0 for y, v in pairs }
    r1.append(result[1])
    r3.append(result[3])
    r5.append(result[5])
    
s1,s3,s5 = [],[],[]
for text in data[11]:
    pat = re.compile(
      r'(\d+)年([+-]?\d+(?:\.\d+)?|-)'
      r'(?=\d年|$)'
    )
    pairs = re.findall(pat, text)
    result = {int(y): float(v) if v!="-" else 0 for y, v in pairs }
    s1.append(result[1])
    s3.append(result[3])
    s5.append(result[5])

df2 = pd.DataFrame()
df2["ファンド名"] = fand_name
df2["1年リターン"] = r1
df2["3年リターン"] = r3
df2["5年リターン"] = r5
df2["1年シャープレシオ"] = s1
df2["3年シャープレシオ"] = s3
df2["5年シャープレシオ"] = s5
df2

ここでうまくファンド名と数値データのみになっていれば
可視化して比較することができます。



リターンとシャープレシオで散布図にする

今回はリターンとシャープレシオを用いて比較していきます。

シャープレシオというのは

投資信託のリターン ÷ リスク(値動きのブレ)

の値で、リスクに対して
どれだけ効率的にリターンをあげているかの目安です。

シャープレシオが高い = より効率よく運用されている
ということになります。

シャープレシオが低い  = リスクを取りすぎている
とも取れます。


一般的な目安としては

シャープレシオの値評価
2.0以上非常に優れた運用成績
1.0から2.0良好な運用成績
0.5から1.0平均的な運用成績
0.5未満改善の余地がある運用成績


ということになっているようです。

早速比較してみましょう
import plotly.express as px

fig = px.scatter(
    df2,
    x="5年リターン",
    y="5年シャープレシオ",
    color="ファンド名",
    hover_name="ファンド名",
    title="ファンド別:5年リターン × 5年シャープレシオ",
)

fig.update_layout(
    xaxis_title="5年リターン (%)",
    yaxis_title="5年シャープレシオ",
    legend_title="ファンド名",
)

fig.show()
スクリーンショット 2025-11-08 16.52.42






まとめ

銘柄が多すぎて選べない際は、リターンやシャープレシオ
手数料、信託報酬などで、色々比較するのが良いです。

同じリターンなら、シャープレシオが高いものの方が
より効率良く運用されているとみなせます。

なお短期のシャープは信用度が低いので
長い期間で見るようにしましょう。


今回はここまでです
それでは

今回はケリー基準を用いた
破産しないための最適資金配分のシミュレーションです。


解説動画はこちら

 




破産しないための最適な賭け金の割合



・問題
コインを投げて、表が出たら賭け金が2倍、裏が出たら全て失う賭けです
このコインは、55%の確率で表が出るやや有利なコインです

手元には100万円あり、このゲームを250回繰り返すとき
毎回いくら賭けるのが最適でしょうか?






--------------------------------------------------------




・回答
ケリー基準をもとに
最適な賭け金を算出することができます。


ケリー基準 : 
資産運用において
最適な資金配分比率を決定するための数式

割合 = (勝率 × オッズ − (1−勝率) ) / オッズ

ここに
勝率 0.55(55%)
オッズ(2倍-1倍 = 1)
を入れると

0.55 - 0.45 = 0.1

資金の0.1倍を賭けるのが
最適解ということになります。




250回の賭けコイン試行シミュレーション


先ほどの問題をシミュレーションするコードです。

初期資金 : 100万円
勝率 : 55%
回数 : 250回

シミュレーション結果を集計した結果を
出力する関数です。
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
pd.options.display.float_format = '{:.2f}'.format

# 250回のコイントスの賭けシミュレーター
def coin_250(default_assets=1000000,times=250,win_rate=0.55):
  kelly_criterion_percentage = (win_rate - (1 - win_rate))
  data = []
  assets = default_assets
  for i in range(times):
    stakes = int(assets * kelly_criterion_percentage)
    assets -= stakes
    result = np.random.choice([1,0],p=[0.55,0.45])
    if result == 1:
      assets += stakes * 2
    tmp =[assets,stakes, int(result)]
    data.append(tmp)
  
  # 250回の結果をデータフレームで集計
  df = pd.DataFrame(data,columns=["assets","stakes","result"])
  max_assets = df["assets"].max()
  min_assets = df["assets"].min()
  max_stakes = df["stakes"].max()
  min_stakes = df["stakes"].min()
  final_ps = int(df["assets"].tail(1).values[0])
  profit = final_ps - default_assets
  win_times = int(df["result"].sum())
  lose_times = len(df) - win_times

  group_id = (df["result"] != df["result"].shift()).cumsum()
  run_lengths = df.groupby(group_id)["result"].sum()
  run_lengths_0 = df.groupby(group_id).apply(lambda x: (len(x) - x["result"].sum()))
  # 最大連敗回数
  max_lose = run_lengths_0.max()
  # 最大連勝回数
  max_win = run_lengths.max()

  result_250 = [max_assets,min_assets,max_stakes,min_stakes,final_ps,profit,win_times,lose_times,max_win,max_lose]
  return result_250

この関数を使って
1000セット試行を行います。
times = 1000
results = []
for i in range(times):
  data = coin_250()
  results.append(data)

columns = ["最大資産","最小資産","最大掛金","最小掛金","最終資産","最終利益","勝利回数","敗北回数","最大連勝","最大連敗"]
df = pd.DataFrame(results,columns=columns)
df.describe()
desc最大資産最小資産最大掛金最小掛金最終資産最終利益勝利回数敗北回数最大連勝最大連敗
count1000.001000.001000.001000.001000.001000.001000.001000.001000.001000.00
mean16066691.73576608.611588961.9557127.3511146821.0310146821.03137.19112.818.496.45
std33581089.69289491.313311346.2928006.3827692950.8927692950.897.917.912.271.56
min900000.007130.00100000.00713.007687.00-992313.00107.0089.004.003.00
25%2515432.75346220.75248966.5034622.001159975.00159975.00132.00108.007.005.00
50%6327419.00575743.50632741.5057574.003163743.502163743.50137.00113.008.006.00
75%15386038.00801900.001515707.5080274.008628829.007628829.00142.00118.0010.007.00
max541305769.001100000.0054130576.00100000.00390665788.00389665788.00161.00143.0026.0014.00


こんな感じの結果になりました

勝利回数の分布をプロットしてみると
download-1

おおよそ勝率55%の回数で正規分布に近似しますね

最終利益はこんな感じです
download

0以上になっていれば、利益が出ている
0未満は負け
ということになります。

今回は1000セットやって
利益が出た回数が762回
0未満は238回でした




まとめ

勝率とオッズが分かっているならケリー基準を元に
資金調整すれば、資金が0になることはほぼ無いです。

ただし、勝率とオッズ次第では
元の資金より減る事もあるので注意が必要です。

より負けたく無い場合は
ケリー基準の半分の割合でかけるなど
保守的な割合にすればもっと負けづらくなります。

株式などにも応用できるため
色々シミュレーションに使うと面白そうです。


今回はここまでです
それでは

今回は競技プログラミングについてです。

解説動画はこちら



競技プログラミングの世界をのぞいてみよう


競技プログラミングとは

プログラミングを「速く・正確に・美しく」解く
頭脳スポーツです。

与えられるのは数行の問題文と、入力例
頭の中でアルゴリズムを組み立て
最速のコードで正答を競います。


競技プログラミングの概要

問題が与えられ、入力例と出力例も与えられます。

問題文から、入力を受け取って
出力例になるようなプログラムコードを書いていきます。

実際の競技では
プログラムコードが開催側のシステム内で実行されて
成否が出るような仕組みになっています。


問題文の例(超初級)

問題:最大値を求めよう

N 個の整数が与えられるので
その中で最大の値を出力してください。

入力例
5
10 3 5 8 2

出力例
10

サンプルコード
N = int(input())
nums = list(map(int, input().split()))
print(max(nums))

通常は計算量や、数値の上限などの制約が与えられます。

正解かどうかの判定は、もっと大掛かりな数値で自動計算されているようで
数が多い場合、制限時間に間に合わないことも有ります。



競技プログラミングの主な大会

AtCoder(日本)
Topcoder(海外)
その他も有るみたいだけど、色々休止中



競技プログラミングはどんなことに役立つのか

1.思考を“構造化”する力が身につく
問題を分解し、条件を抽象化し、最適なアルゴリズムを選ぶ
という一連の思考過程を繰り返し構造化思考力を鍛えることができます

2.アルゴリズムの理解が“AIを使いこなす力”になる
AIが生成したコードを見て
計算量のボトルネック、論理が最適化されているか
入力制約に対応できているか等を判断できます

3.「論理×直感」問題解決能力を鍛える最高のトレーニング
限られた時間と資源の中で最適な解決方法を
論理と直感、両方を磨きながら鍛えることができます

4.キャリアや採用で有利に働く
近年、大企業やスタートアップなどで評価される傾向
アルゴリズムが必要な企業への就職で有利になります




競技プログラミングの問題を解いてみよう


中級くらいの問題集、動画を止めて考えてみてね

問題1 : 文字列の入れ替えチェック(中級)

2つの文字列 S, T が与えられます
S の文字を並べ替えて T にできるなら Yes
できないなら No と出力してください

入力例
listen
silent

出力例
Yes

-------------------------------------------------------------


解説

文字の出現がすべて一致していればOK
sorted(S) == sorted(T) で判定可能です。

S = input().strip()
T = input().strip()
print("Yes" if sorted(S) == sorted(T) else "No")



問題2 : 数字の組み合わせの和(中上級)

N 個の整数が与えられます
この中から3つ選んで、その和が K になる組み合わせの数を求めてください

入力例
5 10
2 3 5 4 1

出力例
2

-------------------------------------------------------------


解説

単純に3重ループで解くコードの場合
3つの数値の和が K になれば OK です。

N, K = map(int, input().split())
A = list(map(int, input().split()))

count = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if A[i] + A[j] + A[k] == K:
                count += 1
print(count)

ただし実際の競技では
3重ループだと、制限に合わない場合があるので
別の方法を検討することが多いようです。

ここでは一例として次のようなアルゴリズムで
解くこととします。

    1.  配列 A の要素をセット S にしておく(探索用)
    2.  二重ループで全ペア (i, j) を探索
    3.  そのペアの和 A[i] + A[j] を計算
    4.  target = K - (A[i] + A[j]) として、 S に存在すればカウント

これをコードに落とすと次のようになります。
# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))

# 集合(SET)を作成
S = set(A)
count = 0
seen = set()  # 同じ組み合わせの重複カウント防止用

for i in range(N):
    for j in range(i + 1, N):
        two_sum = A[i] + A[j]
        target = K - two_sum

        # 3つの値がすべて異なることを確認
        if target in S and target != A[i] and target != A[j]:
            # 組み合わせを小さい順にソートして一意化
            triple = tuple(sorted((A[i], A[j], target)))
            if triple not in seen:
                seen.add(triple)
                count += 1

print(count)






問題3 : 最短経路を求める迷路探索(上級)


H×W のマップが与えられ . は通行可
S から G までの最短距離を求めてください
到達できない場合は -1 を出力

入力例
4 5
S....
.###.
..#G.
.....

出力例
7


------------------------------------------


解説

BFS(幅優先探索 : Breadth First Search)で
最短距離を求めていきます。
(開始地点に近いノードから順に「横に広がるように」探していく手法)

入力は一旦省略し、直接データ化したコードです。
from collections import deque

data = """\
4 5
S....
.###.
..#G.
.....
"""

lines = data.strip().splitlines()
H, W = map(int, lines[0].split())
grid = [list(line) for line in lines[1:]]

# スタート(S)とゴール(G)を探して座標を求める
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            sx, sy = i, j
        if grid[i][j] == "G":
            gx, gy = i, j

# 4方向の移動ベクトルと距離配列の初期化
# dx,dyは上下左右の移動を表す、dist は各セルへの最短距離(始点からの距離)
# 訪問したら dist[nx][ny] = dist[x][y] + 1 と更新
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
dist = [[-1]*W for _ in range(H)]

# キュー初期化と始点の距離設定
# 始点をキューに入れて距離 0 をセット
# 以降はキューから取り出すごとに、そのセルから隣接を探索
q = deque()
q.append((sx, sy))
dist[sx][sy] = 0

# BFS のメインループ
# q.popleft() でキューの先頭から取り出し(FIFO)
# 4方向それぞれについて:
#	•	範囲チェック(境界外は無視)
#	•	壁 (#) なら通れないので無視
#	•	dist[nx][ny] == -1 は未訪問の確認(訪問済みならスキップ)
# 未訪問かつ通行可なら距離を +1 してキューに追加
while q:
    x, y = q.popleft()
    for k in range(4):
        nx, ny = x + dx[k], y + dy[k]
        if 0 <= nx < H and 0 <= ny < W:
            if grid[nx][ny] != "#" and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

# G に到達していれば dist[gx][gy] は非負の最短距離
#	到達していなければ -1(初期値)のまま出力される
print(dist[gx][gy])




まとめ

最適なアルゴリズムが必要な業務には
競技プログラミングの知識が役にたちます。

すごく時間の掛かる処理の高速化、省力化、消費電力低下など
実務面で有効な場面はかなり多いです。

若い人は就職面でも有利になるので、
競技プログラミングに取り組むのかかなりオススメです。


このページのトップヘ