yukicoder No.35 タイパー高橋 解説

問題文

解説

i個目の質問に関する解はこんな感じ。
i番目の打てるタイプ数は
$min(floor(T_i*12/1000),|S_i|)$

$min$の左は、問題文の計算式の$x$に$T_i$を代入したものである。
ただ、$floor(T_i*12/1000)$はいくら大きかろうが、結果打てる限界値は$|S_i|$なので、結果打てるタイプ数は上記二つの最小値となるわけだ。

i番目の取り逃すタイプ数は
$|S_i|-打てるタイプ数_i$
こうして、$\sum_{i=1}^N打てるタイプ数_i$つまり、打てるタイプ数の総和と
$\sum_{i=1}^N取り逃すタイプ数_i$つまり、取り逃す数の総和を求めればOK。
ちなみに余談だが、このような割り算が来る問題は私の場合いつも誤差のことで不安になるので、自作のfloor関数という割り算の誤差を確実になくすための関数を使っている。
こんなやつ。

int floor(int x, int m) {
  int r=(x%m+m)%m;
  return (x-r)/m;
}

これをつかえば、こんな問題でのWAを防げる。

C++での解答例

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

int floor(int x, int m) {
  int r=(x%m+m)%m;
  return (x-r)/m;
}

int main(){
  int n,ok=0,ng=0;cin>>n;
  //ok=打てるタイプ数、ng=取り逃すタイプ数
  for(int i=0;i<n;i++){
    int t;string s;cin>>t>>s;
    int e=min(floor(t*12,1000),(int)(s.size()));
    ok+=e;
    ng+=s.size()-e;
  }
  cout<<ok<<" "<<ng<<endl;
}