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: 2017年11月19日12時15分55秒
Last modified: 2014年12月05日00時59分34秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: