Official

B - String Too Long Editorial by toam


はじめに入力をすべて受け取り,\(l_i\) の総和(すなわち \(S\) の長さ)が \(100\) より大きければ Too Long と出力し,\(100\) 以下ならば 各 \(i\) に対して \(c_i\)\(l_i\) 回出力することでこの問題を解くことができます.

ただし,オーバーフローには十分気を付けてください.例えば c++ で long long を用いて \(l_i\) の総和を次のように求めようとすると Wrong Answer になります.

long long sum = 0;
for (int i = 0; i < N; i++) {
  char c;
  long long l;
  cin >> c >> l;
  sum += l;
}
if (sum > 100) {
  cout << "Too Long";
} else {
  // S を出力
}
落ちるケース 総和が $2^{64}+100$ のケースです.
19
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 1000000000000000000
b 1000000000000000000
a 446744073709551716  


これを回避するには,例えば sum の総和を求めるループの部分で,sum\(100\) を超えた瞬間に即座に打ち切ればよいです.

実装例(c++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int N;
  vector<pair<char, ll>> P;
  cin >> N;
  ll sum = 0;
  for (int i = 0; i < N; i++) {
    char c;
    ll L;
    cin >> c >> L;
    sum += L;
    if (sum > 100) {
      cout << "Too Long" << endl;
      return 0;
    }
    P.push_back({c, L});
  }
  for (auto [c, l] : P) {
    while (l--) cout << c;
  }
  cout << endl;
}

Python などのオーバーフローを気にしなくて良い言語はそのまま書いても良いです.

実装例(Python)

N = int(input())
P = []
for i in range(N):
    c, l = input().split()
    P.append([c, int(l)])
if sum(map(lambda x: x[1], P)) > 100:
    print("Too Long")
else:
    S = ""
    for c, l in P:
        S += c * l
    print(S)

posted:
last update: