早稲田卒のAI研究者のブログ

データサイエンス、機械学習、競技プログラミング、音楽、勉強

【練習問題】ABC135 C - City SaversをPythonで解いてみた

atcoder.jp


今日はAtcoderについての記事です。
特に、このアルゴリズムを使う!っていう問題でもなく、たまには簡単な練習のような問題も解きたいなと思い、上記の問題を選択しました。

問題はいつものように、上のリンクから見てください。

思考の過程

なるほど。

Atcoderの問題に慣れていないと困惑してしまうような問題ですね。

困惑させる原因は確実に、サンプル1の解答です。
1番目の勇者が倒すモンスターの数が、意味もなく中途半端なものになっています。

例に騙されず、問題の本質を見極める、という意味では良問かもしれませんね。

さて、解答した方法について説明していきます。

まず、1番目の勇者が倒すモンスターの数は中途半端である必要はありません。
というのも、1番目の街のモンスターは1番目の勇者しか倒すことができないからです。

したがって、1番目の勇者は1番目の街のモンスターを全力で倒し、余力が残っていれば、2番目の街のモンスターを倒す、というのが最適になります。
そのあと、2番目の街に残ったモンスターは1番目の勇者しか倒せないので、2番目の勇者は2番目の街のモンスターを全力で倒し、余力が残っていれば、3番目の街のモンスターを倒す、というのをN回繰り返していきます。

コード実装

プログラムの流れは以下のようにする。
1. 解答の初期値を0に設定
2. 全ての勇者の数だけforで回す
3. モンスターの数と勇者の倒せる数を比較
4. 解答を更新し、出力


n = int(input())
AL = list(map(int, input().split()))
BL = list(map(int, input().split()))
ans = 0
for i in range(n):
    if BL[i] <= AL[i]:
        ans += BL[i]
    elif BL[i] > AL[i] and BL[i] <= AL[i]+AL[i+1]:
        ans += BL[i]
        AL[i+1] = AL[i+1] - BL[i] + AL[i]
    else:
        ans += AL[i]+AL[i+1]
        AL[i+1] = 0
print(ans)


無事ACでした!
すこし簡単でしたね。。
最近のABCのC問題は簡単ですね。
今度はより難易度が高い問題を解いてみます。