問題
既存投稿一覧ページへのリンク
解法手順1
-
入力を受け取る：
- N（箱と荷物の数）
- A（各荷物が最初に入っている箱の番号）
- W（各荷物の重さ）
-
結果を格納する変数 ret を 0 で初期化する。
-
各箱に入っている荷物の最大重さを記録する配列 boxes を、長さ N で 0 で初期化する。
-
各荷物について以下の処理を行う：
- 荷物が元々入っている箱の番号 a を取得する（0-indexedに調整）。
- 荷物の重さ w を取得する。
- min(boxes[a], w) を ret に加算する。これが移動のコストとなる。
- boxes[a] を max(boxes[a], w) で更新する。これにより、箱 a に入っている最大の重さを記録する。
-
最終的な ret の値を出力する。これが求める最小コストとなる。
ACコード1
ac.py
import logging
def setup_logger(debug_mode):
logger = logging.getLogger(__name__)
if not logger.handlers: # ハンドラが存在しない場合のみ追加
logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
file_handler.setFormatter(formatter)
logger.addHandler(file_handler)
return logger
def io_func():
# 入力を受け取る
N = int(input()) # 箱と荷物の数
A = list(map(int, input().split())) # 各荷物が最初に入っている箱の番号
W = list(map(int, input().split())) # 各荷物の重さ
return N, A, W
def solve(N, A, W, logger):
logger.debug("処理を開始します")
logger.debug(f"N:: (={N}), A: (={A}), W: (={W})")
# 結果を格納する変数を初期化
ret = 0
logger.debug(f"結果変数 ret を {ret} で初期化しました")
# 各箱に入っている荷物の最大重さを記録する配列を初期化
boxes = [0] * N
logger.debug(f"boxes 配列を長さ {N} で初期化しました: {boxes}")
# 各荷物について処理を行う
for i, a in enumerate(A):
a -= 1 # 0-indexedに調整
w = W[i]
logger.debug(f"荷物 {i+1}: 箱番号 {a+1}, 重さ {w}")
# 移動コストを計算し、結果に加算
ret += min(boxes[a], w)
logger.debug(f"移動コスト {min(boxes[a], w)}(min(boxes[{a}](={boxes[a]}), {w})) を ret に加算しました。現在の ret: {ret}")
# 箱の最大重さを更新
boxes[a] = max(boxes[a], w)
logger.debug(f"箱 {a+1} の最大重さを {boxes[a]}(boxes[{a}]) に更新しました")
logger.debug(f"boxes: {boxes}")
logger.debug(f"全ての処理が完了しました。最終的な ret: {ret}")
return ret
def main():
logger = setup_logger(debug_mode=True)
N, A, W = io_func()
result = solve(N, A, W, logger)
print(result)
if __name__ == "__main__":
main()
###
# N: 箱と荷物の数
# A: 各荷物が最初に入っている箱の番号のリスト
# W: 各荷物の重さのリスト
# ret: 最小コストを格納する変数
# boxes: 各箱に入っている荷物の最大重さを記録する配列
# 1. io_func関数:
# - 標準入力から N, A, W を読み取る
# - 読み取った値を返す
# 2. solve関数:
# - 引数として N, A, W, logger を受け取る
# - ret を 0 で初期化
# - boxes を長さ N の 0 で初期化された配列として作成
# - A と W をイテレートし、各荷物について:
# - 箱番号を 0-indexed に調整
# - 移動コスト（現在の箱の最大重さと荷物の重さの小さい方）を ret に加算
# - 箱の最大重さを更新
# - 最終的な ret を返す
# 3. main関数:
# - logger を設定
# - io_func を呼び出して入力を取得
# - solve 関数を呼び出して結果を計算
# - 結果を出力
メモ
各箱のなかで最大の重さであれば移動せず留まっていて良い。