保存されている過去のバージョンの一覧

2017年04月08日22時50分31秒
2017年04月08日22時49分32秒

AtCoder Regular Contest #071/AtCoder Beginner Contest #058 C問題 - 怪文書 / Dubious Document

Source

AtCoder Regular Contest #071
AtCoder Beginner Contest #058
問題文 (ARC)
問題文 (ABC)

問題概要

$N$ 個の紙があり,$i$ 番目の紙には文字列 $S_i$ が書かれている.
$1$ つの紙がもらえるので,その紙に書かれた文字を切り抜いて,好きな文字列を作ることを考える.
どの紙がもらえるかわからないが,作る文字列は予め決めて置かなければならない.
どの紙がもらえても作れる文字列のうち,最も長い文字列,その中で辞書順最小のものを求める問題.

解法

文字列 $S_i$ にアルファベットの $\verb|a|$ が $k_i$ 個含まれてるとすると,使える $\verb|a|$ の個数は $\min(k_1,k_2,\ldots,k_N)$ 個となる.
よって,全ての文字に対して,使える文字数を求めて,使えるだけ $\verb|a|$ から順番に並べれば良い.

cLayversion 20170408-3)のコード

C++に変換後のコードはこちら

{
  int N;
  char S[55];
  
  int res[26], hist[26];
  int i, j, len;

  res[0..25] = 100;
  rd(N);
  while(N--){
    rd(S);
    len = strlen(S);
    S[0..len-1] -= 'a';
    hist[0..25] = 0;
    hist[S[0..len-1]]++;
    res[0..25] <?= hist[0..];
  }
  

  rep(i,26) rep(j,res[i]) putchar_unlocked('a'+i);
  putchar_unlocked('\n');
}

Current time: 2024年03月29日18時34分59秒
Last modified: 2017年04月08日22時50分31秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest AtCoder_Beginner_Contest ARC071 ARC_A ABC058 ABC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: