ABC155E

問題

E - Payment

紙幣の価値がである時、価値のたこ焼き器を買う場合の、自分と店員の使う紙幣の枚数の合計の最小値を求めよ。

解法

下位桁から順に見ていく。

4以下の場合

自分がその枚数を使う。

6以上の場合

一つ上の桁を+1し、店員が10-xの枚数を使う。

5の場合

一つ上の桁が4以下の場合

自分が5枚使う。

一つ上の桁が5以上の場合、

一つ上の桁を+1し、店員が5枚使う。

一つ上の桁が6以上の場合、元々繰り上がりは確定しているので、一つ上の桁で店員の使う枚数を1減らすことができる。

一つ上の桁が5の場合、二つ上の桁が4以下だった場合に使う枚数が1増えてしまうが、一つ上の桁で使う枚数を1減らしているため問題ない。

コード

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
  string s; cin >> s;
  vector<int> n(s.size()+1);
  n[0] = 0;
  for (int i = 0; i < s.size(); i++) n[i+1] = s[i] - '0';
  long long ans = 0;
  for (int i = n.size()-1; i > 0; i--) {
    if (n[i] == 5 && n[i-1] < 5) {
      ans += 5;
    }
    else if (n[i] < 5) {
      ans += n[i];
    }
    else {
      ans += 10 - n[i];
      n[i-1]++;
    }
  }
  cout << ans + n[0] << endl;
}

感想

コンテスト中は何となくで通してしまったので反省。

ただ、ゲームだから良いよね…。