yukicoder No.35 - タイパー高橋（writer担当）

Source

ニコニコミュニティ
問題文

問題概要

タイピングゲームにおいて，高橋くんは $1$ 秒当たり $12$ 文字打てます．
このタイピングゲームでは $N$ 個の単語を打たなければいけなく，$k$ 個目の単語 $S_k$ とそれを打つ時間制限 $T_k$ がミリ秒単位で与えられます．
高橋くんはできるだけ多くタイピングするとして，何文字打つことができ，何文字打ち逃すかを求める問題．

解法

例えば，各単語ごとに，制限時間から打てる文字数を求めて，単語の文字数と打てる文字数の小さい方だけ文字を打てる．
その和を求めて，最後に，全ての単語の文字数の和からそれを引いたものも求める．
時間計算量は $O(N |S_k|)$ 程度．

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N;
int T[1111];
char S[1111][111]; int len[1111];

int main(){
  int i, j, k;
  int res1 = 0, res2 = 0;

  scanf("%d",&N);
  assert(1 <= N && N <= 1000);
  rep(i,N){
    scanf("%d%s",T+i,S[i]);
    len[i] = strlen(S[i]);

    assert(1 <= T[i] && T[i] <= 30000);
    assert(1 <= len[i] && len[i] <= 100);
    rep(k,len[i]) assert('a'<=S[i][k] && S[i][k] <= 'z');
  }

  rep(i,N){
    k = min(len[i], T[i] * 12 / 1000);
    res1 += k;
    res2 += len[i] - k;
  }

  printf("%d %d\n", res1, res2);

  return 0;
}

Current time: 2024年04月26日07時08分57秒
Last modified: 2014年12月05日00時59分34秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：