Submission #1769576
Source Code Expand
/**
*
*/
// #include {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <forward_list>
#include <functional>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#ifdef DEBUG
#include <fmt/format.h>
#include <fmt/ostream.h>
#endif
using namespace std;
// }}}
// type {{{
using s8 = int8_t;
using u8 = uint8_t;
using s16 = int16_t;
using u16 = uint16_t;
using s32 = int32_t;
using u32 = uint32_t;
using s64 = int64_t;
using u64 = uint64_t;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
// }}}
// hide {{{
#ifdef __clang__
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunused-const-variable"
#endif
// }}}
// 適宜調整
//#define int s64
//#define double long double
constexpr bool AUTOFLUSH = false;
constexpr bool STDIO_ENABLE = false;
constexpr int IOS_PREC = 10;
constexpr int INF_S32 = 1'010'000'000;
constexpr s64 INF_S64 = 1'010'000'000'000'000'000LL;
constexpr auto INF = INF_S64;
constexpr double EPS = 1e-9;
constexpr s64 MOD = 1'000'000'007;
// hide {{{
#ifdef __clang__
#pragma clang diagnostic pop
#endif
// }}}
// util {{{
template<typename T, size_t N, size_t... NS>
struct ArrayStruct {
using type = array<typename ArrayStruct<T,NS...>::type,N>;
};
template<typename T, size_t N>
struct ArrayStruct<T,N> {
using type = array<T,N>;
};
template<typename T, size_t N, size_t... NS>
using Array = typename ArrayStruct<T,N,NS...>::type;
template<typename T>
constexpr bool is_odd(T x)
{
return x % 2 != 0;
}
template<typename T>
constexpr bool is_even(T x)
{
return x % 2 == 0;
}
template<typename T>
constexpr int cmp(T x, T y)
{
return (x > y) - (x < y);
}
template<typename T>
constexpr int sgn(T x)
{
return cmp(x, T(0));
}
template<typename T>
constexpr T ipow(T a, T b)
{
assert(b >= 0);
T res(1);
for(T i = 0; i < b; ++i)
res *= a;
return res;
}
template<
typename T,
std::enable_if_t<
std::is_integral<T>::value &&
std::is_signed<T>::value, std::nullptr_t> = nullptr>
constexpr T div_ceil(T a, T b)
{
return a/b + (((a<0)^(b>0)) && (a%b));
}
template<
typename T,
std::enable_if_t<
std::is_integral<T>::value &&
std::is_unsigned<T>::value, std::nullptr_t> = nullptr>
constexpr T div_ceil(T a, T b)
{
return a/b + !!(a%b);
}
template<
typename T,
std::enable_if_t<
std::is_integral<T>::value &&
std::is_signed<T>::value, std::nullptr_t> = nullptr>
constexpr T div_floor(T a, T b)
{
return a/b - (((a>0)^(b>0)) && (a%b));
}
template<
typename T,
std::enable_if_t<
std::is_integral<T>::value &&
std::is_unsigned<T>::value, std::nullptr_t> = nullptr>
constexpr T div_floor(T a, T b)
{
return a/b;
}
template<typename T, typename U>
constexpr auto modulo(T a, U b)
{
using R = common_type_t<T,U>;
assert(b > 0);
R r = a % b;
return r >= 0 ? r : r+b;
}
template<typename T>
constexpr T clamp(T x, T lo, T hi)
{
assert(lo <= hi);
if(x < lo)
return lo;
else if(x > hi)
return hi;
else
return x;
}
template<typename T>
T isqrt(T x)
{
assert(x >= 0);
return static_cast<T>(sqrt(static_cast<long double>(x)));
}
template<typename T, typename U>
bool chmax(T& xmax, const U& x)
{
if(x > xmax) {
xmax = x;
return true;
}
else {
return false;
}
}
template<typename T, typename U>
bool chmin(T& xmin, const U& x)
{
if(x < xmin) {
xmin = x;
return true;
}
else {
return false;
}
}
template<typename T>
constexpr int SIZE(const T& c)
{
return static_cast<int>(c.size());
}
template<typename T, size_t N>
constexpr int SIZE(const T (&)[N])
{
return static_cast<int>(N);
}
template<typename InputIt, typename T>
int argfind(InputIt first, InputIt last, const T& x)
{
auto it = find(first, last, x);
return distance(first, it);
}
template<typename InputIt>
int argmax(InputIt first, InputIt last)
{
auto it = max_element(first, last);
return distance(first, it);
}
template<typename InputIt>
int argmin(InputIt first, InputIt last)
{
auto it = min_element(first, last);
return distance(first, it);
}
template<typename InputIt>
bool alltrue(InputIt first, InputIt last)
{
return all_of(first, last, [](bool b) { return b; });
}
template<typename InputIt>
bool anytrue(InputIt first, InputIt last)
{
return any_of(first, last, [](bool b) { return b; });
}
template<typename InputIt>
bool allfalse(InputIt first, InputIt last)
{
return !anytrue(first, last);
}
template<typename InputIt>
bool anyfalse(InputIt first, InputIt last)
{
return !alltrue(first, last);
}
template<typename T>
array<pair<T,T>,4> neighbor4(const T& x, const T& y)
{
return array<pair<T,T>,4> {{
{ x, y-1 },
{ x-1, y }, { x+1, y },
{ x, y+1 },
}};
}
template<typename T>
array<pair<T,T>,8> neighbor8(const T& x, const T& y)
{
return array<pair<T,T>,8> {{
{ x-1, y-1 }, { x, y-1 }, { x+1, y-1 },
{ x-1, y }, { x+1, y },
{ x-1, y+1 }, { x, y+1 }, { x+1, y+1 },
}};
}
template<typename T>
bool in_bounds(const T& x, const T& minx, const T& maxx)
{
return !(x < minx) && !(maxx < x);
}
template<typename T>
bool in_bounds_2(
const T& x, const T& y,
const T& minx, const T& miny,
const T& maxx, const T& maxy)
{
return in_bounds(x, minx, maxx) && in_bounds(y, miny, maxy);
}
template<typename T>
bool in_bounds_wh(const T& x, const T& y, const T& w, const T& h)
{
return in_bounds_2(x, y, 0, 0, w-1, h-1);
}
struct pairhash {
template<typename T1, typename T2>
size_t operator()(const pair<T1,T2>& p) const
{
size_t res = 17;
res = 31*res + hash<T1>()(p.first);
res = 31*res + hash<T2>()(p.second);
return res;
}
};
struct vectorhash {
template<typename T>
size_t operator()(const vector<T>& v) const
{
size_t res = 17;
res = 31*res + hash<size_t>()(v.size());
for(const auto& e : v) {
res = 31*res + hash<T>()(e);
}
return res;
}
};
template<typename K, typename V>
pair<typename map<K,V>::iterator, bool> insert_or_assign(map<K,V>& m, const K& k, const V& v)
{
auto it = m.lower_bound(k);
if(it != end(m) && !m.key_comp()(k,it->first)) {
it->second = v;
return make_pair(it, false);
}
else {
auto it_ins = m.insert(it, make_pair(k,v));
return make_pair(it_ins, true);
}
}
template<typename K, typename V>
pair<typename unordered_map<K,V>::iterator, bool>
insert_or_assign(unordered_map<K,V>& m, const K& k, const V& v)
{
auto it = m.find(k);
if(it != end(m)) {
it->second = v;
return make_pair(it, false);
}
else {
auto it_ins = m.insert(it, make_pair(k,v));
return make_pair(it_ins, true);
}
}
template<typename T>
string TO_STRING(const T& x)
{
ostringstream out;
out << x;
return out.str();
}
template<typename InputIt>
string JOIN(InputIt first, InputIt last, const string& sep)
{
ostringstream out;
while(first != last) {
out << *first++;
if(first != last)
out << sep;
}
return out.str();
}
template<typename InputIt>
auto SUM(InputIt first, InputIt last)
{
using T = typename iterator_traits<InputIt>::value_type;
return accumulate(first, last, T());
}
template<typename T>
void UNIQ(T& c)
{
c.erase(unique(begin(c), end(c)), end(c));
}
template<typename T, typename F>
enable_if_t<rank<T>::value==0> ARRAY_FOREACH(T& e, F f)
{
f(e);
}
template<typename Array, typename F>
enable_if_t<rank<Array>::value!=0> ARRAY_FOREACH(Array& ary, F f)
{
for(auto& e : ary)
ARRAY_FOREACH(e, f);
}
template<typename Array, typename U>
enable_if_t<rank<Array>::value!=0> ARRAY_FILL(Array& ary, const U& v)
{
ARRAY_FOREACH(ary, [&v](auto& elem) { elem = v; });
}
template<typename T>
T POP_BACK(vector<T>& que)
{
T x = que.back(); que.pop_back();
return x;
}
template<typename T>
T POP_BACK(deque<T>& que)
{
T x = que.back(); que.pop_back();
return x;
}
template<typename T>
T POP_FRONT(deque<T>& que)
{
T x = que.front(); que.pop_front();
return x;
}
template<typename T, typename C>
T POP(stack<T,C>& stk)
{
T x = stk.top(); stk.pop();
return x;
}
template<typename T, typename C>
T POP(queue<T,C>& que)
{
T x = que.front(); que.pop();
return x;
}
template<typename T, typename Cont, typename Cmp>
T POP(priority_queue<T,Cont,Cmp>& que)
{
T x = que.top(); que.pop();
return x;
}
template<typename T>
void RD(T& x)
{
cin >> x;
#ifdef DEBUG
if(!cin) assert(false);
#endif
}
template<typename T>
void RD(vector<T>& v, int n)
{
v.reserve(n);
for(int i = 0; i < n; ++i) {
T e; RD(e);
v.emplace_back(e);
}
}
// 出力 {{{
// FPRINTSEQ {{{
template<typename InputIt>
ostream& FPRINTSEQ(ostream& out, InputIt first, InputIt last)
{
for(InputIt it = first; it != last; ++it) {
if(it != first) out << ' ';
out << *it;
}
return out;
}
template<typename InputIt>
ostream& PRINTSEQ(InputIt first, InputIt last)
{
return FPRINTSEQ(cout, first, last);
}
template<typename InputIt>
ostream& DPRINTSEQ(InputIt first, InputIt last)
{
#ifdef DEBUG
FPRINTSEQ(cerr, first, last);
#endif
return cerr;
}
// }}}
// 1次元生配列 {{{
template<typename T, size_t N>
ostream& FPRINTARRAY1(ostream& out, const T (&c)[N])
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
template<typename T, size_t N>
ostream& PRINTARRAY1(const T (&c)[N])
{
return FPRINTARRAY1(cout, c);
}
template<typename T, size_t N>
ostream& DPRINTARRAY1(const T (&c)[N])
{
#ifdef DEBUG
FPRINTARRAY1(cerr, c);
#endif
return cerr;
}
// }}}
// 2次元生配列 {{{
template<typename T, size_t N1, size_t N2>
ostream& FPRINTARRAY2(ostream& out, const T (&c)[N1][N2])
{
out << '\n';
for(const auto& e : c) {
FPRINTARRAY1(out, e) << '\n';
}
return out;
}
template<typename T, size_t N1, size_t N2>
ostream& PRINTARRAY2(const T (&c)[N1][N2])
{
return FPRINTARRAY2(cout, c);
}
template<typename T, size_t N1, size_t N2>
ostream& DPRINTARRAY2(const T (&c)[N1][N2])
{
#ifdef DEBUG
FPRINTARRAY2(cerr, c);
#endif
return cerr;
}
// }}}
// 非mapコンテナ {{{
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& c)
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
// 特別扱い
template<typename T>
ostream& operator<<(ostream& out, const vector<vector<T>>& c)
{
out << '\n';
for(const auto& e : c) {
out << e << '\n';
}
return out;
}
// 特別扱い
ostream& operator<<(ostream& out, const vector<string>& c)
{
out << '\n';
for(const string& e : c) {
out << e << '\n';
}
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const deque<T>& c)
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
template<typename T>
ostream& operator<<(ostream& out, const list<T>& c)
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
template<typename T>
ostream& operator<<(ostream& out, const forward_list<T>& c)
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
template<typename T>
ostream& operator<<(ostream& out, const set<T>& c)
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
template<typename T>
ostream& operator<<(ostream& out, const unordered_set<T>& c)
{
return out << set<T>(cbegin(c), cend(c));
}
template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& c)
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
template<typename T>
ostream& operator<<(ostream& out, const unordered_multiset<T>& c)
{
return out << multiset<T>(cbegin(c), cend(c));
}
template<typename T, size_t N>
ostream& operator<<(ostream& out, const array<T,N>& c)
{
return FPRINTSEQ(out, cbegin(c), cend(c));
}
// }}}
// mapコンテナ {{{
template<typename InputIt>
ostream& FPRINTMAP(ostream& out, InputIt first, InputIt last)
{
out << "{\n";
for(auto it = first; it != last; ++it) {
out << " " << it->first << " : " << it->second << '\n';
}
out << "}\n";
return out;
}
template<typename InputIt>
ostream& PRINTMAP(InputIt first, InputIt last)
{
return FPRINTMAP(cout, first, last);
}
template<typename InputIt>
ostream& DPRINTMAP(InputIt first, InputIt last)
{
#ifdef DEBUG
FPRINTMAP(cerr, first, last);
#endif
return cerr;
}
template<typename K, typename V>
ostream& operator<<(ostream& out, const map<K,V>& c)
{
return FPRINTMAP(out, cbegin(c), cend(c));
}
template<typename K, typename V>
ostream& operator<<(ostream& out, const unordered_map<K,V>& c)
{
return out << map<K,V>(cbegin(c), cend(c));
}
template<typename K, typename V>
ostream& operator<<(ostream& out, const multimap<K,V>& c)
{
return FPRINTMAP(out, cbegin(c), cend(c));
}
template<typename K, typename V>
ostream& operator<<(ostream& out, const unordered_multimap<K,V>& c)
{
return out << multimap<K,V>(cbegin(c), cend(c));
}
// }}}
// stack/queue/priority_queue {{{
template<typename T, typename C>
ostream& operator<<(ostream& out, stack<T,C> c)
{
while(!c.empty()) {
out << c.top();
c.pop();
if(!c.empty()) out << ' ';
}
return out;
}
template<typename T, typename C>
ostream& operator<<(ostream& out, queue<T,C> c)
{
while(!c.empty()) {
out << c.front();
c.pop();
if(!c.empty()) out << ' ';
}
return out;
}
template<typename T, typename Cont, typename Cmp>
ostream& operator<<(ostream& out, priority_queue<T,Cont,Cmp> c)
{
while(!c.empty()) {
out << c.top();
c.pop();
if(!c.empty()) out << ' ';
}
return out;
}
// }}}
// pair/tuple {{{
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1,T2>& p)
{
return out << '(' << p.first << ',' << p.second << ')';
}
template<typename Tuple, size_t Pos>
ostream& FPRINTTUPLE(ostream& out, const Tuple&)
{
return out;
}
template<typename Tuple, size_t Pos, typename T, typename... TS>
ostream& FPRINTTUPLE(ostream& out, const Tuple& t)
{
if(Pos != 0)
out << ',';
out << get<Pos>(t);
return FPRINTTUPLE<Tuple,Pos+1,TS...>(out, t);
}
template<typename... TS>
ostream& operator<<(ostream& out, const tuple<TS...>& t)
{
out << '(';
FPRINTTUPLE<tuple<TS...>,0,TS...>(out, t);
out << ')';
return out;
}
// }}}
// PRINT {{{
ostream& FPRINT(ostream& out) { return out; }
template<typename T, typename... TS>
ostream& FPRINT(ostream& out, const T& x, const TS& ...args)
{
out << x;
if(sizeof...(args))
out << ' ';
return FPRINT(out, args...);
}
template<typename... TS>
ostream& FPRINTLN(ostream& out, const TS& ...args)
{
FPRINT(out, args...);
return out << '\n';
}
template<typename... TS>
ostream& PRINT(const TS& ...args)
{
return FPRINT(cout, args...);
}
template<typename... TS>
ostream& PRINTLN(const TS& ...args)
{
return FPRINTLN(cout, args...);
}
template<typename... TS>
ostream& DPRINT(const TS& ...args)
{
#ifdef DEBUG
FPRINT(cerr, args...);
#endif
return cerr;
}
template<typename... TS>
ostream& DPRINTLN(const TS& ...args)
{
#ifdef DEBUG
FPRINTLN(cerr, args...);
#endif
return cerr;
}
// }}}
// }}}
void FLUSH()
{
if(STDIO_ENABLE)
fflush(stdout);
else
cout.flush();
}
[[noreturn]] void EXIT()
{
#ifdef DEBUG
fflush(stdout);
fflush(stderr);
cout.flush();
cerr.flush();
#else
FLUSH();
#endif
//quick_exit(0); // does not work on codeforces
_Exit(0);
}
struct IoInit {
IoInit()
{
#ifndef DEBUG
cin.tie(nullptr);
if(!STDIO_ENABLE)
ios::sync_with_stdio(false);
#endif
cout << fixed << setprecision(IOS_PREC);
if(AUTOFLUSH) {
if(STDIO_ENABLE)
setvbuf(stdout, nullptr, _IONBF, 0);
cout << unitbuf;
}
}
} IOINIT;
#define FOR(i, start, end) for(s64 i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cc) { return (f)(begin(cc), end(cc), ## __VA_ARGS__); })(c))
#define GENERIC(f) ([](auto&&... args) -> decltype(auto) { return (f)(forward<decltype(args)>(args)...); })
#define MEMSET(a,v) memset((a), (v), sizeof(a))
#define DBG(x) DPRINTLN('L', __LINE__, ':', #x, ':', (x))
// }}}
s64 N;
s64 K;
void solve()
{
array<s64,26> cnt {};
REP(_, N) {
string s; RD(s);
++cnt[s[0]-'A'];
}
max_heap<s64> que;
REP(i, 26) {
if(cnt[i] > 0)
que.emplace(cnt[i]);
}
DBG(que);
s64 ans = 0;
for(;;) {
vector<s64> tmp(K);
REP(i, K) {
if(que.empty()) goto finish;
tmp[i] = POP(que) - 1;
}
for(auto e : tmp) {
if(e > 0)
que.emplace(e);
}
DBG(que);
++ans;
}
finish: ;
PRINTLN(ans);
}
signed main(signed /*argc*/, char** /*argv*/)
{
RD(N);
RD(K);
solve();
EXIT();
}
Submission Info
Submission Time |
|
Task |
B - Problem Committee |
User |
yumsiim |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
17820 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample.txt, 01_sample.txt, corner_case_20.txt, corner_case_21.txt, corner_case_22.txt, corner_case_23.txt, corner_case_24.txt, corner_case_25.txt, corner_case_26.txt, corner_case_27.txt, corner_case_28.txt, corner_case_29.txt, random_case_00.txt, random_case_01.txt, random_case_02.txt, random_case_03.txt, random_case_04.txt, random_case_05.txt, random_case_06.txt, random_case_07.txt, random_case_08.txt, random_case_09.txt, random_case_10.txt, random_case_11.txt, random_case_12.txt, random_case_13.txt, random_case_14.txt, random_case_15.txt, random_case_16.txt, random_case_17.txt, random_case_18.txt, random_case_19.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample.txt |
AC |
1 ms |
256 KB |
01_sample.txt |
AC |
1 ms |
256 KB |
corner_case_20.txt |
AC |
1 ms |
256 KB |
corner_case_21.txt |
AC |
1 ms |
256 KB |
corner_case_22.txt |
AC |
1 ms |
256 KB |
corner_case_23.txt |
AC |
1 ms |
256 KB |
corner_case_24.txt |
AC |
3 ms |
256 KB |
corner_case_25.txt |
AC |
3 ms |
256 KB |
corner_case_26.txt |
AC |
3 ms |
256 KB |
corner_case_27.txt |
AC |
3 ms |
256 KB |
corner_case_28.txt |
AC |
3 ms |
256 KB |
corner_case_29.txt |
AC |
3 ms |
256 KB |
random_case_00.txt |
AC |
3 ms |
256 KB |
random_case_01.txt |
AC |
3 ms |
256 KB |
random_case_02.txt |
AC |
3 ms |
256 KB |
random_case_03.txt |
AC |
3 ms |
256 KB |
random_case_04.txt |
AC |
3 ms |
256 KB |
random_case_05.txt |
AC |
3 ms |
256 KB |
random_case_06.txt |
AC |
3 ms |
256 KB |
random_case_07.txt |
AC |
3 ms |
256 KB |
random_case_08.txt |
AC |
3 ms |
256 KB |
random_case_09.txt |
AC |
3 ms |
256 KB |
random_case_10.txt |
AC |
3 ms |
256 KB |
random_case_11.txt |
AC |
3 ms |
256 KB |
random_case_12.txt |
AC |
3 ms |
256 KB |
random_case_13.txt |
AC |
3 ms |
256 KB |
random_case_14.txt |
AC |
3 ms |
256 KB |
random_case_15.txt |
AC |
3 ms |
256 KB |
random_case_16.txt |
AC |
3 ms |
256 KB |
random_case_17.txt |
AC |
3 ms |
256 KB |
random_case_18.txt |
AC |
3 ms |
256 KB |
random_case_19.txt |
AC |
3 ms |
256 KB |