AtCoder Beginner Contest 314 #ABC314
2024-01-16AtCoder Beginner Contest 314 の A/B/C 問題の解法。
実装はこちら atcoder/abc/301-400/314 · michimani/atcoder 。
A - 3.14
円周率の小数点以下 100 桁をあらかじめ文字列として定義しておき、 3. に続けて \(N\) 文字目の文字を出力する。
#include <iostream>
using namespace std;
using ui = unsigned int;
int main()
{
string pi_d = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
ui n;
cin >> n;
cout << "3.";
for (ui i = 0; i < n; i++)
{
cout << pi_d[i];
}
cout << endl;
return 0;
}
提出 #49343200 - AtCoder Beginner Contest 314
B - Roulette
次のような map を用意する。
map<ui, vector<ui>- key: 賭けた目の個数 \(C_i\)
- value: 賭けた人 \(i\) の配列
map<ui, map<u_i, vector<ui>>>- key: 掛け目 \(A_{i,C_i}\)
- value: ↑の
map
この map を使うと、例えば「掛け目 \(2\) に賭けた人の中で、賭けた目の個数が一番少ない人たち」は、 map<ui, map<u_i, vector<ui>>> accm とすると
vector<ui> users = accm[1].begin()->second;
で表せる。
「賭けた目の個数が一番少ない」を begin() で取得できるのは、 C++ の std:map の仕様によるもので、 map の key は昇順にソートされているためである。
このサイズが \(0\) であれば 0 を出力して終了。 そうでなければ、サイズと各賭けた人の番号を半角スペース区切りで出力して終了。
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ui = unsigned int;
int main()
{
ui n;
cin >> n;
map<ui, map<ui, vector<ui>>> accm;
for (ui i = 0; i < n; i++)
{
ui c;
cin >> c;
for (ui j = 0; j < c; j++)
{
ui a;
cin >> a;
accm[a][c].push_back(i + 1);
}
}
ui x;
cin >> x;
if (accm.count(x) == 0)
{
cout << 0 << endl;
return 0;
}
cout << accm[x].begin()->second.size() << endl;
for (ui h = 0; h < accm[x].begin()->second.size(); h++)
{
if (h != 0)
{
cout << " ";
}
cout << accm[x].begin()->second[h];
}
cout << endl;
return 0;
}
提出 #49340791 - AtCoder Beginner Contest 314
C - Rotate Colored Subsequence
C - Rotate Colored Subsequence
\(S\) の各文字のポインタを、色ごとにまとめる。具体的には、下記のような map で記録する。
map<ui, vector<char *>> cs- key: 色 \(C_i\)
- value: 色 \(C_i\) である文字 \(S_i\) のポインタの配列
cs の各配列に対して値を右向きにシフトして、最後に \(S\) を出力する。
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ui = unsigned int;
int main()
{
ui n, m;
string s;
cin >> n >> m >> s;
map<ui, vector<char *>> cs;
for (ui i = 0; i < n; i++)
{
ui c;
cin >> c;
cs[c].push_back(&s[i]);
}
auto it = cs.begin();
while (it != cs.end())
{
char tmp = *it->second[it->second.size() - 1];
for (ui j = ui(it->second.size()) - 1; j > 0; j--)
{
*it->second[j] = *it->second[j - 1];
}
*it->second[0] = tmp;
it++;
}
cout << s << endl;
return 0;
}
提出 #49340115 - AtCoder Beginner Contest 314
comments powered by Disqus